§7树
§ 7.1 树的概念
【定义】 树（Tree ）是门（n>0）个结点的有限集合 T，它满足如下两个条件:
（1） 有且仅有一个特定的称为根（Root ）的结点；
（2） 其余的结点可分为m （ m，0 ）个互不相交的有限集合， 颗树，并称为根的子树其中每一个集合又都是
（Sub Tree ）。
【基本术语】k
O E
O G O H OI
1.
树的结点包含一个数据元素及若干指向其子树的分支 结点拥有的子树数称 为
结点的度 （degree ）。
图
如图7.1
, A的度为3 , C的度为1 , F的度为0
7.1.1
2.
度为0的结点称为叶子（leaf ）或终端结点。例如K、 I、J。度不为
FG、 0的结点称为分支结点或非终端结点。
、 M、
除根结点外，分支结点也称为内部结点。
3. 树的度 是树内各结点的度的最大值，如图7.1中树的度为
孩子（Child ），该结点称为孩子的 结点双亲 4. 的子树的根称为该结点的
（pare nt ）。 如图7.1.1 , B为A的子树的 B是A的孩子，而A则是B的双
根，则
亲。
兄弟 ），例如B、C、 将这D互为兄
同一个双亲的孩子之间互称为（sibli ng
些关系进一步推广，可认 为 D弟。 是M的祖父 所有结点。例如，M的祖先为 上的 结点的祖先是从根到该结点所经分支 H。 A、 D、 子孙，女口 B的为E、F、K、L。 结点的反之，结点的子树中的任一结点都称为该结点 层次（level ）是从根开始定义起，根为第一层，根的孩子为第二层。 的
若某结点在第x层，则其子树的根就 5. 6.
在 x+1层。 树中结点的最大层次称为树 高度或深度（depth ）。如图 的 7.1
如果将树中的结点的各子树看成从左到右是有次序的（即不能互
的树的深度为4。
换） 则称为无序树。如图O
，则称该树为有序树, 7.1.2
A
C B
JJ
否
6.
o o o o
图7.1.2两棵不同的有序树
7. 森林 （forest ）是m （ m，0）棵互不相交的树的集合。
高中信息技术-竞赛班数据结构专项培训教程-07树教案(20201123121210)
