数据结构 第6章 树和二叉树

《数据结构 第6章 树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树和二叉树6.1树的定义和基本概念6.2二叉树6.2.1二叉树的定义和基本术语6.2.2二叉树的性质6.2.3二叉树的存储结构6.3遍历二叉树6.3.1遍历二叉树6.3.2线索二叉树6.4树和森林6.4.1树的存储结构6.4.2森林与二叉树的转换6.5哈夫曼树及其应用树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，

2、可用树来描述其执行过程。等等。6.1树的定义和基本操作一．树的定义定义：树(Tree)是n(n>=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根(Root)的结点；（2）其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。在图6-1(c)中，树的根结点为A，该树还可以分为三个互不相交子集T0，T1，T2，具体请参见图6-2，其中T0

3、={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又可以分为三个不相交子集T000，T001，T002，其中，T000={J}，T001={K}，T002={L}。二．树的逻辑结构描述一棵树的逻辑结构可以用二元组描述为：tree=(k,R)k={ki∣1≤i≤n;n≥0,kielemtype}R={r}其中，k是具有相同特性的数据元素的集合;n为树中结点

4、个数，若n=0，则为一棵空树，n>0时称为一棵非空树，而关系r应满足下列条件：（1）有且仅有一个结点没有前驱,称该结点为树根;（2）除根结点以外,其余每个结点有且仅有一个直接前驱;（3）树中每个结点可以有多个直接后继(孩子结点)。例如，对图6-1(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)}四、基本术语1.结点：指树中的一个数据元素，一般用一个字母表示。度：一个结点包含子树的数目

5、，称为该结点的度。树中结点度的最大值称为树的度。3.树叶（叶子）：度为0的结点，称为叶子结点或树叶，也叫终端结点。4.孩子结点：若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图6-1（c）中A的孩子为B，C，D。5.双亲结点：若结点X有子女Y，则X为Y的双亲结点。6.祖先结点：从根结点到该结点所经过分枝上的所有结点为该结点的祖先，如图6-1（c）中M的祖先有A，D，H。7.子孙结点：某一结点的子女及子女的子女都为该结点子孙。8.兄弟结点：具有同一个双亲的结点，称为兄弟结点。9.分枝结点：除叶子结点外的所有结点，为分枝结点，也叫非终端结点。10．层数：根结

6、点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。11.树的高度（深度）：树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度为1。12.有序树：若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。13.无序树：若一棵树中所有子树的次序无关紧要，则称为无序树。14．森林（树林）：若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。五．树的基本运算(1)inittree(T)初始化树T。(2)root(T)求树T的根结点。(3)parent(T,x)求树T中，值为x的结点的双亲。(4)child(T,x

7、,i)求树T中，值为x的结点的第i个孩子。(5)addchild(y,i,x)把值为x的结点作为值为y的结点的第i个孩子插入到树中。(6)delchild(x,i)删除值为x的结点的第i个孩子。(7)traverse(T)遍历或访问树T。树的存储结构在计算机中，树的存储通常采用顺序存储结构和链式存储结构，但无论采用何种存储方式，都要求存储结构不但能存储各结点本身的数据信息，还要能唯一地反映树中各结点之间的逻辑关系1.双亲结点数组表示法#defineMaxnode100