数据结构与算法-树
抽象数据类型定义
若|D|=0,则称为空树;
否则:
(1) 在D中存在唯一的称为根的数据元素root,
(2) 当n>1时,其余结点可分为m (m>0)个互不相交的有限集T1, T2, …, Tm,其中Ti本身是一棵符合本定义的树,称为根root的子树。
例如:A是根;其余结点分成三个互不相交的子集,T1={B,E,F,K,L}; T2={C,G};T3={D,H,I,J,M};T1,T2,T3都是根A的子树,且本身也是一棵树。
表示方法
- 图
- 凹入表示法
- 嵌套集合表示法
- 广义表
基本术语
- 结点:数据元素+若干指向子树的分支
- 结点的度:分支的个数
- 树的度:树中所有结点的度的最大值
- 叶子节点:度为零的结点
- 分支(非终端)结点:度大于零的结点
- (从根到结点的)路径:由从根到该结点所经分支和结点构成
- 祖先结点、双亲结点、兄弟结点、堂兄弟节点、孩子结点、子孙结点:
- 结点的层次:假设根结点的层次为0,第 i 层结点的子树的根结点的层次为 i
- 树的深度:树中叶子结点所在的最大层次
- 有向树:(1) 有确定的根;(2) 树根和子树根之间为有向关系
- 有序树:子树之间存在确定的次序关系
- 无序树:子树之间不存在确定的次序关系
- 森林:是 m(m≥0)棵互不相交的树的集合
- 任何一棵非空树是一个二元组 Tree = (root,F)其中:root 被称为根结点,F 被称为子树森林
结构特点
线性结构 | 树型结构 |
---|---|
第一个数据元素无前驱 | 根结点(无前驱) |
最后一个数据元素(无后继) | 多个叶子结点(无后继) |
其它数据元素(一个前驱、一个后继) | 其它数据元素(一个前驱、多个后继) |