数据结构(C++描述)_树.ppt

《数据结构(C++描述)_树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树数据结构（C++描述）6.6哈夫曼树６.５树和森林6.4线索二叉树6.3遍历二叉树6.2二叉树6.1树的基本概念退出目录6.1树的基本概念6.1.1树的定义1．树的定义树是由n（n≥0）个结点组成的有限集合。若n=0，称为空树；若n>0，则：（1）有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；（2）除根结点以外的其它结点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm-1，每个集合Ti（i=0,1,…,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接

2、前驱，但可以有0个或多个直接后继。由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。树的结构参见图6-1。在图6-1(c)中，树的根结点为A，该树还可以分为三个互不相交子集T0，T1，T2，具体请参见图6-2，其中T0={B，E，F，J，K，L}，T1={C，G}，T2={D，H，I，M}，其中的T0，T1，T2都是树，称为图6-1（C）中树的子树，而T0，T1，T2又可以分解成若干棵不相交子树。如T0可以分解成T00，T01两个不相交子集，T00={E，J，K，L}，T01={F}，而T00又可

3、以分为三个不相交子集T000，T001，T002，其中，T000={J}，T001={K}，T002={L}。2．树的逻辑结构描述一棵树的逻辑结构可以用二元组描述为：tree=(k,R)k={ki∣1≤i≤n;n≥0,kielemtype}R={r}其中，n为树中结点个数，若n=0，则为一棵空树，n>0时称为一棵非空树，而关系r应满足下列条件：（1）有且仅有一个结点没有前驱,称该结点为树根;（2）除根结点以外,其余每个结点有且仅有一个直接前驱;（3）树中每个结点可以有多个直接后继(孩子结点)。例如，对图6-1(

4、c)的树结构,可以二元组表示为：K={A，B，C，D，E，F，G，H，I，J，K，L，M}R={r}r={(A,B)，(A,C)，(A,D)，(B,E)，(B,F)，(C,G)，(D,H)，(D,I)，(E,J)，(E,K)，(E,L)，(H,M)}3．树的基本运算树的基本运算可以定义如下几种：(1)inittree(&T)初始化树T。(2)root(T)求树T的根结点。(3)parent(T,x)求树T中，值为x的结点的双亲。(4)child(T,x,i)求树T中，值为x的结点的第i个孩子。(5)addchil

5、d(y,i,x)把值为x的结点作为值为y的结点的第i个孩子插入到树中。(6)delchild(x,i)删除值为x的结点的第i个孩子。(7)traverse(T)遍历或访问树T。6.1.2基本术语1.结点指树中的一个数据元素，一般用一个字母表示。2.度一个结点包含子树的数目，称为该结点的度。3.树叶（叶子）度为0的结点，称为叶子结点或树叶，也叫终端结点。4.孩子结点若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图6-1（c）中A的孩子为B，C，D。5.双亲结点若结点X有子女Y，则X为Y的

6、双亲结点。6.祖先结点从根结点到该结点所经过分枝上的所有结点为该结点的祖先，如图6-1（c）中M的祖先有A，D，H。7.子孙结点某一结点的子女及子女的子女都为该结点子孙。8.兄弟结点具有同一个双亲的结点，称为兄弟结点。9.分枝结点除叶子结点外的所有结点，为分枝结点，也叫非终端结点。10．层数根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。11.树的高度（深度）树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度为1。12.树的度树中结点度的最大值称为树的度。13.

7、有序树若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。14.无序树若一棵树中所有子树的次序无关紧要，则称为无序树。15．森林（树林）若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。6.1.3树的表示1．树形结构表示法具体参见图6-1。2.凹入法表示法具体参见图6-3。3.嵌套集合表示法具体参见图6-4。4.广义表表示法对图6-1（c）的树结构，广义表表示法可表示为：（A（B（E（J，K，L），F），C（G），D（H（M），I）））6.1.4树的性质性质1树中的结点数等

8、于所有结点的度加1。证明：根据树的定义，在一棵树中，除根结点以外，每个结点有且仅有一个直接前驱，也就是说，每个结点与指向它的一个分支一一对应，所以，除根结点以外的结点数等于所有结点的分支数（即度数），而根结点无直接前驱，因此，树中的结点数等于所有结点的度数加1。性质2度为k的树中第i层上最多有ki-1个结点（i≥1）。下面用数学归纳法证明：对于i=1，显然成立，假设对于i