没有合适的资源?快使用搜索试试~ 我知道了~
算法与数据结构:第六章 树和二叉树.ppt
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 22 浏览量
2021-09-19
23:35:27
上传
评论
收藏 928KB PPT 举报
温馨提示
试读
35页
算法与数据结构:第六章 树和二叉树.ppt
资源推荐
资源详情
资源评论
第六章 . 树和二叉树
( Chapter 6. Tree and Binary Tree)
§6.1 树的定义及基本操作
树型结构是一种非常重要的非线性数据结构,
可广泛应用于描述家族关系或行政组织机构。
树是 n (n≥0) 个结点的有限集。在一棵非空树中,
有且仅有唯一的根( root )结点,当 n>1 时,除根结
点外其余结点可分为 m (m>0) 个互不相交的有限集,它
们本身也是一棵树,称为根的子树( subtree )。
A
B C
E F G
D
一棵树如右图所示:
树还可以用下面
的形式化描述来表示:
Tree = ( D,R )
其中: D={ a
i
| a
i
D∈
0
, i=1,2,…,n, n≥0 }
R={ H }
H 为如下描述的二元关系:
1 、在 D 中存在唯一的根元素 root ,它在关系 H 下
无
前驱;
2 、若 D - {root}≠φ ,则存在 D - {root} 的一个划分 D
1
, ... ,
D
m
(m>0) ,对任意一对 j≠k ( 1≤j, k ≤ m) 有 D
j
∩ D
k
= φ ,且对任意的 i ( 1≤i≤ m) ,唯一存在数据元素 x
i
∈
D
i
,有 < root, x
i
> H∈ ;
3 、对于 D - { root } 的划分, H - { < root , x
1
> , … ,
< root ,
x
m
> } 有唯一的划分 H
1
,
H
2
, ... ,
H
m
( m>0 ) ,对任意
一对 j≠k ( 1≤j , k ≤ m) 有 H
j
∩ H
k
= φ ,且对任意的
i ( 1≤i ≤ m) , H
i
是 D
i
上的二元关系,且 ( D
i
, H
i
)
也是一棵符合本定义的树,称为 root 的子树。
树的一些基本术语:
结点的度( degree )
结点所拥有的子树的数目。
叶子结点( leaf-- 又称终端结点 terminal node )
度为零的结点。
度不为零的结点。
孩子( child-- 也称儿子 so
n )
结点的子树的根称为结点的孩子。
分支结点( branch node
-- 又称非终端结点 non-terminal node
)
双亲( parent )
结点是其孩子的双亲。
祖先( forefather )
从树根到双亲的所有结点称为该结点的祖先。
子孙( progeny )
以结点为根的子树的所有结点称为该结点的子孙。
兄弟( sibling )
同一父母的所有孩子互称兄弟。
层次( level )
树根为第一层,其孩子为第二层,孙子为第三层,
以此类推。
剩余34页未读,继续阅读
资源评论
wxg520cxl
- 粉丝: 24
- 资源: 3万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功