天津科技大学数据结构树和二叉树

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

1、第六章树和二叉树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.4.3树和森林的遍历6.6赫夫曼树及其应用6.6.1最优二叉树（赫夫曼树）6.6.2赫夫曼编码主要内容树型结构是一类重要的非线性结构,是以分支关系定义的层次结构。现实世界：如家谱、行政组织机构等。计算机领域：源程序的语法结构等。ABCDEFGHIJA(a)(b)(

2、c)树的例子:6.1树的定义和基本术语树(Tree)的定义：n(n≥0)个结点组成的有限集合。若n=0，则为空树；若n>0，则满足如下两个条件：(1)有且仅有一个特定的根(Root)结点；(2)当n>1时，根结点以外的其它结点可分为m(m>0)个互不相交的有限集合T1,T2,…Tm，其中每个集合本身又是一棵树，称其为根的子树(Subtree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。ABCDEFGHIJ(A(B(E(K,L),F),C(G),D(H(M),I,J))嵌套括号表示法IJFKLG

3、MCCDBEA嵌套集合凹入表树形表示树的表示方法：ABCDEFGHIJKLM基本术语1.结点2.结点的度3.叶子(终端结点)4.分枝结点(非终端结点)5.树的度6.孩子结点11.层次7.双亲结点12.树的高度(深度)8.兄弟结点13.有序树9.祖先结点14.无序树10.子孙结点15.森林(树林)ABCDEFGHIJKLM树的基本运算InitTree(&T)构造空树T。Root(T)求树T的根结点。Parent(T,x)求树T中值为x的结点的双亲。Child(T,x,i)求树T中值为x的结点的第i个孩子

4、。AddChild(T,y,i,x)树T中将值为x的结点作为值为y的结点的第i个孩子插入到树中。DelChild(T,x,i)删除值为x的结点的第i个孩子。Traverse(T)遍历或访问树T。6.2二叉树二叉树的定义由n(n≥0)个结点构成的有限集合，此集合或者为空集，或者由一个根结点及两棵互不相交的左、右子树组成，并且左右子树都是二叉树。特点：每个结点最多有两个孩子，即不存在度大于2的结点，有序树，其子树的顺序不能颠倒，即使只有一棵子树也要区分其是左子树还是右子树。二叉树不是树!意义：操作算法简单，且任何树都可与

5、二叉树相互转换，解决了树的存储结构及其运算中存在的复杂性。(a)空二叉树(b)仅有根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)根和左右子树图：二叉树的5种形式注：图(c)和图(d)是不同的两棵二叉树。AABABACB二叉树的基本运算InitBiTree(&T)构造空二叉树T。DestroyBiTree(&T)销毁二叉树T。Root(T)求T的根结点。Parent(T,e)求T中值为e的结点的双亲。LChild(T,e)/RChild(T,e)求T中值为e的结点的左/右孩子。LBrother(T

6、,e)/RBrother(T,e)求T中值为e的结点的左/右兄弟。Traverse(T)遍历二叉树T。AddLChild(&T,x,y)/AddRChild(&T,x,y)在T中，将值为y的结点作为值为x的结点的左/右孩子插入。DelLChild(&T,x)/DelRChild(&t,x)在T中，删除值为x的结点的左/右孩子。二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)。采用归纳法证明：i=1时，只有一个根结点，2i-1=20=1,命题成立。现假定对所多的j，1≤j

7、多有2j-1个结点。由假设可知，第i－1层上至多有2i-2个结点。由于二叉树每个结点的度最大为2，所以在第i层上最大结点数为第i－1层上最大结点数的二倍，即2×2i-2＝2i-1。命题得到证明。性质2：深度为k的二叉树至多有2k－1个结点(k≥1)。性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2+1设二叉树中度为1的结点数为n1，二叉树中总结点数为N。因为二叉树中所有结点均小于或等于2，所以：N＝n0＋n1＋n2而二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉

8、树中的分支总数，则有：N＝B＋1。由于这些分支都是由度为1和2的结点射出的，所以有：B＝n1+2*n2N＝B＋1＝n1＋2×n2＋1从而得到：n0+n1+n2=n1+2*n2+1n0＝n2+1两种特殊形态的二叉树：满二叉树深度为k且具有2k-1个结点的二叉树。满二叉树结点连续编号的方法：从根结点开始，自上而下、从左至右的顺序。完全二叉树如果一棵