树二叉树树、森林与二叉树的转换树的应用.ppt

《树二叉树树、森林与二叉树的转换树的应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、树二叉树树、森林与二叉树的转换树的应用第五章树和二叉树9/1/20211树和森林的概念树的定义树是由n(n0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，则有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；除根以外的其它结点划分为m(m0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。9/1/20212树的表示树型表示bacghdefij9/1/20213凹入表表示abdeijfcgh9/1

2、/20214嵌套集合表示嵌套括号表示ijdfghabcea(b(d,e(i,j),c(g,h)))9/1/20215结点(node)结点的度(degree)结点的子树个数分支(branch)结点度不为0的结点叶(leaf)结点度为0的结点子女(child)结点某结点子树的根结点双亲(parent)结点某个结点是其子树之根的双亲9/1/20216兄弟(sibling)结点具有同一双亲的所有结点祖先(ancestor)结点若树中结点k到ks存在一条路径，则称k是ks的祖先子孙(descendant)结点若树中结点k到ks存在一条路径，则称ks是k的子孙结点所

3、处层次(level)根结点的层数为1，其余结点的层数为双亲结点的层数加1树的高度(depth)树中结点的最大层数树的度(degree)有序树子树的次序不能互换无序树子树的次序可以互换森林互不相交的树的集合9/1/20217树的基本操作1、初始化2、求指定结点所在树的根结点3、求指定结点的双亲结点4、求指定结点的某一孩子结点5、求指定结点的最右边兄弟结点6、将一棵树插入到另一树的指定结点下作为它的子树7、删除指定结点的某一子树8、树的遍历9/1/20218二叉树(BinaryTree)二叉树的定义二叉树的五种不同形态一棵二叉树是结点的一个有限集合，该集合或

4、者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。9/1/20219性质1若二叉树的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i0)二叉树的性质证明：i=1时，有2i-1=20=1，成立假定：i=k时性质成立；当i=k+1时，第k+1的结点至多是第k层结点的两倍，即总的结点个数至多为2×2k-1=2k故命题成立9/1/202110性质2高度为k的二叉树最多有2k-1个结点。(k1)证明：仅当每一层都含有最大结点数时，二叉树的结点数最多，利用性质1可得二叉树的结点数至多为：20+21+22+23+…+2k-

5、1=2k－19/1/202111性质3对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0＝n2＋1证明：1、结点总数为度为0的结点加上度为1的结点再加上度为2的结点：n=n0+n1+n22、另一方面，二叉树中一度结点有一个孩子，二度结点有二个孩子，根结点不是任何结点的孩子，因此，结点总数为：n=n1+2n2+13、两式相减，得到：n0=n2+19/1/202112定义1满二叉树(FullBinaryTree)一棵深度为k且有2k-1个结点的二叉树。定义2完全二叉树(CompleteBinaryTree)若设二叉树的高度为h，则

6、共有h+1层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。9/1/202113性质4具有n个结点的完全二叉树的高度为log2n+1证明：设完全二叉树的高度为h，则有2h-1-1

7、双亲若i>1,则i的双亲为i/2若2*i<=n,则i的左子女为2*i；否则，i无左子女，必定是页结点，二叉树中i>n/2的结点必定是页结点若2*i+1<=n,则i的右子女为2*i+1，否则，i无右子女若i为奇数,且i不为1，则其左兄弟为i-1，否则无左兄弟；若i为偶数,且小于n，则其右兄弟为i+1，否则无右兄弟i所在层次为log2(i)+19/1/20211512435689107111213141516179/1/202116完全二叉树的数组表示一般二叉树的数组表示二叉树的存储数组表示9/1/202117单支树由于一般二叉树必须仿照完全二叉

8、树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。9/1/202118