树和二叉树数据结构

1、第六章 树和二叉树一、树的基本概念1、树的定义：2、树的基本术语（1）节点的度和树的度（2）分支节点和叶节点（3）路径和路径长度（4）孩子节点、双亲结点和兄弟节点（5）节点的层次和树的高度（6）有序树和无序树（7）森林3、树的逻辑表示（1）树形表示法（2）文氏图表示法（3）凹入表示法（4）嵌套括号表示法4、树的性质（1）树中节点数等于所有节点的度加1。（2）度为m的树中第i层至多有mi-1个节点。（3）高度为h的m叉树至多有(mh-1)/(m-1)个节点。（4）具有n个节点的m叉树的最小高度为logm(n(m-1)+1)v性质1的证明：v证明：根据树的定义，在一棵树中，除树根结点外，每个结点有

2、且仅有一个前驱结点。也就是说，每个结点与指向它的一个分支一一对应，所以除树根之外的结点数等于所有结点的分支数(度数)，从而可得树中的结点数等于所有结点的度数加1。 v性质2证明（数学归纳法）： v（1）对于第一层，因为树中的第一层上只有一个结点，即整个树的根结点，而由i=l代入mi-1得mi-1 =1，也同样得到只有一个结点，显然结论成立。v（2）假设对于第(i-1)层(il)命题成立，即度为m的树中第(i-1)层上至多有mi-2结点，则根据树的度的定义，度为m的树中每个结点至多有m个孩子，所以第i层上的结点数至多为第(i-1)层上结点数的m倍，即至多为mi-2 *m= mi-1个，这与命题相

3、同，故命题成立。 v性质4的证明：5、树的基本运算 树的运算主要分为三大类：第一类：寻找满足某种特定关系的的节点，如寻找当前节点的双亲结点；第二类：插入和删除某个节点；第三类：遍历树中的每一个节点。 树的遍历算法：按某种方式访问树中每一个节点且每一个节点只被访问一次。 注意：树的先根和后根遍历算法是递归的。（1）先根遍历。例如：对前述图（a），先根遍历得到的节点序列为：ABEFCGJDHIKLM。（2）后根遍历。例如：对前述图（a），后根遍历得到的节点序列为：EFBJGCHKLMIDA6、树的存储结构 既要求存储节点的数据元素，又要存储节点之间的逻辑关系。常用的三种存储结构：（1）双亲存储结构

4、：需一伪指针指示双亲结点的位置。（2）孩子存储结构：按树的度设计节点的孩子节点的指针域的个数。（3）孩子兄弟存储结构：为每个节点设计三个域：数据元素域、该节点的第一个孩子域、该节点的下一个兄弟节点指针域。 由于树的孩子兄弟存储结构有两个指针域，并且这两个指针是有序的，所以孩子兄弟存储结构是把树转换为二叉树的存储结构。我们在后面将会讨论到，把树转换为二叉树所对应的结构恰好就是这种孩子兄弟存储结构。所以，孩子兄弟存储结构的最大优点是可方便地实现树和二叉树的相互转换。 孩子兄弟存储结构的缺点也和孩子表示法的缺点一样：就是从前结点查找双亲结点比较麻烦，需要从树的根结点开始逐个结点比较查找。 树的基础要

5、点1、树最适合表示元素之间具有分支层次关系的数据。2、一般树可以转换成二叉树是基于树的树形表示法。3、树在计算机内的存储方式有三种方法：双亲、孩子和孩子兄弟存储结构。4、利用树的孩子兄弟表示法，可以将一棵树转换为二叉树。5、高度为k的m（m=2）叉树至少有（ ）个节点，最多有（ ）个节点。6、在线性表、m叉树、栈和队列中，不可以利用顺序存储结构的是（ ）。7、高度为h的满m叉树的第k层有（ ）个节点。8、按后序遍历树或森林，等同于按（ ）遍历对应的二叉树。9、在树中，一个节点的直接孩子节点的个数称为该节点的度。10、一棵有n个节点的树，树中的所有节点的度之和为（ ）。11、节点最少的树为（ ）

6、，节点最少的二叉树为（ ）。【例1】含有n个节点和n个叶子节点的完全三叉树的高度各是多少？【例2】以孩子兄弟链表为存储结构，请设计递归和非递归算法求树的高度。二、二叉树的概念和性质1、二叉树的概念 二叉树是有限的结点的集合，此集合或者为空，或者是由一个根节点和两棵互不相交的称为左子树和右子树的二叉树组成。 特点：（1）每个节点至多有两个子树，任何结点的度数不能大于2。（2）二叉树的结点有严格的左右之分，其次序不能任意颠倒。 二叉树的表示方法：与树的表示方法一样，有：树形表示法、文氏图表示法、凹入表示法和嵌套括号表示法。 满二叉树的概念。 完全二叉树的概念。 满二叉树是完全二叉树的一种特例，并且

7、完全二叉树与同高度的满二叉树对应位置结点有同一编号。2、二叉树的性质（1）非空二叉树上叶节点数等于双分支节点数加1。（会证明）（2）非空二叉树上第i层上至多有2i-1个结点（i=1）。（3）高度为h的二叉树至多有2h-1个结点（h=1）。（4）对完全二叉树中编号为i的结点（1i n ,n1,n为结点数 ）有： 若2in,则编号为i的结点为分支节点，否则为叶子节点。 若n为奇数，则每个分支节点都既有左孩子，又有右孩子；若n为偶数，则编号最大的分支节点（编号为n/2）只有左孩子，没有右孩子，其余分支节点左、右孩子都有。 若编号为i的结点有左孩子，则左孩子结点的编号为2i；若编号为i的结点有右孩子，

8、则左孩子结点的编号为2i+1。 除根节点以外，若一个结点的编号为i，则其双亲结点的编号为i/2，即当i为偶数时，其双亲结点的编号为i/2，它是双亲结点的左孩子；当i为奇数时，其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子。 该性质可用数学归纳法来证明。（5）具有n个（n0）结点的完全二叉树的高度为log2n+1（取上整）或log2n+1（log2n取下整）。 注意：二叉树的上述性质是计算和证明二叉树中某类结点个数或高度的基础。【例3】对于任何非空二叉树，假设叶子结点的个数为n0，而度数为2的结点个数为n2，请给出和之间所满足的关系式n0=f(n2)。要求给出推导过程。3、二叉树、树、森

9、林之间的转换 可以把在树的处理中的问题对应到二叉树中进行处理。 转换时的约定：把一般的树作为有序树来处理。（1）森林、树转换为二叉树【例4】将下图所示的森林转换成二叉树表示。（2）二叉树还原为森林、树【例5】将下图所示的二叉树转换为一般的树。三、二叉树的存储结构1、二叉树的顺序存储结构 用一组地址连续的存储单元来存放二叉树的存储元素。 二叉树顺序存储结构中结点的存放次序：结点从小到大编号，编号顺序就是结点存放在连续存储单元的先后次序。 该存储结构对于完全二叉树来说是合适的，但对于一般的二叉树，特别是那些单分支的二叉树来说很不合适。 顺序存储结构的固有缺陷使得二叉树的插入、删除等运算十分不方便。

10、【例6】给出下图所示的二叉树的顺序存储结构。2、二叉树的链式存储结构（二叉链） 二叉树中，标准方式的节点结构如下：【例】给出如下图所示的二叉树的链式存储结构。四、二叉树的基本运算及其实现1、二叉树基本运算概述（1）创建二叉树：creatree(*b,*str)；（2）找结点：find(*b,x)；（3）找孩子结点：lchhild(p)和rchild(p)（4）求高度：treedepth(*b)（5）输出二叉树：disptree(*b)五、二叉树的遍历v二叉树的遍历二叉树的遍历是指按照一定次序访问树中所有结点，井且每个结点仅被访问一次的过程，它是最基本的运算，是二叉树中所有其他运算的基础。v六种

11、遍历方法先序遍历二叉树中序遍历二叉树后序遍历二叉树v二叉树遍历算法的实现二叉树的基础要点1、具有64个结点的完全二叉树的高度为（ ）。2、具有n个结点的互不相似的二叉树共有（ ）。3、高度为h的完全二叉树至少有（ ）个结点，至多有（ ）个结点。H与结点数n之间的关系是（ ）。4、具有n个结点的二叉树，采用二叉链表存储，共有（ ）个空链域。5、由二叉树的先序序列和后序序列不能唯一确定一棵二叉树。6、具有n个结点的完全二叉树是一棵路径长度最短的二叉树。7、对于先序序列和中序序列结果相同的二叉树为（ ）二叉树。对于中序序列和后序序列结果相同的二叉树为（ ）二叉树。对于先序序列和后序序列结果相同的二叉

12、树为（ ）二叉树。8、具有10个叶子结点的二叉树中有（）个度为2的结点。9、设只包含根节点的二叉树的高度为0，则高度为k的二叉树的最大节点数是（ ），最小节点数为（ ）。10、具有n个叶子节点的完全二叉树的高度为（ ）。具有n个结点的完全二叉树的高度为（ ）。11、某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则该二叉树结点的先序序列是（ ）。该二叉树对应的森林包括（ ）棵树。12、下列叙述中正确的是：（1）在二叉树中，任何一个结点的度都为2；（2）二叉树的度为2；（3）在二叉树中至少有一个结点的度为2。（4）一棵二叉树的度可以小于2。13、树的基本遍历策略可分为先根和后根

13、遍历；二叉树的遍历策略可分为先序、中序和后序遍历。这里，把由树转化得到的二叉树叫做该树对应的二叉树，则在以下叙述中，正确的是：（1）树的先根遍历序列与其对应的二叉树的先序遍历序列相同。（2）树的后根遍历序列与其对应的二叉树的后序遍历序列相同。（3）树的后根遍历序列与其对应的二叉树的中序遍历序列相同。（4）树的先根遍历序列与其对应的二叉树的中序遍历序列相同。14、一棵非空二叉树的中序序列中，根节点的右边只有右子树的所有节点。15、一棵满二叉树共有n个结点，其中有m个叶子结点，m和n的关系是（ ）。16、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1，m2和m3，则森林F对应的二叉树

14、根节点的右子树上的结点个数为（ ） 。17、二叉树的先序序列中，任意一个结点均在其孩子节点的前面。18、若一棵二叉树中只有叶子结点和左右子树皆非空的结点，设叶子结点的个数为k，则左右子树皆非空的结点个数是k-1。19、对于一个具有n个结点的二叉树，当它为一棵（ ）时，具有最小高度；当它为（ ）具有最大高度，即为n。20、从概念上来讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是树可以采用二叉树的存储结构并利用二叉树已有的算法来解决树的有关问题。【例8】设计二叉树先序遍历的非递归算法。 使用一个栈保存二叉树中结点的指针。有两种实现二叉树先序遍历的非递归算法。六、线索化二叉树v概念

15、：线索、线索二叉树、【例9】给出下图所示的二叉树的先序、中序和后序线索二叉树。v对同一棵二叉树的遍历方式不同，所得到的线索树也不同，二叉树有先序、中序和后序三种遍历方式，所以线索树也有先序线索二叉树、中序线索二叉树和后序线索二叉树三种。v以中序线索二叉树为例，讨论建立线索二叉树的算法。 v建立线索二叉树，或者说，对二叉树线索化，实质上就是遍历一棵二叉树，在遍历的过程中，检查当时结点的左、右指计域是否为空。如果为空，将它们改为指向前驱结点或后继结点的线索。另外，在对一棵二叉树加线索时，必须首先创建一个头结点，建立头结点与二叉树的根结点的线索。对二叉树线索化后，还须建立最后一个结点与头结点之间的线

16、索。v为了实现线索化二叉树，将前面二叉树结点的类型定义修改如下 ：typedef struct node ElemType data; int Itag, rtag; /增加的线索标记 struct node *lchiid; struct node *rchild;)BTree; 线索二叉树基础要点1、线索二叉树的左线索指向其前驱结点，右线索指向其后继结点。2、后序线索树的遍历仍需要栈的支持。3、二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索。（对/错）4、在线索化二叉树中，结点*t没有左子树的充分条件是：（ ）。【例10】设计一个算法在中序线索二叉树上寻找一个结点的前驱结点。

17、七、哈夫曼树1、路径长度及哈夫曼树 结点的权 结点的带权路径的长度 树的带权路径长度 哈夫曼树（最优二叉树）v在许多应用中，常常将树中的结点赋上一个有着某种意义的实数，称此实数为该结点的权。v从树根结点到该结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度。v树中所有叶子结点的带权路径长度之和称为该树的带权路径长度，通常记为： 其中，n表示叶子结点的数目，Wi和分别表示叶子结点ki的权值和根到ki之间的路径长度。v在n个带权叶子结点构成的所有二叉树中,带权路径长度WPL最小的二叉树称为哈夫曼树(或最优二叉树因为构造这种树的算法是最早由哈夫曼于1952年提出的，所以被称为哈夫曼树（最优二

18、叉树）。【例】给定4个叶子结点，设其权值分别为1，3，5，7，可构造出形状不同的4棵二叉树：2、哈夫曼树的构造方法哈夫曼算法：哈夫曼算法：3、哈夫曼编码v在数据通信中，经常需要将传送的文字转换为二进制字符0和1组成的二进制字符串，我们称这个过程为编码。显然，希望电文编码的代码长度最短。哈夫曼树可用于构造使电文编码的代码长度最短的编码方案。v具体构造方法如下：设需要编码的字符集合为d0,d1,dn-1,各个字符在电文中出现的次数集合为W0,W1,Wn-l，以d0,d1,dn-1作为叶结点，以w0, W0,W1,Wn-l作为各根结点到每个叶结点的权值构造一棵二叉树，规定哈夫曼树中的左分支为0，右分

19、支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的编码称为哈夫曼编码。 v实质：就是利用使用频率越高的采用越短的编码。哈夫曼树的基础要点1、求具有最小带权外部路径的扩充二叉树的算法成为哈夫曼算法。对于给定的一组权w=10,12,16,21,30，通过该算法求出扩充二叉树的带权外部路径长度为（ ）。2、在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。（对/错）【例11】假定用于通讯的电文仅有a，b，c，d，e，f，g，h8个字母组成，字母在电文中出现的频率为：0.07,0.19,0,02,0.06,0.32,0.03,0.21和0.1

20、0。试为这些字母设计哈夫曼编码。练习1、一棵左、右子树均不空的二叉树在先序线索化后，其空指针域是多少？2、有n个结点并且高度为n的二叉树的数目是多少？3、已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点个数最多是多少？4、一棵二叉树的先序、中序和后序序列分别如下，其中一部分未显示出来。试求出空格处的内容，并画出该二叉树。先序序列：（）B（）F（）ICEH（）G中序序列：D（）KFIA（）EJC（）后序序列：（）K（）FBHJ（）G（）A5.对于如图所示的二叉树：(1)请画出它的顺序存储结构图；(2)请将它转换成森林。 6.设F=T1,T2,T3是森林，试画出所对应的二叉树，森林如下图所示。 7.如果一棵哈夫曼树T有n0个叶子结点，那么，树T有多少个结点，要求给出求解过程。8.下表所列的数据表给出了在一篇有19710个词的英文文章中出现最普通的15个单词的出现频度。假定一篇正文仅由上述字符数据表中的词组成，那么它们的最佳编码是什么？平均长度是多少? v9.用一维数组存放一棵完全二叉树：ABCDEFGHIJKL。请写出后序遍