第6章_树型结构

1、第6章 树 数据结构（C描述） 目录目录 在许多领域许多问题不能或难用线性结构表示（哈夫曼编码、判定问题），故研究非线性的数据结构。树是一种应用十分广泛的非线性数据结构。6.1 树的基本概念树的基本概念6.1.1 树的定义树的定义树的定义 树是由n（n0）个结点组成的有限集合。若n=0，称为空树；若n0，则称为非空树，在任一棵非空树中：（1）有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；（2）除根结点以外的其它结点可以划分为m（m0）个互不相交的有限集合T0，T1，Tm-1，且每个集合Ti（i=0,1,m-1）本身又是一棵树，称为根的子树根的子树。由此可知，树的定义是一

2、个递归的定义递归的定义，即树的定义中又用到了树的概念。 从定义中看出树结构具有以下特点：（1）有且仅有一个结点没有直接前驱，即根结点。（2）除根结点之外，其余所有结点有且仅有一个直接前趋结点。（3）包括根结点在内，每个结点可以有多个直接后继结点。从此可见，树型结构的特点是，数据元素之间存在着一对多的关系。树的结构参见图6-1。 A A B C D I H G F E J K L M （a）空树 （b）仅含有根结点的树 （c） 含有多个结点的树 图 6-1 树的示意图 在图6-1(c)中，树的根结点为A，该树还可以分为三个互不相交子集T0，T1，T2，具体请参见图6-2，其中T0=B，E，F，J

3、，K，L，T1=C，G，T2=D，H，I，M而T0，T1，T2又可以分解成若干棵不相交子树。如：T0可以分解成T00，T01两个不相交子集，T00=E，J，K，L，T01=F，而T00又可以分为三个不相交子集T000，T001，T002，其中，T000=J，T001=K，T002=L。 C G B E F J K L D H I M (a) T0子树 (b)T1子树 (c)T2子树 图 6-2 树的三个子树 6.1.2 基本术语基本术语1.树的结点指树中的一个数据元素，一般用一个字母表示。 2.结点的度 一个结点包含子树的数目，称为该结点的度。 3.树叶（叶子） 度为0的结点，称为叶子结点或树

4、叶，也叫终端结点。 4.分支结点（非终端结点）除叶子结点外的所有结点，为分支结点。通常又将除根结点之外的分支结点称为内部结点内部结点。6.双亲结点若结点X有子女Y，则X为Y的双亲结点。 7.祖先结点8.子孙结点某一结点的子女的子女为该结点子孙。 5.孩子结点若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子。如图6-1（c）中A的孩子为B，C，D。 10结点的层次从根结点开始定义，根为第一层，根的孩子为第二层，依次类推。 11. 树的高度树的高度（深度深度） 树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度为1。12.树的度树的度树中结点度的最大值称为树的度。

5、9.兄弟结点具有同一个双亲的结点，称为兄弟结点。 13. 有序树有序树 若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。 14. 无序树无序树 若一棵树中所有子树的次序无关紧要，则称为无序树。 15森林（树林）森林（树林） 若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。树与森林的关系 6.1.3 树的表示树的表示1树形结构表示法树形结构表示法 （掌握）（掌握）具体参 见图6-1 。 A A B C D I H G F E J K L M （a）空树 （b）仅含有根结点的树 （c） 含有多个结点的树 图 6-1 树的示意图 2. 凹入法表示法凹入法

6、表示法具体参见图6-3 A B E J K L F C G D H M I 图 6-3 图 6-1(c)的树的凹入法表示 3. 嵌套集合表示法嵌套集合表示法具体参 见图6-4 。 A B E J K L F C G D H M I 图 6-4 图 6-1(c)的树的集合表示 4.广义表表示法广义表表示法 对图7-1（c）的树结构，广义表表示法可表示为：A（B（E（J，K，L），F），C（G），D（H（M），I）6.2 树的存储结构树的存储结构 仅考虑链式存储结构链式存储结构，有两种：多重链表表示法、二重链表表示法6.2.1 多重链表表示法多重链表表示法 每个结点由一个数据域和若干个指针域若干个

7、指针域组成，其中，每个指针域指向该结点的一个孩子。一棵树中不同结点的度数可能不同，每个结点设置的指针域的数目可能就有所不同。通常有下面的两种方案：1、定长结点的多重链表表示法、定长结点的多重链表表示法取树的度数树的度数作为每个结点的指针域的个数每个结点的指针域的个数。缺点：由于树中多数结点的度可能小于树的度，因而这种方法将会导致许多结点的部分指针域为空，造成空间的浪费。2、不定长结点的多重链表示法、不定长结点的多重链表示法 树中每个结点都取自己的度数作为指针域的个数，显然，对于叶结点就不必设指针域。另外，每个结点除了数据域、指针域外，还应设一个度数域用来指出该结点的度数，即指出该结点中指针域的

8、个数。6.2.2 二重链表表示法二重链表表示法 这种方法是对树中的每个结点设三个域：数据域和2个指针域，第一个指针域给出该结点的第一个孩子（即最左边子树的根结点，长子长子）的地址，第二个指针域给出该结点的右边第一个兄弟结点（次弟次弟）的地址。 树的三重链表表示，增加了一个指针域即给出该结点的双亲结点的地址。6.3 二叉树二叉树 在树型结构中，有一类简单而又重要的树，它的每个结点最多只有2棵子树，这种树被称为二叉树。6.3.1 二叉树的定义二叉树的定义1二叉树的定义二叉树的定义 和树结构定义类似，二叉树的定义也可以递归形式给出：二叉树是n（n0）个结点的有限集，它或者是空集（n=0），或者由一个

9、根结点及两棵不相交的左子树和右子树组成。 二叉树的特点：二叉树的特点： 每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点 二叉树是有序树（树为无序树），其子树的顺序不能颠倒。因此，二叉树有五种不同的形态，参见下图。 L R L R (a) (b) (c) (d) (e) 图 6-5 二叉树的五种不同的形态 6.3.2 二叉树的性质二叉树的性质性质性质1 若二叉树的层数从1开始，则二叉树的第k层结点数，最多为个 （k0）。可以用数学归纳法证明之。性质性质2 深度（高度）为k的二叉树最大结点数为 （k0）证明： 深度为k的二叉树，若要求结点数最多，则必须每一层的结点数都为最多，由性

10、质1可知，最大结点数应为每一层最大结点数之和。即为： 20+21+2k-1=2k-1。2k-12k-1性质性质3 对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。证明：设二叉树中度为1的结点个数为n1，根据二叉树的定义（二叉树中所有结点的度均小于或等于2)可知，该二叉树的结点总数 n=n0+n1+n2 (1)。 再看二叉树中的分支数。除了根结点外，其余结点都有一个分支进入。设B为分支总数，则 n=B+1由于这些分支是由度为1或2的结点射出的，所以又有B=n1+2*n2 于是得：n=n1+2n2+1 (2)由（1）和（2）得：n0=n2+1下面讨论两种特殊的

11、二叉树：满二叉树和完全二叉树。 满二叉树满二叉树 深度为k具有2k-1个结点的二叉树，称为满二叉树。或或者说：者说：如果一棵二叉树中任何结点，或者是叶结点，或者是有两棵非空子树，且叶子结点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。 从定义可知：必须是二叉树的每一层上的结点数都达到最大，否则就不是满二叉树。例：深（高）度为4的满二叉树如图（15个结点） 可以对满二叉树的结点进行编号，约定编号从根结点起，自上而下，自左而右，由此引出完全二叉树的定义。完全二叉树完全二叉树 如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1 n的结点一一对一一对应应，则称

12、这棵二叉树为完全二叉树。（例：k=3,n=4,5,6） 从满二叉树及完全二叉树定义可以得出如下结论： 满二叉树一定是一棵完全二叉树 反之完全二叉树不一定是一棵满二叉树。 满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。深度为4的满二叉树和完全二叉树（8个结点）如图6-6所示。 A B C D E F G H I J K L M N O A B C D E G H F （a）满二叉树 (b)完全二叉树 图 6-6 满二叉树和完全二叉树示意图 性质性质4 具有n个结点的完全二叉树高度为log2(n)+1 或 log2（n+1） 。（注意x表示取不大于x（即）的最大整数，

13、也叫做对x下取整，x表示取不小于x（即）的最小整数，也叫做对x上取整。)1、二叉树中度为0的结点数为50，度为1的结点数为30，总结点数为_。湖南大学考研题湖南大学考研题性质3：n0=n2+12、树最合适用来表示_。A 有序数据元素 B 无序数据元素 C 元素之间无联系的数据 D元素之间分支层次关系的数据3、对于有n 个结点的二叉树, 其高度为（ ）【武汉交通科技大学 一、5 (4分)】 Anlog2n Blog2n Clog2n+1 D不确定4、深度为h的满m叉树的第k层有（ ）个结点。(1 k h)【北京航空航天大学 一、4（2分）】 Amk-1 Bmk-1 Cmh-1 Dmh-15、在一

14、棵高度为k的满二叉树中，结点总数为（ ）【北京工商大学 一、3 (3分)】 A2k-1 B2k C2k-1 Dlog2k+16、高度为 K的二叉树最大的结点数为（ ）。 【山东大学 二、3 (1分)】A2k B2k-1 C2k -1 D2k-1-17、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A9 B11 C15 D不确定 【北京工商大学一.7(3分)】性质性质3 对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。6.3.3 二叉树的存贮结构二叉树的存贮结构1顺序存贮结构顺序存贮结构 即用一维数组TM来存储二叉树的数据元

15、素，按照二叉树的结点层次编号结点层次编号依次来存放。如：见图这种结构适合于存储完全二叉树和满二叉树适合于存储完全二叉树和满二叉树，若是一般二叉树应如何处理？必须按完全二叉树完全二叉树的形式来存贮树中的结点，这就要虚设很多空结点才能使它成为一棵完全二叉树。如图可见这将造成空间的浪费。例：k=3的一般二叉树 A B C D E F G A B C D . A B C D E F G A B C D 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 (a)满二叉树的存储形式 (b)非完全二叉树的存储形式 图 6-7 二叉树的顺序存储形式 对于一棵二叉树,若采用顺序存贮时,当它为完全

16、二叉树（或满二叉树）时,比较方便,若为非完全二叉树,将会浪费大量存贮存贮单元。 最坏情况的非完全二叉树是全部只有右分支,设高度为K,则需占用个 存贮单元,而实际只有k个元素,实际只需k个存储单元。因此，对于非完全二叉树非完全二叉树，宜采用下面的链式存储结构链式存储结构。2K-12二叉链表存贮结构二叉链表存贮结构 （1）二叉链表表示）二叉链表表示将一个结点分成三部分,一部分存放结点本身信息,另外两部分为指针,分别存放左、右孩子的地址。二叉链表中一个结点可描述为: 1child data rchild 对于图6-7所示二叉树,用二叉链表形式描述见图6-8。 A B C D E F G root A

17、 root B C D (a)完全二叉树的链表 (b)非完全二叉树的二叉链表 图 6-8 二叉树的二叉链表表示法 （2）二叉链表的类型说明）二叉链表的类型说明二叉链表的数据类型描述如下:typedef struct btnode int data ; /结点数据类型struct btnode *lchild, *rchild; /定义左、右孩子为指 针型 bitree;有时，为了便于找到结点中的双亲，还可在结点结构中增加一个指向双亲的指针域，这种存贮结构称为三叉链表。6.4 遍历二叉树遍历二叉树 （二叉树的运算）二叉树的运算） 所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个

18、结点仅被访问访问一次。 这里提到的“访问”是指对结点施行某种操作，操作可以是输出结点信息，修改结点的数据值等，但要求这种访问不破坏它原来的数据结构。在本书中，我们规定访问是输出结点信息data，且以二叉链表作为二叉树的存贮结构。 遍历对线性结构而言非常简单，只需顺序扫描每个数据元素即可。但对非线性结构，要找到一种规律，以便二叉树上各结点能排列成一个线性序列。 二叉树由三部分组成：根结点（D），左子树（L），右子树（R）。要遍历这三个基本部分，可有六种可能的顺序：DLR（先序或前序） DRL（逆先序遍历） LDR(中序） RDL（逆中序） LRD （后序） RLD（逆后序）规定：二叉树中必须先左

19、后右(左右顺序不能颠倒)，则只有DLR、LDR、LRD三种遍历规则。DLR称为前根遍历(或前序遍历、先序遍历、先根遍历)，LDR称为中根遍历(或中序遍历)，LRD称为后根遍历(或后序遍历)。6.4.1先序遍历先序遍历所谓先序遍历，就是根结点最先遍历，其次左子树，最后右子树。递归遍历递归遍历先序遍历二叉树的递归遍历算法描述为：若二叉树为空，则算法结束;否则（1）输出（访问）根结点；）输出（访问）根结点；（2）再按先序遍历方式遍历根结点的左子树）再按先序遍历方式遍历根结点的左子树;（3）最后按先序遍历方式遍历根结点的右子树）最后按先序遍历方式遍历根结点的右子树;递归算法如下:void preord

20、er(bitree *root)if(root!=NULL) printf(“%d”,root-data); preorder(root-lchild); preorder (root-rchild); 6.4.2中序遍历中序遍历所谓中序遍历，就是根在中间，先左子树，然后根结点，最后右子树。递归遍历递归遍历中序遍历二叉树的递归遍历算法描述为：若二叉树为空，则算法结束；否则中序遍历左子树中序遍历左子树;输出根结点输出根结点;中序遍历右子树。中序遍历右子树。算法如下:void inorder(biteee *root) if (root!=NULL) inorder(root-lchild); p

21、rintf(“%d”,root-data); inorder(root-rchild);6.4.3 后序遍历后序遍历所谓后序遍历，就是根在最后，即先左子树，然后右子树，最后根结点。递归遍历递归遍历后序遍历二叉树的递归遍历算法描述为：若二叉树为空，则算法结束;否则（1）后序遍历左子树）后序遍历左子树:（2）后序遍历右子树）后序遍历右子树;（3）访问根结点。）访问根结点。算法如下:void postorder( bitree *root)if (root!=NULL) postorder (root-lchild); postorder (root-rchild); printf(“%d”,roo

22、t-data);例如，可以利用上面介绍的遍历算法，写出如下图所示二叉树的三种遍历序列为： A B C D E F G H 图 6-11 一棵二叉树 先 序 遍 历 序 列 ：ABDGCEFH中 序 遍 历 序 列 ： BGDAECFH后 序 遍 历 序 列 ： GDBEHFCA例题例题另外，在编译原理中，有用二叉树来表示一个算术表达式的情形。在一棵二叉树中，若用操作数代表树叶，用操作数代表树叶，运算符代表非叶子结点运算符代表非叶子结点，则这样的树可以代表一个算术表达式。 若按前序、中序、后序对该二叉树进行遍历，则得到的遍历序列分别称为前缀表达式(或称波兰式)、中缀表达式、后缀表达式(逆波兰式)

23、。具体参见图6-12。右图所对应的前缀表达式：-*abc。右图所对应的中缀表达式：a*b-c。右图所对应的后缀表达式：ab*c-。 a c b * - 图 6-12 表达式 a*b-c 代表的二叉树 6.4.4 遍历二叉树的非递归算法遍历二叉树的非递归算法递归算法递归算法：简明，但效率较低，且有的程序设计语言不允许函数递归调用。故要讨论遍历二叉树的非递归算法非递归算法。均用栈保存遍历过程中经历的结点的左右孩子（指向孩子的指针），用一维数组SM作为栈存放元素，top为栈顶指针。1、先序遍历二叉树的非递归算法利用一个一维数组作为栈，来存储二叉链表中结点，算法思想为：算法思想为： 从二叉树根结点开始

24、，先输出输出结点信息，沿左左子树子树一直走到末端(左孩子为空)为止，在走的过程中，遇到结点有右孩子的，则把指向结点右孩子的指针进栈，当左子树为空时，从栈顶退出一个指针信息（即退出某结点的右孩子）。如此重复，直到栈为空。void preorder(bitree *root) bitree *p,*s100; int top=0; /top为栈顶指针 p=root;do while(p!=NULL) printf(“%d”,p-data); if(p-rchild!=NULL) stop+=p-rchild; p=p-lchild; if(top=0) p=s-top; while(top=0);

25、2中序遍历二叉树的非递归算法同样利用一个一维数组作栈，来存贮二叉链表中结点，算法思想为：从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，把依次遇到的结点进栈,待左子树为空时,从栈中退出结点并访问,然后再转向它的右子树。如此重复，直到栈空或指针为空止。算法如下:void inorder ( bitree *root) bitree *p,*s100; /s为一个栈，top为栈顶指针 int top=0; p=root;do while(p!=NULL) stop +=p;p=p-lchild; if(top=0) p=s-top; printf(“%d”,p-data)

26、; p=p-rchild; while(top=0);6.4.5 遍历算法应用举例遍历算法应用举例 例1 由二叉树的前序序列和中序序列建立该二叉树分析：分析： 若二叉树的任意两个结点的值都不相同，则二叉树的前序序列和中序序列能唯一确定一棵二叉树。另外，由前序序列和中序序列的定义可知，前序序列中第一个结点必为根结点，而在中序序列中，根结点刚好是左、右子树的分界点，因此，可按如下方法建立二叉树：1.用前序序列的第一个结点作为根结点;2.在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列(左、右子树);3.根据左、右子树的中序序列中的结点个数，将前序序列去掉根结点后的序列划分为左

27、、右两个序列，它们分别是左、右子树的前序序列;4.对左、右子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。假设前序序列为ABDGHCEFI， 中序序列为GDHBAECIF， 则得到的二叉树如下页所示1。A为根结点A BDGH CEFI GDHB A ECIF BDGHCEFIA2. B为左子树的根结点B DGHGDH BCEFIDHGBA3. D为左子树的左子树的根结点 A B G H D C E F I A B G H D C FI E 4。C为右子树的根结点 A B G H D C F I E 5。F为右子树的右子树的根结点C E FIE C IF思考：能否根据中序、后

28、序求前序？能否根据前序、后序求中序？例2 按层次遍历一棵二叉树对于一棵二叉树，若规定遍历顺序为从上到下(上层遍历完才进入下层)，从左到右(同一层从左到右进行，这样的遍历称为按层次遍历：例1的树的层次遍历序列为：ABCDEFGHI。下面用一个一维数组来模拟队列，实现二叉树的层次遍历。Void lorder (bitree * t) bitree *qmaxsize,*p; / maxsize为最大容量 int f,r; / f,r类似于头尾指针q0=t; f=r=0; while (fdata); if(p -lchild!=NULL) r+; qr=p-1child; /入队 if (p-rc

29、hild!=NULL) r+; qr=p-rchild; /入队 作业：作业：1、一棵度为2的树与一棵二叉树有何区别？2、用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的前序、中序、后序遍历序列。3、假设一棵二叉树的前序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK，请写出二叉树的后序遍历序列。4、假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。请写出二叉树前序遍历序列。12311458912136710141512345671231145891267101234566.5 二叉排序树二叉排序树(二叉搜索树，二叉查找树

30、）二叉搜索树，二叉查找树）1什么是二叉排序树什么是二叉排序树二叉排序树（Binary Sorting Tree），它或者是一棵空树，或者是一棵具有如下特征的非空二叉树：(1)若它的左子树非空，则左子树上所有结点的关键字均小于根结点的关键字；(2)若它的右子树非空，则右子树上所有结点的关键字均大于等于根结点的关键字； (3)左、右子树本身又都是一棵二叉排序树。下图各例是否为二叉排序树？（为了讨论问题的方便，假设树中每个结点的值是一个十进制整数）2、下面给出构造二叉排序树的算法、下面给出构造二叉排序树的算法：将一个给定的数据元素构造为相应的二叉排序树，通常采用逐步插入结点逐步插入结点的方法来构造二

31、叉排序树。设k=k1,k2,.,kn为数据元素序列，从k1开始依次取序列中的元素，每取出一个元素ki,按下列原则建立二叉排序树的一个新结点：（1）若二叉排序树为空，则新的数据元素就是二叉排序树的根结点。（2）若二叉排序树非空，则将新的数据元素与该二叉树的根结点的值进行比较，若小于根结点的值，则将新的数据元素插入到根结点的左子树中；否则，插入到右子树中。这个过程是一个递归的过程递归的过程，因为数据元素插入到左子树或右子树也同样是按这个原则递归进行的。（例）例如，结定关键字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序树过程如下图所示。 79 62 79 68 62

32、 79 68 62 79 90 88 68 62 79 90 (a) (b) (c) (d) (e) 88 68 62 79 90 89 89 17 88 68 62 79 90 17 5 88 68 62 79 90 89 (f) (g) (h) 89 17 5 88 68 62 79 90 100 89 17 5 88 68 62 79 90 100 120 图 7-6 二叉排序树的生成过程 (i) (j) （注：排列顺序不一样，得到的二叉排序树也不一样）二叉排序树与关键字排列顺序有关吗?a、递归算法bitree *Inserttree(bitree *t, int x) if(t=NUL

33、L) t=( bitree *)malloc(sizeof(bitree); t-data=x; t-lchild=NULL; t-rchild=NULL; else若二叉排序树为空，则新的数据元素就是二叉排序树的根结点。 if(xdata) t-lchild=Inserttree(t-lchild,x); else t-rchild=Inserttree(t-rchild,x); return(t);b、生成二叉排序树的非递归算法： bitree *creat(bitree *t) bitree *s,*p,*q; int x;若二叉排序树非空，则将新的数据元素与该二叉树的根结点的值进行比较

34、，若小于根结点的值，则将新的数据元素插入到根结点的左子树中；否则，插入到右子树中。scanf(“%d”,&x);while(x!=0)s= ( bitree *)malloc(sizeof(bitree);s-data=x;s-lchild=s-rchild=NULL;if(t=NULL) t=s;else p=t; while(p) q=p; if(s-datadata) p=p-lchild; else p=p-rchild; if(s-datadata) q-lchild=s;else q-rchild=s; /插入结点算法scanf(“%d”,&x); /while循环结束return

35、(t);3、二叉排序、二叉排序 树上的查找树上的查找(检索算法）检索算法） （1）二叉排序）二叉排序 树的查找思想树的查找思想若二叉排树为空，则查找 失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成功。（2）二叉排序树查找的算法实现）二叉排序树查找的算法实现a、递归算法： bitree *bstsrch(bitree *t,int k) if(t=NULL)|(t-data=k) return(t); else if(t-data rc

36、hild,k); else return(bstsrch(t-lchild,k); b、非递归算法bitree *search(bitree *t,int k) while(t!=NULL) if(t-data=k) return(t); else if(t-datarchild; else t=t-lchild; return(NULL);4、删除运算、删除运算在二叉排序树上删除一个结点需注意：要保证删除后所得的二叉树仍是一棵二叉检索树。考虑下面三种情况：1）若要删除的是叶子结点若要删除的是叶子结点 最简单的一种，只要将其双亲结点与它之间的链接的指针置空即可。如图 2）若要删除的结点只有左子

37、树或只有右子树，即单支若要删除的结点只有左子树或只有右子树，即单支结点。结点。a、若被删除的结点没有左子树，则可用其右子树的根结点取代被删除结点的位置。b、若被删除结点没有右子树，则可用其左子树的根结点取代被删除结点的位置。3）若删除的结点具有左、右子树。若删除的结点具有左、右子树。方法：首先将该结点的中序前趋结点的值赋给该结点的值，然后再删除它的中序前趋结点。由于此时，它的中序前趋结点的右指针为空，只要将中序前趋结点的左指针链接到中序前趋结点所在的链接位置即可。5二叉排序树查找的性能分析二叉排序树查找的性能分析 在二叉排序树查找中，成功的查找次数不会超过二叉树的深度，而具有n个结点的二叉排序

38、树的深度，最好为log2（n+1） ，最坏为n。因此，二叉排序树查找的最好时间复杂度为O(log2n)，最坏的时间复杂度为O(n)，一般情形下，其时间复杂度大致可看成O(log2n)，比顺序查找效率要好，但比二分查找要差。 即使关键字相同的一组数据，若先后插入的次序不同插入的次序不同，所生成的二叉排序树也不同生成的二叉排序树也不同，则查找的时间性能也不同，当要求查找的性能较高时，要对构成二叉排序树的过程进行“平衡化”处理，形成二叉平衡树。 6.6 平衡二叉树平衡二叉树1平衡二叉树的概念平衡二叉树的概念平衡二叉树(balanced binary tree)是由阿德尔森一维尔斯和兰迪斯(Adels

39、on-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。平衡二叉树平衡二叉树: 若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二叉树为平衡二叉树。平衡因子：平衡因子：将该结点的左子树深度减去右子树深度的值，称为该结点的平衡因子(balance factor)。也就是说，一棵二叉排序树中，所有结点的平衡因子只能为0、1、-1时，则该二叉排序树就是一棵平衡二叉树， 5 2 3 4 16 7 图 7-8 一棵平衡二叉树 6 1 2 3 4 8 5 7 图 7-9 一棵非平衡二叉树 2. 非平衡二叉树的平衡处理非平衡二叉树的平衡处理 若一棵二叉

40、排序树是平衡二叉树，扦入某个结点后，可能会变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成一棵平衡二叉树。处理的原则处理的原则应该是处理与扦入点最近的最近的、而平衡因子又比1大或比-1小的结点。下面将分四种情况讨论平衡处理。 （1）LL型型 的处理的处理(左左型左左型)如图7-10所示，在C的左孩子B上扦入一个左孩子结点A，使C的平衡因子由1变成了2，成为不平衡的二叉树序树。这时的平衡处理为：将C顺时针旋转，成为B的右子树，而原来B的右子树则变成C的左子树，待扦入结点A作为B的左子树。(注：图中结点旁边的数字表示该 结点的平衡因子) 平衡外理 a 1 A B C 0 2 C B

41、A 0 0 0 图 7-10 LL 型平衡外理 （2）LR型的处理型的处理(左右型左右型)如图7-11所示，在C的左孩子A上扦入一个右孩子B，使的C的平衡因子由1变成了2，成为不平衡的二叉排序树。这是的平衡处理为：将B变到A与C 之间，使之成为LL型，然后按第(1)种情形LL型处理。 0 -1 C A B 2 0 1 C A B 2 B 0 0 C A 0 平衡处理 旋转 图 7-11 LR 型平衡处理 （3）RR型的处理型的处理(右右型右右型)如图7-12所示，在A的右孩子B上扦入一个右孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将A逆时针旋转，成为B的左

42、子树，而原来B的左子树则变成A的右子树，待扦入结点C成为B的右子树。 平衡处理 a -1 C B A 0 -2 C B A 0 0 0 图 7-12 RR 型平衡处理 （4）RL型的处理型的处理(右左型右左型)如图7-13所示，在A的右孩子C上扦入一个左孩子B，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将B变到A与C之间，使之成为RR型，然后按第(3) 种情形RR型处理。 平衡处理 a C B A 0 0 0 图 7-13 RL 型平衡处理 -1 -2 C B A B 0 1 -2 A 旋转 C 例1，给定一个关键字序列4,5,7,2,1,3,6，试生成一棵平衡二

43、叉树。分析：平衡二叉树实际上也是一棵二叉排序树，故可以按建立二叉排序树的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，最后就可以建成一棵平衡二叉树。具体生成过程见图7-14。 (a)插入 4 (b)插入 5 (c)插入 7 RR 型 4 0 4 5 0 -1 7 4 5 -2 -1 0 0 0 4 5 7 0 LL 型 (d)插入 2 (e)插入 1 4 2 5 7 1 0 0 0 0 0 4 2 5 7 1 0 0 1 2 2 4 2 5 7 0 0 1 1 -1 5 2 1 4 3 7 2 0 1 0 0 5 2 1 4 3 7 -1 0 0 0 0 0 LR 型 (f)插入

44、 3 5 2 1 4 3 7 -2 -1 0 1 0 0 6 0 RL 型 0 6 2 1 4 3 7 0 0 0 0 0 5 0 (g) 插入 6 图 7-14 平衡二叉树的生成过程 例2：给定一个关键字序列13，24，37，90，53，试生成一棵平衡二叉树。作业作业：将一组关键字（47,16,21,36,29,59,19,54)生成一二叉平衡树。 3平衡二叉树的查找及性能分析平衡二叉树的查找及性能分析平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查找 性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度O(n)，它的时间复杂度与二叉排序树的最好时间复杂相

45、同，都为O(log2n)。一般二叉平衡树主要应用于查找。例3，对例1给定的关键字序列4,5,7,2,1,3,6，试用二叉排序树和平衡二叉树两种方法查找，给出查找6的次数及成功的平均查找长度。分析：由于关键字序列的顺序己经确定，故得到的二叉排序树和平衡二叉树都是唯一的。得到的平衡二叉树见图7-14，得到的二叉排序树见图7-15。 4 2 3 1 5 7 6 图 7-15 由 关 键 字 序 列 4,5,7,2,1 ,3,6 生 成 的二 叉 排 序 树 从图7-15的二叉排序树可知，查找6需4次，假设7个记录的查找概率相等，为1/7，则该二叉排序树的平均查找长度为 ASL=(1+2+2+3+3+

46、3+4)/7=18/72.57。从图7-16的平衡二叉树可知，查找6需2次，平均查找长度ASL=(1+2+2+3+3+3+3)/7=17/72.43。从结果可知，平衡二叉树的查找性能优于二叉排序树。 0 6 2 1 4 3 7 0 0 0 0 0 5 0 图 7-16 平衡二叉树 #includeh1.h#include#includebitree *creat(bitree *t) bitree *s,*p,*q; int x; printf(input the nodes value:0-ENDn); scanf(%d,&x); while(x!=0) s=(bitree *)malloc

47、(sizeof(bitree); s-data=x; s-lchild=s-rchild=NULL; if(t=NULL) t=s; else p=t; while(p) q=p; if(s-datadata) p=p-lchild; else p=p-rchild; if(s-datadata) q-lchild=s; else q-rchild=s; printf(input the nodes value:n); scanf(%d,&x); return(t); void preorder(bitree *root) if(root!=NULL) printf(%dn,root-data

48、); preorder(root-lchild); preorder (root-rchild);void main() bitree *p=NULL,*q; q=creat(p); printf(now output the trees preorder value:n); preorder(q);湖南大学01-03 1、树最合适用来表示_。A 有序数据元素 B 无序数据元素 C 元素之间无联系的数据 D元素之间分支层次关系的数据2、中序遍历二叉排序树就可以得到排好序的结点序列。（ ）（判断正误） 一维数组存放一棵完全二叉树:ABCDEFGHIJK，请给出该二叉树的后序遍历序列。算法设计题略

49、1、在二叉排序树上成功地找到一个结点，在平均情况下的时间复杂性是 , 在最坏情况下的时间复杂性是 。设结点个数为 n，以大O形式给出时间复杂性。2、已知一棵二叉树是以二叉链表的形式存储的，其结点结构说明如下：（本题10 分。） struct node int data; / 结点的数据场。 struct node *left; / 给出结点的左儿子的地址。 struct node * right; / 给出结点的右儿子的地址。 ； 请在1、2二题的 处进行填空，完成题目要求的功能。注意，每空只能填一个语句，多填为 0 分。(1) 求出以T 为根的二叉树或子树的结点个数。 int size (s

50、truct node * T ) if ( ) return 0; else ; ( 2) 求出以T为根的二叉树或子树的高度。注：高度定义为树的总的层次数。 int height(struct node * T ) if ( T = NULL ) ; else ; 上海交通大学上海交通大学2004年数据结构考研试题年数据结构考研试题 提示：用递归形式O(log2n) O(n) T = NULLreturn ( 1 +size(T-left) + size(T-right) )return 0return 1 +( ( height(T-left) height(T-right)? height

51、(T-left): height(T-right) )6.7线索二叉树线索二叉树6.7.1 线索的概念 遍历二叉树：遍历二叉树：就是将树中所有结点排成一个线性序列。好处：好处：在这样的线性序列中，很容易求得某个结点在某种遍历下的直接前驱和后继。 带来麻烦，希望不进行遍历就能快速找到快速找到某个结点在某种遍历下的直接前驱和后继，这样，就应该把每个结点的直接前驱和直接后继记录下来。 为了做到这一点，可以在原来的二叉链表结点中，再增加两个指针域，一个指向前驱，一个指向后继，但这样做将会浪费大量存贮单元，存贮空间的利用率相当低(一个结点中有4个指针，1个指左孩子，1个指右孩子，1个指前驱，1个指后继)

52、，而原来的左、右孩子域有许多空指针又没有利用起来。为了不浪费存贮空间，我们利用原有的孩子指针为空时来存放直接前驱和后继，这样的指针称为“线索”（thread)，加线索的过程称为线索化线索化，加了线索的二叉树，称为线索二叉树线索二叉树，对应的二叉链表称为线索二叉链表线索二叉链表（简称为线索链表）。 在线索二叉树中，由于有了线索，无需遍历二叉树就可以得到任一结点在某种遍历下的直接前驱和后继。 但是，我们怎样来区分孩子指针域中存放的是左、右孩子信息还是直接前驱或直接后继信息呢?为此，在二叉链表结点中，还必须增加两个标志域ltag、rtag。 ltag和rtag定义如下： 0 lchild域指向结点的

53、左孩子 ltag= 1 lchild域指向结点在某种遍历下的直 接前驱 0 rchild域指向结点的右孩子 rtag= 1 rchild域指向结点在某种遍历下的直接后继 这样，二叉链表中每个结点还是有5个域，但其中只有2个指针，较原来的4个指针要方便。增加线索后的二叉链表结点结构可描述如下： lchild ltag data rtag rchild 2线索的分类线索的分类另外，根据遍历的不同要求，线索二叉树可以分为：（1）前序前驱线索二叉树）前序前驱线索二叉树(只需画出前驱只需画出前驱)（2）前序后继线索二叉树）前序后继线索二叉树(只需画出后继只需画出后继)（3）前序线索二叉树）前序线索二叉树

54、(前驱和后继都要标出前驱和后继都要标出)（4）中序前驱线索二叉树）中序前驱线索二叉树(只需画出前驱只需画出前驱)（5）中序后继线索二叉树）中序后继线索二叉树(只需画出中序后继只需画出中序后继)（6）中序线索二叉树）中序线索二叉树(中序前驱和后继都要标出中序前驱和后继都要标出)（8）后序前驱线索二叉树）后序前驱线索二叉树(只需画出后序前驱只需画出后序前驱)（8）后序后继线索二叉树）后序后继线索二叉树(中需画出后序后驱中需画出后序后驱)（9）后序线索二叉树）后序线索二叉树(前驱和后继都要标出前驱和后继都要标出) 6.7.2线索的描述线索的描述1结点数据类型描述结点数据类型描述typedef str

55、uct bithrnode int data; int ltag ,rtag; /左、右标志域 struct bithrnode *lchild, *rchild; binode ; 2线索的画法线索的画法在二叉树或二叉链表中，若左孩子为空，则画出它的直接前驱，右孩子为空时，则画出它的直接后继，左右孩子不为空时，不需画前驱和后继。这样就得到了线索二叉树或线索二叉链表。前序序列为：ABCD A D C B 0 A 0 1 B 1 0 C 1 root 1 D 1 A D C B NULL (a) 二叉树 (b)前序线索二叉树 (c)前序线索二叉链表 图 7-17 前序线索示意图 A D C B

56、NULL NULL （a）中序线索二叉树 （b） 中序线索二叉链表 图 7-18 中序线索示意图 0 A 0 root 1 D 1 0 C 1 1 B 1 中序序列为：BADC C 0 A 0 1 B 1 0 C 1 1 D 1 root D B A NULL (a)后序线索二叉树 (b)后序线索二叉链表 图 7-19 后序线索示意图 后序序列为：BDCA仿线性表的存储结构，在二叉树的线索链表上添加一个头结点，其中lchild指向根结点，rchild指向自己，并且原先指向空的线索均指向该头结点。如此处理，使得在线索二叉树中查找某结点的前趋、后继结点的算法中不必再判断线索是否为空的情况。6.8

57、树和森林树和森林 6.8.1 树、森林和二叉树的转换树、森林和二叉树的转换1树转换成二叉树树转换成二叉树可以分为三步：（1） 连线指相邻兄弟之间连线，加一虚线。 （2） 抹线指抹掉双亲与除最左孩子外其它孩子之间的连线。 （3） 旋转只需将树作适当的旋转，具体：将图形上原有的实线均向左斜，加上的虚线均向右斜，且变成实线，调整成二叉树的树型结构。 具体实现过程见图7-20。 G F E D C B A A B E C D G F F G D C E B A 图 7-20 树转换成二叉树示意图 连线抹线 旋转 由转换可知：在二叉树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原来的

58、树中是兄弟关系。由于根结点没有兄弟，所以变换后的二叉树的根结点的右孩子必为空2森林转换成二叉树森林转换成二叉树（1） 将森林中每一棵树分别转换成二叉树将森林中每一棵树分别转换成二叉树这在刚才的树转换成二叉树中已经介绍过。这在刚才的树转换成二叉树中已经介绍过。 （2）合并）合并使第n棵树接入到第n-1棵的右边并成为它的右子树，第 n-1 棵二叉树接入到第n-2 棵的右边并成为它的右子树，第2棵二叉树接入到第1棵的右边并成为它的右子树，直到最后剩下一棵二叉树为止。 C D B A F E I A A A H G E F I H G G F E D C B A I H A D B C 图 7-21

59、森 林 转 换 成 二 叉 树 示 意 图 合 并 3二叉树还原成树二叉树还原成树与树转换成二叉树的步骤刚好相反：a. 加线：若某节点I是双亲节点的左孩子，则将该节点的右孩子及沿着此右孩子的右链不断搜索到的所有右孩子，都分别与节点I的双亲节点用虚线连接起来。b. 抹线：抹掉原二叉树中所有双亲节点与右孩子的连线。c. 旋转：将树中虚线均变为实线，并按层次排好。ABECDFABCDEF调整后ABCDEF4. 二叉树还原成森林二叉树还原成森林(1) 右链断开（即抹线）将二叉树的根结点的右链及右链的右链等全部断开，得到若干棵无右子树的二叉树。具体操作见图7-21(b)。（2） 二叉树还原成树 具体操作

60、步骤见图7-21(c)。 G D A B C E F H I J K (a)一个森林得到的二叉树 D A B C E G F H I J K (b)断开根的右链得到 4 棵无右子树的二叉树 C G F H I J K D A B E (c) 四棵二叉树还原成四棵树 H I J K G F C D A B E (d) 二叉树还原成森林 图 7-21 二叉树还原成森林过程 6.8.2 树和森林的遍历树和森林的遍历 在树和森林中，一个结点可能有两棵以上的子树，因而不便讨论它们的中序遍历。故树和森林的遍历通常有两种方式，先序遍历和后序遍历。下面分别讨论：（1）树的先序遍历）树的先序遍历若树非空，则先访