数据结构 C语言版 教学课件 作者 李云清 第07章_二叉树.ppt

《数据结构 C语言版 教学课件 作者 李云清 第07章_二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第7章　二叉树二叉树的基本概念二叉树的存储结构二叉树的基本运算二叉树其它运算的实现穿线二叉树树、森林和二叉树的转换二叉树的遍历7.1二叉树的基本概念二叉树的定义为：二叉树是一个由结点构成的有限集合，这个集合或者为空，或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。当二叉树的结点集合为空时，称为空二叉树。abedchfg二叉树有以下五种基本形态：(a)空二叉树(b)根和空的左、右子树(c)根和非空左子树、空右子树(d)根和空左子树、非空右子树(e)根和非空的左、右子树树型结构中

2、使用的术语如父母（双亲或前件）、子女（后件）、祖先、子孙、兄弟和路径等在二叉树中仍然可以沿用，但值得注意的是，二叉树并非一般树型结构的特殊形式，它们为两种不同的数据结构。二叉树与一般树型结构的主要区别在于：（1）二叉树中每个非空结点最多只有两个子女，而一般的树型结构中每个非空结点可以有0到多个子女；（2）二叉树中结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出是左子树还是右子树。二叉树具有以下重要性质：性质1一棵非空二叉树的第i层上至多有2i-1个结点（i≥1

3、）。证明：当i=1时，只有根结点，此时21-1=20=1，显然上述性质成立；又由于在二叉树中每个结点最多只能具有两个子女，因而第i层上结点的最大个数是第i-1层上结点的最大个数的两倍。于是第2层上结点的最大个数为2，第3层上结点的最大个数为4，……,则第i层上结点的最大个数即为2i-1。性质2深度为h的二叉树至多有2h-1个结点（h>1）。根据性质1，深度为h的二叉树最多具有的结点的个数为20+21+22+…+2h-1=2h-1。性质3对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，

4、则n0=n2+1。证明：假设二叉树中总的结点个数为n，度为1的结点个数为n1，则有：n=n0+n1+n2又由于在二叉树中除根结点外，其它结点均通过一条树枝且仅通过一条树枝与其父母结点相连，即除根结点外，其它结点与树中的树枝存在一一对应的关系；而二叉树中树枝的总条数为n1+2*n2，因而二叉树总结点的个数为：n=n1+2*n2+1于是有：n0+n1+n2=n1+2*n2+1显然n0=n2+1成立。如果一棵二叉树中所有终端结点均位于同一层次，而其它非终端结点的度数均为2，则称此二叉树为满二叉树。在满二叉树中

5、，若其深度为h，则其所包含的结点个数必为2h-1。下图中的二叉树即为一棵深度为3的满二叉树，其结点的个数为23-1=7。1425367如果一棵二叉树扣除其最大层次那层后即成为一棵满二叉树，且层次最大那层的所有结点均向左靠齐，则称该二叉树为完全二叉树。通俗地说，完全二叉树中只有最下面的两层结点的度数可以小于2，且最下面一层的结点都集中在该层最左边的若干位置上。下图所示的二叉树即为一棵深度为3的完全二叉树。若对深度相同的满二叉树和完全二叉树中的所有结点按自上而下、同一层次按自左向右的顺序依次编号

6、，则两者对应位置上的结点编号应该相同。142536对于完全二叉树，具有以下性质：性质4对于具有n个结点的完全二叉树，如果按照从上到下、同一层次上的结点按从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于序号为i的结点，有：（1）如果i>1，则序号为i的结点其双亲结点的序号为i/2（i/2表示对i/2的值取整）；如果i=1,则结点i为根结点，没有双亲；（2）如果2i>n，则结点i无左子女（此时结点i为终端结点）；否则其左子女为结点2i；（3）如果2i+1>n，则结点i无右子女；否则

7、其右子女为结点2i+1。7.2二叉树的基本运算ADTbintree{数据对象D：D是具有相同性质的数据元素构成的集合。数据关系R：如果D为空或D仅含一个元素，则R为空；否则D中存在一个特殊的结点root,称之为根结点，其无前驱；其它结点被分成互不相交的两个集合，分别构成root的左子树l和右子树r；若l和r非空，则它们的根结点lroot和rroot分别称为整棵二叉树根结点root的后继结点；左子树l和右子树r也是二叉树，因而它们中数据元素间的关系也同样满足R的定义。二叉树的基本操作如下

8、：(1)createbitree(t)(2)destroybitree(t)(3)root(t)(4)leftchild(t)(5)rightchild(t)(6)locate(t,x)(7)parent(t,x)(8)isempty(t)(9)depth(t)(10)numofnode(t)(11)addchild(t,x,t1,b)(12)deletechild(t,x,b)(13)setnull(t)(14)is