二叉树的概念和术语.ppt

二叉树的概念和术语
二、树的定义〔Tree〕
树〔Tree〕是 n 个〔n≥0〕个结点的组成的有限集合 T ，当 T 为空集时称为空树；否那么它满足如下两个条件：
(1) 有且仅有一个特定的称为根〔Root〕的结点。
(2) 除根结点外的其余结点可分为 m〔m ≥0〕个互不相交的子集 T1，T2，···，Tm，其中每个子集Ti本身又是一棵树，并称其为根的子树〔Subtree〕。
以下图是一棵具有10个结点的树，即T＝{A，B，C，…，I，J}，结点A为树T的根结点，除根结点A之外的其余结点分为两个不相交的集合：T1＝{B，D，H，I，J}和T2={C，F，G}，T1和T2构成了结点A的两棵子树，子树T1的根结点为B，其余结点又分为两个不相交的集合：T11＝{D，H，I}，T12＝{E，J}。子树T2以C为根结点，又可划分为集合T21={F，G}。如此可继续向下分为更小的子树，直到每棵子树只有一个根结点为止。
A
B
C
D
E
G
F
H
I
J
树具有下面两个特点：
〔1〕树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。
〔2〕树中所有结点可以有零个或多个后继结点。
由此特点可知，右图所示不是树型结构。
A
B
C
D
E
G
F
H
I
J
A
B
C
D
E
G
F
H
I
J
三、 树的相关术语
结点：一个数据元素及假设干个指向其子树的分支。
结点的度：结点所拥有的子树的个数称为该结点的度。树的度：树中结点度的最大值。以下图中结点B、C、D的度为2；树的度为2。
叶子结点：度为0的结点称为叶子结点，或者称为终端结点。分支结点：度不为0的结点称为分支结点或非终端结点。图中的结点H、I、J、F、G为叶子结点；结点A、B、C，D、E为分支结点。
A
B
C
D
E
G
F
H
I
J
孩子、双亲和兄弟结点：树中结点子树的根称为该结点的孩子。相应地，该结点称为孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。
祖先、子孙：从树中根结点到某一结点所经过的分支上的所有结点称为该结点的祖先。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。
A
B
C
D
E
G
F
H
I
J
结点的层数：规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。
树的深度：树中所有结点的最大层数称为树的深度或高度。图中结点A的层数为1，结点B和C的层数为2，结点H、I和J的层数为4，树的深度为4。双亲在同一层结点互为堂兄弟，如结点D、E、F、G为堂兄弟。
A
B
C
D
E
G
F
H
I
J
有序树和无序树：如果一棵树中结点的各子树从左到右是有次序的，那么称这棵树为有序树；反之，那么称为无序树。后面讲到的二叉树为有序树。
森林：m〔m≥0〕棵互不相交的树的集合称为森林。
A
B
C
A
B
C
D
A
B
C
D
E
F
A
B
C
D
a b c d