软件技术基础树资料.pptx

赌王家族6.1 树的基本概念树(Tree)是n(n≥0)个结点的有限集合T。 若n=0时称为空树，否则：(1)有且只有一个特殊的结点时称为树的根(Root)结点；(2)若n1时，其余的结点被分为m(m0)个互不相交的子集T1, T2, T3…Tm，其中每个子集本身又是一棵树，称其为根的子树(Subtree)。 这是树的递归定义，即用树来定义树，而只有一个结点的树必定仅由根组成。ACDBAJGHIFE(a)只有根结点MNLK(b)一般的树图6-1树的示例形式树的基本术语(1)结点(node)：包含一个数据元素及若干指向其他结点的分支信息。(2)结点的度(degree) 、树的度：结点所拥有的子树的棵数称为结点的度。树中结点度的最大值称为树的度。 如图6-1(b)中结点A的度是3 ，结点B的度是2 ，结点M的度是0，树的度是3。ACDBJGHIFEMNLK(3) 叶子(left)结点、非叶子结点 树中度为0的结点，即无后继的结点，称为叶子结点(或终端结点)。 度不为0的结点称为非叶子结点(或非终端结点或分支结点)。 除根结点外，分支结点又称为内部结点。 如图中结点F、H、I、J、K、L、M、N是叶子结点，而所有其它结点都是分支结点。ACDBJGHIFEMNLK(4) 孩子结点、双亲结点、兄弟结点一个结点的直接后继称为该结点的孩子结点(child)或子结点；相应地，一个结点的直接前趋称为该结点的双亲结点(parent)或父结点。同一双亲结点的所有子结点互称为兄弟结点。如图中结点B 、C、D是结点A的子结点，而结点A是结点B 、C、D的父结点；类似地结点E 、F是结点B的子结点，结点B是结点E 、F的父结点。如图中结点B 、C、D是兄弟结点；结点E 、F是兄弟结点。ACDBJGHIFEMNLK（5） 层次、堂兄弟结点规定树中根结点的层次为1，其余结点的层次等于其双亲结点的层次加1。若某结点在第l (l ≥ 1)层，则其子结点在第l+1层。双亲结点在同一层上的所有结点互称为堂兄弟结点。如图6-1(b)中结点E、F、G、H、I、J。（6）树的深度(或高度)：树中结点的最大层次值，又称为树的深度，如图6-1(b)中树的深度为4。第1层第2层第3层第4层ACDBJGHIFEMNLK(7)结点的（层次）路径、祖先、子孙从根结点开始，到达某结点p所经过的所有结点成为结点p的层次路径(有且只有一条)。结点p的层次路径上的所有结点（p除外）称为p的祖先。以某一结点为根的子树中的任意结点称为该结点的子孙结点。AACBBC（8）有序树和无序树对于一棵树，若其中每一个结点的子树（若有）具有一定的次序，则该树称为有序树，否则称为无序树。例如： 若T1，T2为有序树，它们是两棵不同的树；若T1，T2为无序树，它们是两棵相同的树。 ACDBJGHIFEMNLK（9）森林(forest)： m(m≥0)棵互不相交的树的集合。 显然，若将一棵树的根结点删除，剩余的子树就构成了森林。ACDBJGHIFEMNLK图6.1 (b)一般的树树的表示形式倒悬树。是最常用的表示形式，如图6-1(b)。圆圈表示结点，结点的名字可写在圆圈内或圆圈旁。连线表示结点之间的关系AEGDCBAKMHNLICDBFJJGHIFEMNLK图6.1 (b)一般的树嵌套集合形式树的表示形式嵌套集合: 是一些集合的集体，对于任何两个集合，或者不相交，或者一个集合包含另一个集合。右图是图6-1(b)树的嵌套集合形式。圆圈表示结点圆圈的相互包含表示结点之间的关系。ACDBJGHIFEMNLK图6.1 (b)一般的树树的表示形式广义表形式(A(B,C,D))(A(B(E,F),C(G),D(H,I,J)))(A(B(E(K,L),F),C(G(M,N)),D(H,I,J)))括号表示结点括号的相互包含表示结点间的关系。ACDBJGHIFEMNLK图6.1 (b)一般的树树的表示形式目录表示ABEKLFC……D……凹入的线条表示结点线条的长短表示结点间的关系，长线条包含短线条。树的存储结构顺序存储顺序存储时，首先必须对树形结构的结点进行某种方式的线性化，使之成为一个线性序列，然后存储。链式存储链式存储时，使用多指针域的结点形式，每一个指针域指向一棵子树的根结点。由于树的分支数不固定，很难给出一种固定的存储结构，通常采用二叉树的形式存储树。6.2 二叉树的定义及其性质二叉树的定义 我们把满足以下两个条件的树形结构叫做二叉树（binary tree）：（1）每个结点的度都不大于2；（2）每个结点的孩子结点次序不能任意颠倒。由此定义可以看出，一个二叉树中的每个结点只能含有0，1或2个孩子，并且每个孩子有左右之分。 位于左边的孩子叫做左孩子 位于右边的孩子称为右孩子AAAA(c)(d)(a)(b)(e)(