第7章树形结构

1、第第7章章 树和二叉树树和二叉树7.1 树的基本概念树的基本概念 7.2 二叉树概念和性质二叉树概念和性质7.3 二叉树存储结构二叉树存储结构7.4 二叉树的遍历二叉树的遍历7.5 二叉树的基本运算及其实现二叉树的基本运算及其实现7.6 二叉树的构造二叉树的构造7.8 哈夫曼树哈夫曼树 7.7 线索二叉树线索二叉树本章小结本章小结7.1.1 树的定义树的定义 形式化定义：形式化定义： 树：树：T=D,R。D是包含是包含n个节点的有穷集合（个节点的有穷集合（n0）。）。当当n=0时为空树，否则关系时为空树，否则关系R满足以下条件满足以下条件: l 有且仅有一个节点有且仅有一个节点d0D，它对于关

2、系，它对于关系R来说没来说没有前驱节点，节点有前驱节点，节点d0称作树的称作树的根节点根节点。l 除节点除节点d0外，外，D中的每个节点对于关系中的每个节点对于关系R来说都来说都有且有且仅有一个前驱节点仅有一个前驱节点。l D中每个节点对于关系中每个节点对于关系R来说可以有来说可以有零个或多个零个或多个后继节点后继节点。7.1 树的基本概念树的基本概念 递归定义：递归定义： 树树是由是由n（n0）个节点组成的有限集合（记为）个节点组成的有限集合（记为T）。其中：）。其中： l 如果如果n=0，它是一棵空树，这是树的特例；，它是一棵空树，这是树的特例；l 如果如果n0，这，这n个节点中存在（有仅

3、存在）一个节点个节点中存在（有仅存在）一个节点作为树的根节点，简称为根节点（作为树的根节点，简称为根节点（root），其余节点），其余节点可分为可分为m （m0）个互不相交的有限集）个互不相交的有限集T1,T2,Tm,其其中每一棵子集本身又是一棵符合本定义的中每一棵子集本身又是一棵符合本定义的树树，称为，称为根根root的子树。的子树。rootT1T2Tm7.1.2 树的表示树的表示 （1）树形表示法。）树形表示法。这是树的最基本的表示，使用一棵倒这是树的最基本的表示，使用一棵倒置的树表示树结构，非常直观和形象。下图就是采用这种表置的树表示树结构，非常直观和形象。下图就是采用这种表示法。示法。

4、ABCDEFGJHIKLM逻辑结构表示逻辑结构表示1 （2）文氏图表示法。）文氏图表示法。使用集合以及集合的包含关系描述树结使用集合以及集合的包含关系描述树结构。下图就是树的文氏图表示法。构。下图就是树的文氏图表示法。ABCDEFGJHIKLM逻辑结构表示逻辑结构表示2AEFBCGJHDKLMI （3）凹入表示法。）凹入表示法。使用线段的伸缩描述树结构。下使用线段的伸缩描述树结构。下图是树的凹入表示法。图是树的凹入表示法。逻辑结构表示逻辑结构表示3ABCDEFGJHIKLM（4）括号表示法。）括号表示法。将树的根节点写在括号的左边，除将树的根节点写在括号的左边，除根节点之外的其余节点写在括号中

5、并用逗号间隔来描述根节点之外的其余节点写在括号中并用逗号间隔来描述树结构。下图是树的括号表示法。树结构。下图是树的括号表示法。 括括号号表表示示法法 A(B(E,F),C(G(J),D(H,I(K,L,M) ABCDEFGJHIKLM思考题：思考题：树的逻辑结构定义？适合表示什么类型的数据？树的逻辑结构定义？适合表示什么类型的数据？7.1.3 树的基本术语树的基本术语 1. 节点的度与树的度：节点的度与树的度：树中某树中某个节点的子树的个数称为该节点的个节点的子树的个数称为该节点的度。树中各节点的度的最大值称为度。树中各节点的度的最大值称为树的度，通常将度为树的度，通常将度为m的树称为的树称为

6、m次树次树。 2. 分支节点与叶节点：分支节点与叶节点：度不为零的节点称为非终端节点度不为零的节点称为非终端节点,又叫分支节点。度为零的节点称为终端节点或叶节点。在分又叫分支节点。度为零的节点称为终端节点或叶节点。在分支节点中，每个节点的分支数就是该节点的度。如对于度为支节点中，每个节点的分支数就是该节点的度。如对于度为1的节点的节点,其分支数为其分支数为1，被称为单分支节点；对于度为，被称为单分支节点；对于度为2的节的节点，其分支数为点，其分支数为2，被称为双分支节点，其余类推。，被称为双分支节点，其余类推。ABCDEFGJHIKLM度为度为3度为度为2 3. 路径与路径长度：路径与路径长度

7、：对于任意对于任意两个节点两个节点di和和dj，若树中存在一个节，若树中存在一个节点序列点序列di,di1,di2,din,dj，使得序列中，使得序列中除除di外的任一节点都是其在序列中的外的任一节点都是其在序列中的前一个节点的后继，则称该节点序前一个节点的后继，则称该节点序列为由列为由di到到dj的一条路径，用路径所的一条路径，用路径所通过的节点序列通过的节点序列(di,di1,di2,dj)表示表示这条路径这条路径。 路径长度路径长度等于路径所通过的节点等于路径所通过的节点数目减数目减1（即路径上分支数目）。（即路径上分支数目）。ABCDEFGJHIKLMA到到K的路径为的路径为A,D,I

8、,K，其长度为其长度为3 4. 孩子节点、双亲节点和兄弟节孩子节点、双亲节点和兄弟节点：点：在一棵树中，每个节点的后继，在一棵树中，每个节点的后继，被称作该节点的孩子节点（或子女节被称作该节点的孩子节点（或子女节点）。相应地，该节点被称作孩子节点）。相应地，该节点被称作孩子节点的点的双亲节点双亲节点（或父母节点）。（或父母节点）。 具有同一双亲的孩子节点互为兄弟具有同一双亲的孩子节点互为兄弟节点。进一步推广这些关系，可以把节点。进一步推广这些关系，可以把每个节点的所有子树中的节点称为该每个节点的所有子树中的节点称为该节点的节点的子孙节点子孙节点。从树根节点到达该节点的路径上经从树根节点到达该节

9、点的路径上经过的所有节点被称作该节点的过的所有节点被称作该节点的祖先节祖先节点点。ABCDEFGJHIKLM 5. 节点的层次和树的高度：节点的层次和树的高度：树树中的每个节点都处在一定的层次上。中的每个节点都处在一定的层次上。节点的层次从树根开始定义，根节节点的层次从树根开始定义，根节点为第点为第1层，它的孩子节点为第层，它的孩子节点为第2层层,以此类推以此类推,一个节点所在的层次为一个节点所在的层次为其双亲节点所在的层次加其双亲节点所在的层次加1。树中。树中节点的最大层次称为树的节点的最大层次称为树的高度高度（或（或树的树的深度深度）。）。 6. 有序树和无序树：有序树和无序树：若树中各若

10、树中各节点的子树是按照一定的次序从左节点的子树是按照一定的次序从左向右安排的，且相对次序是不能随向右安排的，且相对次序是不能随意变换的，则称为意变换的，则称为有序树，有序树，否则称否则称为为无序树无序树。ABCDEFGJHIKLM1234 7. 森林：森林：n（n0）个互不相交的树的集合称为森）个互不相交的树的集合称为森林。森林的概念与树的概念十分相近，因为只要把树的林。森林的概念与树的概念十分相近，因为只要把树的根节点删去就成了森林。反之，只要给根节点删去就成了森林。反之，只要给n棵独立的树加棵独立的树加上一个节点，并把这上一个节点，并把这n棵树作为该节点的子树，则森林棵树作为该节点的子树，

11、则森林就变成了树。就变成了树。7.1.4 树的性质树的性质性质性质1 树中的节点数等于所有节点树中的节点数等于所有节点的度数加的度数加1。 证明：证明：根据树的定义，在一棵树中，根据树的定义，在一棵树中，除树根节点外，每个节点有且仅有一除树根节点外，每个节点有且仅有一个前驱节点。也就是说，每个节点与个前驱节点。也就是说，每个节点与指向它的一个分支一一对应，所以除指向它的一个分支一一对应，所以除树根之外的节点数等于所有节点的分树根之外的节点数等于所有节点的分支数（度数），从而可得树中的节点支数（度数），从而可得树中的节点数等于所有节点的度数加数等于所有节点的度数加1。度之和分支数度之和分支数分支

12、数分支数=n-1所以，所以，n=度之和度之和+1ABCDEFGJHIKLM求解树的节点个数问题求解树的节点个数问题：对于度为：对于度为m的树，在的树，在n、n0、n1、n2、nm中只有两个参数未知时，一般可求出这两个值。中只有两个参数未知时，一般可求出这两个值。例如求例如求n和和n0的求解过程如下：的求解过程如下：n=n0+n1+nm度之和度之和=n1度之和度之和=n1+2n2+mnm所以有：所以有：nn1+2n2+mnm+1=n0+n1+nm这样：这样：n0=n2+(m1)nm+1求解方法归纳求解方法归纳 例：一棵度为例：一棵度为4的树的树T中，若有中，若有20个度为个度为4的节点，的节点，

13、10个个度为度为3的节点，的节点，1个度为个度为2的节点，的节点，10个度为个度为1的节点，则树的节点，则树T的叶子节点个数是的叶子节点个数是 。 A.41B.82 C.113D.122注：本题为注：本题为2010年全国考研题年全国考研题 性质性质2 度为度为m的树中第的树中第i层上至多有层上至多有mi-1个节点，这里应有个节点，这里应有i1。 证明（采用数学归纳法）证明（采用数学归纳法） 对于第一层对于第一层,因为树中的第一层上只有一个节点，即整个树的因为树中的第一层上只有一个节点，即整个树的根节点根节点,而由而由i=1代入代入mi-1，得，得mi-1=m1-1=1，也同样得到只有一个，也同

14、样得到只有一个节点，显然结论成立。节点，显然结论成立。 假设对于第假设对于第(i-1)层（层（i1）命题成立，即度为）命题成立，即度为m的树中第的树中第(i-1)层上至多有层上至多有mi-2个节点。个节点。 则根据树的度的定义，度为则根据树的度的定义，度为m的树中每个节点至多有的树中每个节点至多有m个孩个孩子节点，所以第子节点，所以第i层上的节点数至多为第层上的节点数至多为第(i-1)层上节点数的层上节点数的m倍，倍，即至多为即至多为mi-2m=mi-1个，这与命题相同，故命题成立。个，这与命题相同，故命题成立。 性质性质3 高度为高度为h的的m次树至多有次树至多有 个节点。个节点。 证明：证

15、明：由树的性质由树的性质2可知可知,第第i层上最多节点数为层上最多节点数为mi - 1（i=1,2,h），显然当高度为），显然当高度为h的的m次树（即度为次树（即度为m的树）上的树）上每一层都达到最多节点数时，整个每一层都达到最多节点数时，整个m次树具有最多节点数，因次树具有最多节点数，因此有：此有：整 个 树 的 最 多 节 点 数整 个 树 的 最 多 节 点 数 = 每 一 层 最 多 节 点 数 之 和每 一 层 最 多 节 点 数 之 和=m0+m1+m2+mh-1 = 。11 mmh11 mmh 性质性质4 具有具有n个节点的个节点的m次树的最小高度为次树的最小高度为 logm(n

16、(m-1)+1) 。 证明：证明：设具有设具有n个节点的个节点的m次树的高度为次树的高度为h，若在该树中前，若在该树中前h-1层都是满的，即每一层的节点数都等于层都是满的，即每一层的节点数都等于mi-1个（个（1ih-1），第），第h层（即最后一层）的节点数可能满，也可能不满，则该树具层（即最后一层）的节点数可能满，也可能不满，则该树具有最小的高度。其高度有最小的高度。其高度h可计算如下：可计算如下：m=3，h=3，最多节点情况，最多节点情况m=3，h=3，最少节点情况，最少节点情况根据树的性质根据树的性质3可得：可得： n乘乘(m-1)后得：后得： mh-1n(m-1)+1mh以以m为底取对

17、数后得：为底取对数后得：h-1logm(n(m-1)+1)h即即logm(n(m-1)+1)hlogm(n(m-1)+1)+1因因h只能取整数，所以只能取整数，所以 h= logm(n(m-1)+1) 结论得证。结论得证。111 mmh11 mmh 例例7.1 含含n个节点的三次树的最小高度是多少？最大高个节点的三次树的最小高度是多少？最大高度是多少？度是多少？ 解：解：设含设含n个节点的（为完全三次树时高度最小）的个节点的（为完全三次树时高度最小）的三次树的最小高度为三次树的最小高度为h，则有：，则有： 1+3+9+3h-2n1+3+9+3h-1 (3h-1-1)/2 n (3h-1)/2

18、3h-12n+13h 即：即：h= log3(2n+1) 最大高度为最大高度为n-2。7.1.5 树的基本运算树的基本运算 树的运算主要分为三大类：树的运算主要分为三大类： 第一类，寻找满足某种特定关系的节点，如寻找当前第一类，寻找满足某种特定关系的节点，如寻找当前节点的双亲节点等；节点的双亲节点等； 第二类，插入或删除某个节点，如在树的当前节点上第二类，插入或删除某个节点，如在树的当前节点上插入一个新节点或删除当前节点的第插入一个新节点或删除当前节点的第i个孩子节点等；个孩子节点等； 第三类，遍历树中每个节点，这里着重介绍。第三类，遍历树中每个节点，这里着重介绍。 树的遍历运算是指按某种方式

19、访问树中的树的遍历运算是指按某种方式访问树中的每一个节点且每每一个节点且每一个节点只被访问一次一个节点只被访问一次。 有以下三种遍历方法：有以下三种遍历方法：树的遍历树的遍历 先根遍历先根遍历 后根遍历后根遍历 层次遍历层次遍历注意：先根和后根遍历算法都是递归的。注意：先根和后根遍历算法都是递归的。先根遍历先根遍历: 若树不空，则先访问根节点，然后依次先根遍历各棵子树。若树不空，则先访问根节点，然后依次先根遍历各棵子树。后根遍历后根遍历: 若树不空，则先依次后根遍历各棵子树，然后访问根节点。若树不空，则先依次后根遍历各棵子树，然后访问根节点。按层次遍历按层次遍历: 若树不空，则自上而下自左至右

20、访问树中每个节点。若树不空，则自上而下自左至右访问树中每个节点。ABCDEFGHJIK 先根遍历的顶点访问次序：先根遍历的顶点访问次序：A B E F C D G H I J K 后根遍历的顶点访问次序：后根遍历的顶点访问次序：E F B C I J K H G D A 层次遍历的顶点访问次序：层次遍历的顶点访问次序：A B C D E F G H I J K7.1.6 树的存储结构树的存储结构1. 1. 双亲存储结构双亲存储结构 这种存储结构是一种顺序存储结构，用一组连续空间这种存储结构是一种顺序存储结构，用一组连续空间存储树的所有节点，同时在每个节点中附设一个存储树的所有节点，同时在每个节

21、点中附设一个伪指针伪指针指指示其双亲节点的位置。示其双亲节点的位置。 A D B C G E F A -1 B 0 C 0 D 0 E 2 F 2 G 2 0 1 2 3 4 5 6 (a) (b) 树的双亲存储结构示意图树的双亲存储结构示意图双亲存储结构的类型声明如下：双亲存储结构的类型声明如下：typedef struct ElemType data; /节点的值节点的值 int parent;/指向双亲的位置指向双亲的位置 PTreeMaxSize;思考题：思考题：该存储结构的优缺点？该存储结构的优缺点？ A D B C G E F A -1 B 0 C 0 D 0 E 2 F 2 G

22、2 0 1 2 3 4 5 6 (a) (b) 2. 孩子链存储结构孩子链存储结构 孩子链存储结构可按树的度（即树中所有节点度的最大值）孩子链存储结构可按树的度（即树中所有节点度的最大值）设计节点的孩子节点指针域个数。以下左图的树对应的孩子链设计节点的孩子节点指针域个数。以下左图的树对应的孩子链存储结构如右图所示。存储结构如右图所示。树的树的孩子链孩子链存储结构示意图存储结构示意图孩子链存储结构的节点类型声明如下：孩子链存储结构的节点类型声明如下：typedef struct node ElemType data; /节点的值节点的值 struct node *sonsMaxSons;/指向孩

23、子节点指向孩子节点 TSonNode;其中，其中，MaxSons为最多的孩子节点个数。为最多的孩子节点个数。思考题思考题：n个节点的个节点的m次树有多少个空指针域？次树有多少个空指针域？思考题思考题：该存储结构的优缺点？：该存储结构的优缺点？3. 孩子兄弟链存储结构孩子兄弟链存储结构 孩子兄弟链存储结构是为每个节点设计三个域：一个数孩子兄弟链存储结构是为每个节点设计三个域：一个数据元素域，一个该节点的第一个孩子节点指针域，一个该据元素域，一个该节点的第一个孩子节点指针域，一个该节点的下一个兄弟节点指针域。节点的下一个兄弟节点指针域。树的树的孩子兄弟链孩子兄弟链存储结构示意图存储结构示意图兄弟链

24、存储结构中节点的类型声明如下：兄弟链存储结构中节点的类型声明如下：typedef struct tnode ElemType data;/节点的值节点的值 struct tnode *hp; /指向兄弟指向兄弟 struct tnode *vp; /指向孩子节点指向孩子节点 TSBNode;每个节点固定只有两个指针域。每个节点固定只有两个指针域。思考题思考题：该存储结构的优缺点？：该存储结构的优缺点？7.2.1 二叉树概念二叉树概念 二叉树是有限的节点集合。二叉树是有限的节点集合。 这个集合或者是空。这个集合或者是空。 或者由一个根节点和两棵互不相交的称为左子树和右或者由一个根节点和两棵互不相

25、交的称为左子树和右子树的二叉树组成。子树的二叉树组成。 注意：二叉树的定义是一种递归定义。注意：二叉树的定义是一种递归定义。7.2 二叉树概念和性质二叉树概念和性质 二叉树的五种基本形态：二叉树的五种基本形态：空树空树N只含根节点只含根节点L右子树为空树右子树为空树NL左右子树均左右子树均不为空树不为空树N左子树为空树左子树为空树NRR 二叉树是可以采用树的逻辑结构表示法，其四种表示二叉树是可以采用树的逻辑结构表示法，其四种表示法如下：法如下： 树形表示法树形表示法 文氏图表示法文氏图表示法 凹入表示法凹入表示法 括号表示法括号表示法 在一棵二叉树中在一棵二叉树中,如果如果所有分支节点都有左孩

26、子节点和右孩所有分支节点都有左孩子节点和右孩子节点，子节点，并且并且叶节点都集中在二叉树的最下一层，叶节点都集中在二叉树的最下一层，这样的二叉这样的二叉树称为树称为满二叉树满二叉树。下图所示就是一棵满二叉树。可以对满二叉树的节点进行下图所示就是一棵满二叉树。可以对满二叉树的节点进行连续编号，约定编号从树根为连续编号，约定编号从树根为1开始，按照层数从小到大、同开始，按照层数从小到大、同一层从左到右的次序进行。图中每个节点外边的数字为对该节一层从左到右的次序进行。图中每个节点外边的数字为对该节点的编号。点的编号。 A B C D E H I J K F G L M N O 1 2 3 4 5 6

27、 7 8 9 10 15 11 12 13 14 满二叉树满二叉树 若二叉树中最多若二叉树中最多只有最下面两层的节点的度数可以小于只有最下面两层的节点的度数可以小于2，并且并且最下面一层的叶节点都依次排列在该层最左边的位置上，最下面一层的叶节点都依次排列在该层最左边的位置上，则这样的二叉树称为则这样的二叉树称为完全二叉树完全二叉树。如下图所示为一棵完全二叉树。同样可以对完全二叉树中每如下图所示为一棵完全二叉树。同样可以对完全二叉树中每个节点进行连续编号，编号的方法同满二叉树相同。图中每个个节点进行连续编号，编号的方法同满二叉树相同。图中每个节点外边的数字为对该节点的编号。节点外边的数字为对该节

28、点的编号。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉树完全二叉树 7.2.2 二叉树性质二叉树性质 性质性质1 非空二叉树上叶节点数等于双分支节点数加非空二叉树上叶节点数等于双分支节点数加1。 证明：证明：设二叉树上叶节点数为设二叉树上叶节点数为n0，单分支节点数为，单分支节点数为n1，双分，双分支节点数为支节点数为n2，则总节点数，则总节点数n=n0+n1+n2。在一棵二叉树中，所。在一棵二叉树中，所有节点的分支数（即度数）应等于单分支节点数加上双分支节有节点的分支数（即度数）应等于单分支节点数加上双分支节点数的点数的2倍，即总的分

29、支数倍，即总的分支数=n1+2n2。 由于二叉树中除根节点以外，每个节点都有唯一的一个分支由于二叉树中除根节点以外，每个节点都有唯一的一个分支指向它，因此二叉树中有：总的分支数指向它，因此二叉树中有：总的分支数=总节点数总节点数-1。 由上述三个等式可得：由上述三个等式可得：n1+2n2=n0+n1+n2-1即：即：n0=n2+1求解二叉树的节点个数问题：求解二叉树的节点个数问题：通常利用二叉树的性质通常利用二叉树的性质1，即，即n0=n2+1来求解这类问题，也常利用以下关系求解：来求解这类问题，也常利用以下关系求解： n=n0+n1+n2 度之和度之和=n-1 度之和度之和=n1+2n2所以

30、有：所以有： n=n1+2n2求解方法归纳求解方法归纳 求解完全二叉树的节点个数问题求解完全二叉树的节点个数问题：完全二叉树属于二叉：完全二叉树属于二叉树，也满足二叉树的性质树，也满足二叉树的性质1，即，即n0=n2+1。 除此之外，完全二叉树中一旦除此之外，完全二叉树中一旦n确定，其树形就确定了，确定，其树形就确定了，可以计算出高度可以计算出高度h以及以及n0、n1和和n2。其中。其中n1=0或或1，当，当n为偶数为偶数时，时，n1=1，当，当n为奇数时，为奇数时，n1=0。其关系有：。其关系有： h= log2n +1或或h= log2(n+1) 求解方法归纳求解方法归纳例例7.2 已知一

31、棵完全二叉树的第已知一棵完全二叉树的第6层（设根为第层（设根为第1层）有层）有8个叶节点，则该完全二叉树的节点个数最多是个叶节点，则该完全二叉树的节点个数最多是 。A.39B.52C.111D.119注：本题为注：本题为2009年全国考研题年全国考研题求解满二叉树的节点个数问题：求解满二叉树的节点个数问题：满二叉树是最严格的二叉满二叉树是最严格的二叉树，一旦树，一旦n确定，其树形就确定了，可以计算出高度确定，其树形就确定了，可以计算出高度h以及以及n0、n1和和n2。其关系有：。其关系有：h=log2(n+1)n1=0n=2h-1n0=2h-1n2=2h-1-1求解方法归纳求解方法归纳例：一棵

32、满二叉树中共有例：一棵满二叉树中共有n个节点，其中有个节点，其中有m个叶子节点，个叶子节点，高度为高度为h，则，则 。A. n=h+mB. h+m=2nC. m=h-1D. n=2h-1 性质性质2 非空二叉树上第非空二叉树上第i层上至多有层上至多有2i-1个节点，这里应有个节点，这里应有i1。 由树的性质由树的性质2可推出。可推出。 性质性质3 高度为高度为h的二叉树至多有的二叉树至多有2h-1个节点（个节点（h1）。）。 由树的性质由树的性质3可推出。可推出。 性质性质4 对完全二叉树中编号为对完全二叉树中编号为i的节点（的节点（1in，n1，n为节点数）有：为节点数）有： （1）若）若i

33、 n/2 ，即即2in，则编号为，则编号为i的节点为分支节点，的节点为分支节点，否则为叶子节点。否则为叶子节点。 （2）若）若n为奇数，则每个分支节点都既有左孩子节点，为奇数，则每个分支节点都既有左孩子节点，也有右孩子节点；若也有右孩子节点；若n为偶数，则编号最大的分支节点只有为偶数，则编号最大的分支节点只有左孩子节点，没有右孩子节点，其余分支节点都有左、右孩左孩子节点，没有右孩子节点，其余分支节点都有左、右孩子节点。子节点。i/2i2i2i+1 （3）若编号为）若编号为i的节点有左孩子节点，则左孩子节点的编的节点有左孩子节点，则左孩子节点的编号为号为2i；若编号为；若编号为i的节点有右孩子节

34、点，则右孩子节点的编的节点有右孩子节点，则右孩子节点的编号为号为(2i+1)。 （4）除树根节点外）除树根节点外,若一个节点的编号为若一个节点的编号为i，则它的双亲，则它的双亲节点的编号为节点的编号为 i/2 ，也就是说，当，也就是说，当i为偶数时，其双亲节点的为偶数时，其双亲节点的编号为编号为i/2,它是双亲节点的左孩子节点，当它是双亲节点的左孩子节点，当i为奇数时，其双为奇数时，其双亲节点的编号为亲节点的编号为(i-1)/2，它是双亲节点的右孩子节点。，它是双亲节点的右孩子节点。思考题：思考题：性质性质4的特点？的特点？ 性质性质5 具有具有n个（个（n0）节点的完全二叉树的高度为）节点的

35、完全二叉树的高度为 log2n+1 或或 log2n +1。 由完全二叉树的定义和树的性质由完全二叉树的定义和树的性质3可推出。可推出。7.2.3 二叉树与树、森林之间的转换二叉树与树、森林之间的转换1森林、树转换为二叉树森林、树转换为二叉树 步骤如下：步骤如下： （1）在所有相邻兄弟节点（森林中每棵树的根节点可看）在所有相邻兄弟节点（森林中每棵树的根节点可看成是兄弟节点）之间加一水平连线。成是兄弟节点）之间加一水平连线。 （2）对每个非叶节点）对每个非叶节点k,除了其最左边的孩子节点外，删去除了其最左边的孩子节点外，删去k与其他孩子节点的连线。与其他孩子节点的连线。 （3）所有水平线段以左边

36、节点为轴心顺时针旋转）所有水平线段以左边节点为轴心顺时针旋转45度。度。 通过以上步骤，原来的森林就转换为一棵二叉树。通过以上步骤，原来的森林就转换为一棵二叉树。 一般的树是森林中的特殊情况，由一般的树转换的二叉树一般的树是森林中的特殊情况，由一般的树转换的二叉树的根节点的右孩子节点始终为空，原因是一般的树的根节点的根节点的右孩子节点始终为空，原因是一般的树的根节点不存在兄弟节点和相邻的树。不存在兄弟节点和相邻的树。ABCDEFGHII将森林转换为二叉树的过程将森林转换为二叉树的过程2. 二叉树还原为森林、树二叉树还原为森林、树 步骤如下：步骤如下： （1）对于一棵二叉树中任一节点）对于一棵二

37、叉树中任一节点k0，沿着，沿着k0的左孩子的左孩子节点节点k1的右子树方向搜索所有右孩子节点，即搜索节点序的右子树方向搜索所有右孩子节点，即搜索节点序列列k2,k3,km，其中，其中ki+1为为ki的右孩子节点（的右孩子节点（1im），），km没有右孩子节点。没有右孩子节点。 （2）删去）删去k1,k2,km之间连线。之间连线。 （3）若）若k1有双亲节点有双亲节点k0，则连接，则连接k0与与ki（2im）。）。 （4）将图形规整化，使各节点按层次排列）将图形规整化，使各节点按层次排列。 A D H B F C G E A B D C F E H G (a) (c) A B D C F E H

38、 G (b) 将一棵二叉树还原为树的过程将一棵二叉树还原为树的过程 例例7.3 设森林设森林F中有中有3棵树，第一、第二和第三棵树的节棵树，第一、第二和第三棵树的节点个数分别为点个数分别为9、8和和7，则与森林，则与森林F对应的二叉树根节点的右对应的二叉树根节点的右子树上的节点个数是子树上的节点个数是 。A. 16B. 15C. 7D. 17 例例7.4 设一棵二叉树是由森林转换而来的，若森林中有设一棵二叉树是由森林转换而来的，若森林中有n个非终端节点，则二叉树中无右孩子的节点个数为个非终端节点，则二叉树中无右孩子的节点个数为 。 A. n-1B. n C. n+1D. n+2设计题：设计题：

39、设计一棵二叉树，表示夫妻、父子和兄弟关系。设计一棵二叉树，表示夫妻、父子和兄弟关系。思考题：思考题：树树二叉树，二叉树二叉树，二叉树树树为什么没有讨论树的算法？为什么没有讨论树的算法？7.3.1 二叉树的顺序存储结构二叉树的顺序存储结构 二叉树的顺序存储结构中节点的存放次序是：对该二叉树的顺序存储结构中节点的存放次序是：对该树中每个节点进行编号，其编号从小到大的顺序就是节点树中每个节点进行编号，其编号从小到大的顺序就是节点存放在连续存储单元的先后次序。存放在连续存储单元的先后次序。 若把二叉树存储到一维数组中若把二叉树存储到一维数组中,则该编号就是下标值则该编号就是下标值加加1（注意（注意C/

40、C+语言中数组的起始下标为语言中数组的起始下标为0）。树中各节）。树中各节点的编号与等高度的完全二叉树中对应位置上节点的编号点的编号与等高度的完全二叉树中对应位置上节点的编号相同。相同。 利用二叉树的性质利用二叉树的性质4。7.3 二叉树存储结构二叉树存储结构 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉树完全二叉树 ABCDEFGHIJK123456789101112131415顺序存储结构（不用下标为顺序存储结构（不用下标为0的元素）的元素）ABCDEF A B D # C # E # # # # # # F 1 2 3 4 5 6

41、7 8 9 10 11 12 13 142511437一般的二叉树先用空节点一般的二叉树先用空节点补全成为完全二叉树，然补全成为完全二叉树，然后对节点编号后对节点编号typedef ElemType SqBTreeMaxSize;SqBTree bt=#ABD#C#E#F;7.3.2 二叉树的链式存储结构二叉树的链式存储结构 在二叉树的链接存储中，节点的结构如下在二叉树的链接存储中，节点的结构如下: typedef struct node ElemType data; struct node *lchild,*rchild; BTNode; 其中其中,data表示值域表示值域,用于存储对应的数

42、据元素，用于存储对应的数据元素，lchild和和rchild分别表示左指针域和右指针域，用于分别存储左孩子节分别表示左指针域和右指针域，用于分别存储左孩子节点和右孩子节点（即左、右子树的根节点）的存储位置。点和右孩子节点（即左、右子树的根节点）的存储位置。二叉树及其链式存储结构：二叉链二叉树及其链式存储结构：二叉链 ABCDEGFABDGCEFb7.4.1 二叉树的基本运算概述二叉树的基本运算概述 归纳起来，二叉树有以下基本运算：归纳起来，二叉树有以下基本运算： （1）创建二叉树）创建二叉树CreateBTNode(*b,*str)：根据二叉树括：根据二叉树括号表示法的字符串号表示法的字符串*

43、str生成对应的链式存储结构。生成对应的链式存储结构。 （2）查找节点）查找节点FindNode(*b,x)：在二叉树：在二叉树b中寻找中寻找data域域值为值为x的节点，并返回指向该节点的指针。的节点，并返回指向该节点的指针。 （3）找孩子节点）找孩子节点LchildNode(p)和和Rchild-Node(p)：分别：分别求二叉树中节点求二叉树中节点*p的左孩子节点和右孩子节点。的左孩子节点和右孩子节点。7.4 二叉树的基本运算及其实现二叉树的基本运算及其实现 （4）求高度）求高度BTNodeDepth(*b)：求二叉树：求二叉树b的高度。若二的高度。若二叉树为空，则其高度为叉树为空，则其

44、高度为0；否则，其高度等于左子树与右子树；否则，其高度等于左子树与右子树中的最大高度加中的最大高度加l。 （5）输出二叉树）输出二叉树DispBTNode(*b)：以括号表示法输出一：以括号表示法输出一棵二叉树。棵二叉树。7.4.2 二叉树的基本运算算法实现二叉树的基本运算算法实现 （1）创建二叉树）创建二叉树CreateBTNode(*b,*str) 用用ch扫描采用括号表示法表示二叉树的字符串。分以下几种扫描采用括号表示法表示二叉树的字符串。分以下几种情况：情况： 若若ch=(：则将前面刚创建的节点作为双亲节点进栈，并：则将前面刚创建的节点作为双亲节点进栈，并置置k=1，表示其后创建的节点

45、将作为这个节点的左孩子节点；，表示其后创建的节点将作为这个节点的左孩子节点； 若若ch=)：表示栈中节点的左右孩子节点处理完毕，退栈；：表示栈中节点的左右孩子节点处理完毕，退栈； 若若ch=,：表示其后创建的节点为右孩子节点，置：表示其后创建的节点为右孩子节点，置k=2； 其他情况：其他情况： 当当k=1时，表示这个节点作为栈中节点的左孩子节点；时，表示这个节点作为栈中节点的左孩子节点； 当当k=2时，表示这个节点作为栈中节点的右孩子节点。如时，表示这个节点作为栈中节点的右孩子节点。如此循环直到此循环直到str处理完毕。处理完毕。 算法中使用一个栈算法中使用一个栈St保存双亲节点，保存双亲节点

46、，top为其栈指针，为其栈指针，k指定其后处理的节点是双亲节点（保存在栈中）的左孩子节指定其后处理的节点是双亲节点（保存在栈中）的左孩子节点（点（k=1）还是右孩子节点（）还是右孩子节点（k=2）。）。A ( B ( D ( , G ) ) , C ( E , F ) )Ak=1 2B A B D G C E F DC根据括号表示法字符串构造二叉树根据括号表示法字符串构造二叉树void CreateBTNode(BTNode * &b,char *str) BTNode *StMaxSize,*p=NULL; int top=-1,k,j=0; char ch; b=NULL;/建立的二叉树初

47、始时为空建立的二叉树初始时为空 ch=strj; while (ch!=0) /str未扫描完时循环未扫描完时循环 switch(ch) case (:top+;Sttop=p;k=1; break; /为左孩子节点为左孩子节点 case ):top-;break; case ,:k=2; break; /为孩子节点右节点为孩子节点右节点 default: p=(BTNode *)malloc(sizeof(BTNode); p-data=ch;p-lchild=p-rchild=NULL; if (b=NULL) /p为二叉树的根节点为二叉树的根节点 b=p; else /已建立二叉树根节点

48、已建立二叉树根节点 switch(k) case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break; j+;ch=strj; （2）查找节点）查找节点FindNode(*b,x) 采用先序遍历递归算法查找值为采用先序遍历递归算法查找值为x的节点。找到后返回其指的节点。找到后返回其指针，否则返回针，否则返回NULL。算法如下：。算法如下： BTNode *FindNode(BTNode *b,ElemType x) BTNode *p; if (b=NULL) return NULL; else if (b-data=x) return b;

49、else p=FindNode(b-lchild,x); if (p!=NULL) return p; else return FindNode(b-rchild,x); （3）找孩子节点）找孩子节点LchildNode(p)和和RchildNode(p) 直接返回直接返回*p节点的左孩子节点或右孩子节点的指针。算节点的左孩子节点或右孩子节点的指针。算法如下：法如下： BTNode *LchildNode(BTNode *p) return p-lchild; BTNode *RchildNode(BTNode *p) return p-rchild; （4）求高度）求高度BTNodeDept

50、h(*b) 求二叉树的高度的递归模型求二叉树的高度的递归模型f()如下：如下： f(b) = 0 b=NULL f(b) = MAXf(b-lchild),f(b-rchild)+1 其他情况其他情况int BTNodeDepth(BTNode *b) int lchilddep,rchilddep; if (b=NULL) return(0); /空树的高度为空树的高度为0 else lchilddep=BTNodeDepth(b-lchild);/求左子树的高度为求左子树的高度为lchilddep rchilddep=BTNodeDepth(b-rchild);/求右子树的高度为求右子树的

51、高度为rchilddep return(lchilddeprchilddep)? (lchilddep+1):(rchilddep+1); （5）输出二叉树）输出二叉树DispBTNode(*b) 用括弧表示法输出二叉树。用括弧表示法输出二叉树。 对于非空二叉树对于非空二叉树b，先输出其元素值，当存在左孩子节点，先输出其元素值，当存在左孩子节点或右孩子节点时，输出一个或右孩子节点时，输出一个“(”符号，然后递归处理左子树，符号，然后递归处理左子树，输出一个输出一个“,”符号，递归处理右子树，最后输出一个符号，递归处理右子树，最后输出一个“)”符号。符号。void DispBTNode(BTNo

52、de *b) if (b!=NULL) printf(%c,b-data); if (b-lchild!=NULL | b-rchild!=NULL) printf(); DispBTNode(b-lchild); /递归处理左子树递归处理左子树 if (b-rchild!=NULL) printf(,); DispBTNode(b-rchild);/递归处理右子树递归处理右子树 printf(); 7.5.1 二叉树遍历的概念二叉树遍历的概念 二叉树的遍历是指按照一定次序访问树中所有节点，并二叉树的遍历是指按照一定次序访问树中所有节点，并且且每个节点仅被访问一次每个节点仅被访问一次的过程。它

53、是最基本的运算的过程。它是最基本的运算,是二叉是二叉树中所有其他运算的基础。树中所有其他运算的基础。7.5 二叉树的遍历二叉树的遍历1. 先序遍历过程先序遍历过程先序遍历二叉树的过程是：先序遍历二叉树的过程是： 访问根节点；访问根节点； 先序遍历左子树；先序遍历左子树； 先序遍历右子树。先序遍历右子树。ABCDEFGHK先序序列：先序序列：A B C D EHGKF2. 中序遍历过程中序遍历过程中序遍历二叉树的过程是：中序遍历二叉树的过程是： 中序遍历左子树；中序遍历左子树； 访问根节点；访问根节点； 中序遍历右子树。中序遍历右子树。ABCDEFGHK中序序列：中序序列：ABCDE H G K

54、 F3. 后序遍历过程后序遍历过程后序遍历二叉树的过程是：后序遍历二叉树的过程是： 后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树； 访问根节点。访问根节点。ABCDEFGHK后序序列：后序序列：ABCDEHGKF7.5.3 二叉树遍历递归算法二叉树遍历递归算法 由二叉树的三种遍历过程直接得到如下三种递归算法。由二叉树的三种遍历过程直接得到如下三种递归算法。 先序遍历的递归算法：先序遍历的递归算法： void PreOrder(BTNode *b) if (b!=NULL) printf(%c ,b-data); /访问根节点访问根节点 PreOrder(b-lchild);

55、 PreOrder(b-rchild); ABCDEFGHK先序序列：先序序列：A 形参形参T T取值取值 下层调用结束后返回到下层调用结束后返回到主调应该执行的语句主调应该执行的语句A B C D EHGKFB 445C 4D 4 555E 4 5G 4 5H 4 5K 4 5F 4 5递归算法执行时系统栈的变化递归算法执行时系统栈的变化 PreOrder(A) 访问访问 A PreOrder(B) 访问访问 B PreOrder(D) 访问访问 D PreOrder(NULL) PreOrder(G) 访问访问 G PreOrder(NULL) PreOrder(NULL) PreOrde

56、r(NULL) PreOrder(C) 访问访问 C PreOrder(E) 访问访问 E PreOrder(NULL) PreOrder(NULL) PreOrder(F) 访问访问 F PreOrder(NULL) PreOrder(NULL) 递归算法执行过程：递归算法执行过程： 中序遍历的递归算法：中序遍历的递归算法： void InOrder(BTNode *b) if (b!=NULL) InOrder(b-lchild); printf(%c ,b-data); /访问根节点访问根节点 InOrder(b-rchild); 后序遍历递归算法：后序遍历递归算法： void Post

57、Order(BTNode *b) if (b!=NULL) PostOrder(b-lchild); PostOrder(b-rchild); printf(%c ,b-data); /访问根节点访问根节点 思考题：思考题：每种遍历序列提供了什么信息？每种遍历序列提供了什么信息？为什么三种遍历都采用递归求解？为什么三种遍历都采用递归求解？ 例例7.5 假设二叉树采用二叉链存储结构存储，试设计一个算假设二叉树采用二叉链存储结构存储，试设计一个算法，计算一棵给定二叉树的所有节点个数。法，计算一棵给定二叉树的所有节点个数。 解：计算一棵二叉树解：计算一棵二叉树b中所有节点个数的递归模型中所有节点个数

58、的递归模型f(b)如下：如下：f(b)=0若若b=NULLf(b)=f(b- -lchild)+f(b- -rchild)+1其他情况其他情况bb- -lchildb- -rchild对应的递归算法如下：对应的递归算法如下：int Nodes(BTNode *b) int num1,num2; if (b=NULL) return 0; else return Nodes(b-lchild)+Nodes(b-rchild)+1提示：本题算法是基于后序遍历的。提示：本题算法是基于后序遍历的。 例例7.6 假设二叉树采用二叉链存储结构存储，试设计一个假设二叉树采用二叉链存储结构存储，试设计一个算法

59、，计算一棵给定二叉树的所有叶子节点个数。算法，计算一棵给定二叉树的所有叶子节点个数。 解：解：计算一棵二叉树计算一棵二叉树b中所有叶子节点个数的递归模型中所有叶子节点个数的递归模型f(b)如下：如下：f(b)=0若若b=NULLf(b)=1若若*b为叶子节点为叶子节点f(b)=f(b- -lchild)+f(b- -rchild)其他情况其他情况int LeafNodes(BTNode *b)int num1,num2; if (b=NULL) return 0; else if (b-lchild=NULL & b-rchild=NULL) return 1; else num1=LeafN

60、odes(b-lchild);num2=LeafNodes(b-rchild);return (num1+num2); 例例7.7 假设二叉树采用二叉链存储结构存储，试设计一个假设二叉树采用二叉链存储结构存储，试设计一个算法，计算一棵给定二叉树的所有单分支节点个数。算法，计算一棵给定二叉树的所有单分支节点个数。 解：解：计算一棵二叉树计算一棵二叉树b中所有单分支节点个数的递归模型中所有单分支节点个数的递归模型f(b)如下：如下：f(b)=0若若b=NULLf(b)=f(b- -lchild)+f(b- -rchild)+1若若*b为单分支节点为单分支节点f(b)=f(b- -lchild)+f