《数据结构第三版李春葆第7章树形结构》由会员分享，可在线阅读，更多相关《数据结构第三版李春葆第7章树形结构（170页珍藏版）》请在文档大全上搜索。
1、第第7章章 树和二叉树树和二叉树7.1 7.1 树的基本概念树的基本概念 7.2 7.2 二叉树概念和性质二叉树概念和性质7.3 7.3 二叉树存储结构二叉树存储结构7.4 7.4 二叉树的遍历二叉树的遍历7.5 7.5 二叉树的基本运算及其实现二叉树的基本运算及其实现7.6 7.6 二叉树的构造二叉树的构造7.8 7.8 哈夫曼树哈夫曼树 本章小结本章小结7.7 7.7 线索二叉树线索二叉树7.9 7.9 并查集并查集 7.1 7.1 树的基本概念树的基本概念 7.1.1 7.1.1 树的定义树的定义 7.1.3 7.1.3 树的基本术语树的基本术语 7.1.2 7.1.2 树的表示树的表示
2、7.1.4 7.1.4 树的性质树的性质7.1.5 7.1.5 树的基本运算树的基本运算7.1.6 7.1.6 树的存储结构树的存储结构7.1.1 树的定义树的定义 形式化定义：形式化定义： 树：树：TK,R。K是包含是包含n个结点的有穷集合个结点的有穷集合(n0),关关系系R满足以下条件满足以下条件: 有且仅有一个结点有且仅有一个结点k0K,它对于关系它对于关系R来说没有来说没有前驱结点前驱结点,结点结点k0称作树的根。称作树的根。 除结点除结点k0外外,K中的每个结点对于关系中的每个结点对于关系R来说都有来说都有且仅有一个前驱结点。且仅有一个前驱结点。 K中每个结点对于关系中每个结点对于关
3、系R来说可以有多个后继结点。来说可以有多个后继结点。递归定义：递归定义： 树是由树是由n（n0）个结点组成的有限集合（记为）个结点组成的有限集合（记为T）。其中：）。其中： 如果如果n=0,它是一棵空树它是一棵空树,这是树的特例；这是树的特例； 如果如果n0,这这n个结点中存在个结点中存在(有仅存在有仅存在)一个结点一个结点作为树的根结点作为树的根结点,简称为根简称为根(root),其余结点可分为其余结点可分为m (m0)个互不相交的有限集个互不相交的有限集T1,T2,Tm,其中每一棵其中每一棵子集本身又是一棵符合本定义的树子集本身又是一棵符合本定义的树,称为根称为根root的子的子树。树。7
4、.1.2 7.1.2 树的表示树的表示 ( (1) 树形表示法。这是树的最基本的表示树形表示法。这是树的最基本的表示,使用一棵倒置使用一棵倒置的树表示树结构的树表示树结构,非常直观和形象。下图就是采用这种表示法。非常直观和形象。下图就是采用这种表示法。 A C G J B E D F I H M K L 树形表示法树形表示法 逻辑结构表示逻辑结构表示1 1 (2) 文氏图表示法。使用集合以及集合的包含文氏图表示法。使用集合以及集合的包含关系描述树结构。下图就是树的文氏图表示法。关系描述树结构。下图就是树的文氏图表示法。 H L D K I M C G J E B F 文氏图表示法文氏图表示法
5、A 逻辑结构表示逻辑结构表示2 2 A C G J B E D F I H M K L 树形表示法树形表示法 (3) 凹入表示法。使用线段的伸缩描述树结构。下凹入表示法。使用线段的伸缩描述树结构。下图是树的凹入表示法。图是树的凹入表示法。逻辑结构表示逻辑结构表示3 3 A C G J B E D F I H M K L 树形表示法树形表示法 (4) 括号表示法。将树的根结点写在括号的左边括号表示法。将树的根结点写在括号的左边,除根除根结点之外的其余结点写在括号中并用逗号间隔来描述树结点之外的其余结点写在括号中并用逗号间隔来描述树结构。下图是树的括号表示法。结构。下图是树的括号表示法。 括号表示
6、法括号表示法 A(B(E,F),C(G(J),D(H,I(K,L,M) 逻辑结构表示逻辑结构表示4 4 A C G J B E D F I H M K L 树形表示法树形表示法 思考题：思考题：树的逻辑结构定义？适合表示什么类型的数据？树的逻辑结构定义？适合表示什么类型的数据？7.1.3 7.1.3 树的基本术语树的基本术语 1. 结点的度与树的度：树中某结点的度与树的度：树中某个结点的子树的个数称为该结点的个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为度。树中各结点的度的最大值称为树的度树的度,通常将度为通常将度为m的树称为的树称为m次次树树。 A C G J B E D F
7、I H M K L 树形表示法树形表示法 2. 分支结点与叶结点：度不为零的结点称为分支结点与叶结点：度不为零的结点称为非终端结点非终端结点,又叫又叫分支结点分支结点。度为零的结点称为。度为零的结点称为终端结点终端结点或或叶结点叶结点。在分。在分支结点中支结点中,每个结点的分支数就是该结点的度。如对于度为每个结点的分支数就是该结点的度。如对于度为1的结点的结点,其分支数为其分支数为1,被称为被称为单分支结点单分支结点；对于度为；对于度为2的结点的结点,其分支数为其分支数为2,被称为被称为双分支结点双分支结点,其余类推。其余类推。 3. 路径与路径长度：对于任意路径与路径长度：对于任意两个结点两
8、个结点ki和和kj,若树中存在一个结点若树中存在一个结点序列序列ki,ki1,ki2,kin,kj,使得序列中除使得序列中除ki外的任一结点都是其在序列中的前外的任一结点都是其在序列中的前一个结点的后继一个结点的后继,则称该结点序列为则称该结点序列为由由ki到到kj的一条的一条路径路径,用路径所通过的用路径所通过的结点序列结点序列(ki,ki1,ki2,kj)表示这条路表示这条路径。径。 路径长度路径长度等于路径所通过的结点等于路径所通过的结点数目减数目减1(即路径上分支数目即路径上分支数目)。 A C G J B E D F I H M K L 树形表示法树形表示法 4. 孩子结点、双亲结点
9、和兄弟结孩子结点、双亲结点和兄弟结点：在一棵树中点：在一棵树中,每个结点的后继每个结点的后继,被被称作该结点的称作该结点的孩子结点孩子结点(或子女结点或子女结点)。相应地相应地,该结点被称作孩子结点的该结点被称作孩子结点的双亲双亲结点结点(或父母结点或父母结点)。 具有同一双亲的孩子结点互为兄弟具有同一双亲的孩子结点互为兄弟结点。进一步推广这些关系结点。进一步推广这些关系,可以把每可以把每个结点的所有子树中的结点称为该结个结点的所有子树中的结点称为该结点的点的子孙结点。子孙结点。从树根结点到达该结点的路径上经从树根结点到达该结点的路径上经过的所有结点被称作该结点的过的所有结点被称作该结点的祖先
10、结祖先结点点。 A C G J B E D F I H M K L 树形表示法树形表示法 5. 结点的层次和树的高度：树结点的层次和树的高度：树中的每个结点都处在一定的层次上。中的每个结点都处在一定的层次上。结点的层次从树根开始定义结点的层次从树根开始定义,根结根结点为第点为第1层层,它的孩子结点为第它的孩子结点为第2层层,以此类推以此类推,一个结点所在的层次为一个结点所在的层次为其双亲结点所在的层次加其双亲结点所在的层次加1。树中。树中结点的最大层次称为结点的最大层次称为树的高度树的高度(或或树的深度树的深度)。 6. 有序树和无序树：若树中各有序树和无序树：若树中各结点的子树是按照一定的次
11、序从左结点的子树是按照一定的次序从左向右安排的向右安排的,且相对次序是不能随且相对次序是不能随意变换的意变换的,则称为则称为有序树有序树,否则称为否则称为无序树无序树。 A C G J B E D F I H M K L 树形表示法树形表示法 7. 森林：森林：n(n0)个互不相交的树的集合称为森林。个互不相交的树的集合称为森林。森林的概念与树的概念十分相近森林的概念与树的概念十分相近,因为只要把树的根结点因为只要把树的根结点删去就成了森林。反之删去就成了森林。反之,只要给只要给n棵独立的树加上一个结棵独立的树加上一个结点点,并把这并把这n棵树作为该结点的子树棵树作为该结点的子树,则森林就变成
12、了树。则森林就变成了树。7.1.4 树的性质树的性质性质性质1 树中的结点数等于所有结点树中的结点数等于所有结点的度数加的度数加1。 证明：根据树的定义证明：根据树的定义,在一棵树中在一棵树中,除树根结点外除树根结点外,每个结点有且仅有一个每个结点有且仅有一个前驱结点。也就是说前驱结点。也就是说,每个结点与指向每个结点与指向它的一个分支一一对应它的一个分支一一对应,所以除树根之所以除树根之外的结点数等于所有结点的分支数外的结点数等于所有结点的分支数(度度数数),从而可得树中的结点数等于所有结从而可得树中的结点数等于所有结点的度数加点的度数加1。 A C G J B E D F I H M K
13、L 树形表示法树形表示法 度之和分支数度之和分支数分支数分支数=n-1所以，所以，n=度之和度之和+1 性质性质2 度为度为m的树中第的树中第i层上至多有层上至多有mi-1个结点个结点,这里应有这里应有i1。 证明证明(采用数学归纳法采用数学归纳法) 对于第一层对于第一层,因为树中的第一层上只有一个结点因为树中的第一层上只有一个结点,即整个树的即整个树的根结点根结点,而由而由i=1代入代入mi-1,得得mi-1=m1-1=1,也同样得到只有一个结点也同样得到只有一个结点,显然结论成立。显然结论成立。 假设对于第假设对于第(i-1)层层(i1)命题成立命题成立,即度为即度为m的树中第的树中第(i
14、-1)层上层上至多有至多有mi-2个结点。个结点。 则根据树的度的定义则根据树的度的定义,度为度为m的树中每个结点至多有的树中每个结点至多有m个孩子个孩子结点结点,所以第所以第i层上的结点数至多为第层上的结点数至多为第(i-1)层上结点数的层上结点数的m倍倍,即至即至多为多为mi-2m=mi-1个个,这与命题相同这与命题相同,故命题成立。故命题成立。 性质性质3 高度为高度为h的的m次树至多有次树至多有 个结点。个结点。 证明：由树的性质证明：由树的性质2可知可知,第第i层上最多结点数为层上最多结点数为mi -1(i=1,2,h),显然当高度为显然当高度为h的的m次树次树(即度为即度为m的树的
15、树)上每一层上每一层都达到最多结点数时都达到最多结点数时,整个整个m次树具有最多结点数次树具有最多结点数,因此有：因此有：整 个 树 的 最 多 结 点 数整 个 树 的 最 多 结 点 数 = 每 一 层 最 多 结 点 数 之 和每 一 层 最 多 结 点 数 之 和=m0+m1+m2+mh-1 = 。11 mmh11 mmh 性质性质4 具有具有n个结点的个结点的m次树的最小高度为次树的最小高度为 logm(n(m-1)+1) 。 证明：设具有证明：设具有n个结点的个结点的m次树的高度为次树的高度为h,若在该树中前若在该树中前h-1层都是满的层都是满的,即每一层的结点数都等于即每一层的结
16、点数都等于mi-1个个(1ih-1),第第h层层(即最后一层即最后一层)的结点数可能满的结点数可能满,也可能不满也可能不满,则该树具有最小的则该树具有最小的高度。其高度高度。其高度h可计算如下：可计算如下：m=3，h=3，最多结点情况，最多结点情况m=3，h=3，最少结点情况，最少结点情况根据树的性质根据树的性质3可得：可得： n乘乘(m-1)后得：后得： mh-1n(m-1)+1mh以以m为底取对数后得：为底取对数后得：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)
17、 结论得证。结论得证。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 3h-12n+13h 即：即：h= log3(2n+1) 最大高度最大高度为为n-2。7.1.5 树的基本运算树的基本运算 树的运算主要分为三大类：树的运算主要分为三大类： 第一类第一类, ,寻找满足某种特
18、定关系的结点寻找满足某种特定关系的结点, ,如寻找当前结如寻找当前结点的双亲结点等；点的双亲结点等； 第二类第二类, ,插入或删除某个结点插入或删除某个结点, ,如在树的当前结点上插如在树的当前结点上插入一个新结点或删除当前结点的第入一个新结点或删除当前结点的第i i个孩子结点等；个孩子结点等； 第三类第三类, ,遍历树中每个结点遍历树中每个结点, ,这里着重介绍。这里着重介绍。 树的遍历运算是指按某种方式树的遍历运算是指按某种方式访问树中的每一个结点访问树中的每一个结点且每且每一个结点一个结点只被访问一次只被访问一次。 有以下三种遍历方法：有以下三种遍历方法：树的遍历树的遍历 先根遍历先根遍
19、历 后根遍历后根遍历 层次遍历层次遍历注意注意:先根和后根遍历算法都是递归的。先根和后根遍历算法都是递归的。按层次遍历按层次遍历:先根遍历先根遍历:后根遍历后根遍历: 若树不空，则先访问根结点，然后依次先根遍历各棵子树。若树不空，则先访问根结点，然后依次先根遍历各棵子树。 若树不空，则先依次后根遍历各棵子树，然后访问根结点。若树不空，则先依次后根遍历各棵子树，然后访问根结点。 若树不空，则自上而下自左至右访问树中每个结点。若树不空，则自上而下自左至右访问树中每个结点。 层次遍历的顶点访问次序：层次遍历的顶点访问次序：ABCDEFGHJIK 先根遍历的顶点访问次序：先根遍历的顶点访问次序：A B
20、 E F C D G H I J K 后根遍历的顶点访问次序：后根遍历的顶点访问次序：E F B C I J K H G D AA B C D E F G H I J K 若森林不空，则访问森林中第一棵树的根结点若森林不空，则访问森林中第一棵树的根结点; 先序遍历森林中第一棵树的子树森林先序遍历森林中第一棵树的子树森林; 先序遍历森林中先序遍历森林中(除第一棵树之外除第一棵树之外)其余树构成的森林。其余树构成的森林。先序遍历先序遍历森林的遍历森林的遍历即：依次从左至右对森林中的每一棵树进行先根遍历。即：依次从左至右对森林中的每一棵树进行先根遍历。森林的森林的中序中序和和后序后序遍历与此类似。遍
21、历与此类似。7.1.6 树的存储结构树的存储结构1. 1. 双亲存储结构双亲存储结构 这种存储结构是一种顺序存储结构这种存储结构是一种顺序存储结构, ,用一组连续空间存用一组连续空间存储树的所有结点储树的所有结点, ,同时在每个结点中附设一个伪指针指示同时在每个结点中附设一个伪指针指示其双亲结点的位置。其双亲结点的位置。 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
22、 data; /结点的值结点的值 int parent;/指向双亲的位置指向双亲的位置 PTreeMaxSize;2. 孩子链存储结构孩子链存储结构 孩子链存储结构可按树的度孩子链存储结构可按树的度(即树中所有结点度的最大值即树中所有结点度的最大值)设设计结点的孩子结点指针域个数。下图计结点的孩子结点指针域个数。下图(a)的树对应的孩子链存储的树对应的孩子链存储结构如图结构如图(b)所示。所示。树的树的孩子链孩子链存储结构示意存储结构示意图图孩子链存储结构的结点类型定义如下：孩子链存储结构的结点类型定义如下：typedef struct node ElemType data; /结点的值结点的
23、值 struct node *sonsMaxSons; /指向孩子指向孩子结点结点 TSonNode;其中，其中，MaxSons为最多的孩子结点个数。为最多的孩子结点个数。思考题：思考题：n个结点的个结点的m次树有多少个空指针域？次树有多少个空指针域？3. 孩子兄弟链存储结构孩子兄弟链存储结构 孩子兄弟链存储结构是为每个结点设计三个域：一个数孩子兄弟链存储结构是为每个结点设计三个域：一个数据元素域据元素域,一个该结点的第一个孩子结点指针域一个该结点的第一个孩子结点指针域,一个该结点一个该结点的下一个兄弟结点指针域。的下一个兄弟结点指针域。树的树的孩子兄弟链孩子兄弟链存储结构示意图存储结构示意图
24、兄弟链存储结构中结点的类型定义如下：兄弟链存储结构中结点的类型定义如下：typedef struct tnode ElemType data;/结点的值结点的值 struct tnode *hp; /指向兄弟指向兄弟 struct tnode *vp; /指向孩子结点指向孩子结点 TSBNode;每个结点固定只有两个指针域。每个结点固定只有两个指针域。7.2 二叉树概念和性质二叉树概念和性质 7.2.1 二叉树概念二叉树概念7.2.2 二叉树性质二叉树性质7.2.3 二叉树与树、森林之间的转换二叉树与树、森林之间的转换7.2.1 二叉树概念二叉树概念 二叉树是有限的结点集合。二叉树是有限的结点
25、集合。 这个集合或者是空。这个集合或者是空。 或者由一个或者由一个根结点根结点和两棵互不相交的称为和两棵互不相交的称为左子树左子树和和右右子树子树的二叉树组成。的二叉树组成。 注意：二叉树的定义是一种递归定义。注意：二叉树的定义是一种递归定义。二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点LRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子树均左右子树均不为空树不为空树NNN 从定义看到从定义看到,二叉树是一种特殊的树二叉树是一种特殊的树,其表示法也与树其表示法也与树的表示法一样：的表示法一样： 树形表示法树形表示法 文氏图表示法文氏图表示法 凹入表示法凹
26、入表示法 括号表示法括号表示法 在一棵二叉树中在一棵二叉树中,如果如果所有分支结点都有左孩子结点和右孩所有分支结点都有左孩子结点和右孩子结点子结点,并且并且叶结点都集中在二叉树的最下一层叶结点都集中在二叉树的最下一层,这样的二叉树这样的二叉树称为称为满二叉树满二叉树。下图所示就是一棵满二叉树。可以对满二叉树的结点进行下图所示就是一棵满二叉树。可以对满二叉树的结点进行连续编号连续编号,约定编号从树根为约定编号从树根为1开始开始,按照层数从小到大、同一层按照层数从小到大、同一层从左到右的次序进行。图中每个结点外边的数字为对该结点的从左到右的次序进行。图中每个结点外边的数字为对该结点的编号。编号。
27、A B C D E H I J K F G L M N O 1 2 3 4 5 6 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,则总结点数则总结点数=n0+n1+n2。在一棵二叉树中。在一棵二叉树中,所有结点所有结点的分支数的分支数(即度数即度数)应等于单分支结点数加上
29、双分支结点数的应等于单分支结点数加上双分支结点数的2倍倍,即总的分支数即总的分支数=n1+2n2。 由于二叉树中除根结点以外由于二叉树中除根结点以外,每个结点都有唯一的一个分支指每个结点都有唯一的一个分支指向它向它,因此二叉树中有：总的分支数因此二叉树中有：总的分支数=总结点数总结点数-1。 由上述三个等式可得：由上述三个等式可得：n1+2n2=n0+n1+n2-1即：即：n0=n2+1 性质性质2 非空二叉树上第非空二叉树上第i层上至多有层上至多有2i-1个结点个结点,这里应有这里应有i1。 由树的性质由树的性质2可推出。可推出。 性质性质3 高度为高度为h的二叉树至多有的二叉树至多有2h-
30、1个结点个结点(h1)。 由树的性质由树的性质3可推出。可推出。 性质性质4 对完全二叉树中编号为对完全二叉树中编号为i的结点的结点(1in,n1,n为结为结点数点数)有：有： (1) 若若i n/2 ,即即2in,则编号为则编号为i的结点为分支结点的结点为分支结点,否则为否则为叶子结点。叶子结点。 (2) 若若n为奇数为奇数,则每个分支结点都既有左孩子结点则每个分支结点都既有左孩子结点,也有右也有右孩子结点；若孩子结点；若n为偶数为偶数,则编号最大的分支结点则编号最大的分支结点(编号为编号为)只有只有左孩子结点左孩子结点,没有右孩子结点没有右孩子结点,其余分支结点都有左、右孩子其余分支结点都
31、有左、右孩子结点。结点。 (3) 若编号为若编号为i的结点有左孩子结点的结点有左孩子结点,则左孩子结点的编号则左孩子结点的编号为为2i；若编号为；若编号为i的结点有右孩子结点的结点有右孩子结点,则右孩子结点的编号则右孩子结点的编号为为(2i+1)。 (4) 除树根结点外除树根结点外,若一个结点的编号为若一个结点的编号为i,则它的双亲结点则它的双亲结点的编号为的编号为 i/2 ,也就是说也就是说,当当i为偶数时为偶数时,其双亲结点的编号为其双亲结点的编号为i/2,它是双亲结点的左孩子结点它是双亲结点的左孩子结点,当当i为奇数时为奇数时,其双亲结点的编号其双亲结点的编号为为(i-1)/2,它是双亲
32、结点的右孩子结点。它是双亲结点的右孩子结点。思考题：思考题：性质性质4的特点？的特点？i/2i2i2i+1 性质性质5 具有具有n个个(n0)结点的完全二叉树的高度为结点的完全二叉树的高度为 log2n+1 或或 log2n +1。 由完全二叉树的定义和树的性质由完全二叉树的定义和树的性质3可推出。可推出。7.2.3 二叉树与树、森林之间的转换二叉树与树、森林之间的转换1森林、树转换为二叉树森林、树转换为二叉树 步骤如下：步骤如下： (1) 在所有相邻兄弟结点在所有相邻兄弟结点(森林中每棵树的根结点可看成是森林中每棵树的根结点可看成是兄弟结点兄弟结点)之间加一水平连线。之间加一水平连线。 (2
33、) 对每个非叶结点对每个非叶结点k,除了其最左边的孩子结点外除了其最左边的孩子结点外,删去删去k与与其他孩子结点的连线。其他孩子结点的连线。 (3) 所有水平线段以左边结点为轴心顺时针旋转所有水平线段以左边结点为轴心顺时针旋转45度。度。 通过以上步骤通过以上步骤,原来的森林就转换为一棵二叉树。原来的森林就转换为一棵二叉树。 一般的树是森林中的特殊情况一般的树是森林中的特殊情况,由一般的树转换的二叉树由一般的树转换的二叉树的根结点的右孩子结点始终为空的根结点的右孩子结点始终为空,原因是一般的树的根结点不原因是一般的树的根结点不存在兄弟结点和相邻的树。存在兄弟结点和相邻的树。ABCDEFGHII
34、将森林转换为二叉树的过程将森林转换为二叉树的过程2. 二叉树还原为森林、树二叉树还原为森林、树 步骤如下：步骤如下： (1) 对于一棵二叉树中任一结点对于一棵二叉树中任一结点k0,沿着沿着k0的左孩子结点的左孩子结点k1的右子树方向搜索所有右孩子结点的右子树方向搜索所有右孩子结点,即搜索结点序列即搜索结点序列k2,k3,km,其中其中ki+1为为ki的右孩子结点的右孩子结点(1im),km没有右孩没有右孩子结点。子结点。 (2) 删去删去k1,k2,km之间连线。之间连线。 (3) 若若k1有双亲结点有双亲结点k,则连接则连接k与与ki(2im)。 (4) 将图形规整化将图形规整化,使各结点按
35、层次排列使各结点按层次排列。 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 G (b) 将一棵二叉树还原为树的过程将一棵二叉树还原为树的过程思考题：思考题：树树二叉树，二叉树二叉树，二叉树树树为什么没有讨论树的算法？为什么没有讨论树的算法？7.3 二叉树存储结构二叉树存储结构 7.3.1 二叉树的顺序存储结构二叉树的顺序存储结构 7.3.2 二叉树的链式存储结构二叉树的链式存储结构7.3.1 二叉树的顺序存储结构二叉树的顺序存储结构 二叉树的顺序存储结构中结点的存放次序是：对该二叉树的顺序存储结构中结点的存放次序是：对该树中每个结点
36、进行编号树中每个结点进行编号,其编号从小到大的顺序就是结点其编号从小到大的顺序就是结点存放在连续存储单元的先后次序。存放在连续存储单元的先后次序。 若把二叉树存储到一维数组中若把二叉树存储到一维数组中,则该编号就是下标值则该编号就是下标值加加1(注意注意,C/C+语言中数组的起始下标为语言中数组的起始下标为0)。树中各结点。树中各结点的编号与等高度的完全二叉树中对应位置上结点的编号相的编号与等高度的完全二叉树中对应位置上结点的编号相同。同。 利用二叉树的性质利用二叉树的性质4。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉树完全二叉树 A
37、BCDEFGHIJK123456789101112131415顺序存储结构顺序存储结构ABCDEF A B D C E F 1 2 3 4 5 6 7 8 9 10 11 12 13 142511437一般的二叉树先用空结点一般的二叉树先用空结点补全成为完全二叉树，然补全成为完全二叉树，然后对结点编号后对结点编号7.3.2 二叉树的链式存储结构二叉树的链式存储结构 在二叉树的链接存储中在二叉树的链接存储中,结点的结构如下结点的结构如下: typedef struct node ElemType data; struct node *lchild,*rchild; BTNode; 其中其中,da
38、ta表示值域表示值域,用于存储对应的数据元素用于存储对应的数据元素,lchild和和rchild分别表示左指针域和右指针域分别表示左指针域和右指针域,用于分别存储左孩子结点和右用于分别存储左孩子结点和右孩子结点孩子结点(即左、右子树的根结点即左、右子树的根结点)的存储位置。的存储位置。二叉树及其链式存储结构二叉树及其链式存储结构 A B C E F D G A B C D E F G (a) (b) 7.4 二叉树的基本运算及其实现二叉树的基本运算及其实现7.4.1 二叉树的基本运算概述二叉树的基本运算概述7.4.2 二叉树的基本运算算法实现二叉树的基本运算算法实现7.4.1 二叉树的基本运算
39、概述二叉树的基本运算概述 归纳起来，二叉树有以下基本运算：归纳起来，二叉树有以下基本运算： （1）创建二叉树）创建二叉树CreateBTNode(*b,*str)：根据二叉树括：根据二叉树括号表示法的字符串号表示法的字符串*str生成对应的链式存储结构。生成对应的链式存储结构。 （2）查找结点）查找结点FindNode(*b,x)：在二叉树：在二叉树b中寻找中寻找data域域值为值为x的结点，并返回指向该结点的指针。的结点，并返回指向该结点的指针。 （3）找孩子结点）找孩子结点LchildNode(p)和和Rchild-Node(p)：分别：分别求二叉树中结点求二叉树中结点*p的左孩子结点和右
40、孩子结点。的左孩子结点和右孩子结点。 （4）求高度）求高度BTNodeDepth(*b)：求二叉树：求二叉树b的高度。若二的高度。若二叉树为空，则其高度为叉树为空，则其高度为0；否则，其高度等于左子树与右子树；否则，其高度等于左子树与右子树中的最大高度加中的最大高度加l。 （5）输出二叉树）输出二叉树DispBTNode(*b)：以括号表示法输出一：以括号表示法输出一棵二叉树。棵二叉树。7.4.2 二叉树的基本运算算法实现二叉树的基本运算算法实现（1）创建二叉树）创建二叉树CreateBTNode(*b,*str) 用用ch扫描采用括号表示法表示二叉树的字符串。分以下几种扫描采用括号表示法表示
41、二叉树的字符串。分以下几种情况：情况： 若若ch=(：则将前面刚创建的结点作为双亲结点进栈，并：则将前面刚创建的结点作为双亲结点进栈，并置置k=1，表示其后创建的结点将作为这个结点的左孩子结点；，表示其后创建的结点将作为这个结点的左孩子结点； 若若ch=)：表示栈中结点的左右孩子结点处理完毕，退栈；：表示栈中结点的左右孩子结点处理完毕，退栈； 若若ch=,：表示其后创建的结点为右孩子结点；：表示其后创建的结点为右孩子结点； 其他情况：其他情况： 当当k=1时，表示这个结点作为栈中结点的左孩子结点；时，表示这个结点作为栈中结点的左孩子结点； 当当k=2时，表示这个结点作为栈中结点的右孩子结点。时
42、，表示这个结点作为栈中结点的右孩子结点。如此循环直到如此循环直到str处理完毕。处理完毕。 算法中使用一个栈算法中使用一个栈St保存双亲结点，保存双亲结点，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,cha
43、r *str) BTNode *StMaxSize,*p=NULL; int top=-1,k,j=0; char ch; b=NULL;/建立的二叉树初始时为建立的二叉树初始时为空空 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=c
44、h;p-lchild=p-rchild=NULL; if (b=NULL) /p为二叉树的根结点为二叉树的根结点 b=p; else /已建立二叉树根已建立二叉树根结点结点 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,
45、ElemType x) BTNode *p; if (b=NULL) return NULL; else if (b-data=x) return b; 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
46、p-lchild; BTNode *RchildNode(BTNode *p) return p-rchild; （4）求高度）求高度BTNodeDepth(*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-lchi
47、ld);/求左子树的高度为求左子树的高度为lchilddep rchilddep=BTNodeDepth(b-rchild);/求右子树的高度为求右子树的高度为rchilddep return(lchilddeprchilddep)? (lchilddep+1):(rchilddep+1); （5）输出二叉树）输出二叉树DispBTNode(*b) 用括弧表示法输出二叉树。用括弧表示法输出二叉树。 对于非空二叉树对于非空二叉树b，先输出其元素值，当存在左孩子结点，先输出其元素值，当存在左孩子结点或右孩子结点时，输出一个或右孩子结点时，输出一个“(”符号，然后递归处理左子树，符号，然后递归处理左
48、子树，输出一个输出一个“,”符号，递归处理右子树，最后输出一个符号，递归处理右子树，最后输出一个“)”符号。符号。void DispBTNode(BTNode *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 二叉树的遍历二叉树的遍历7.5.1
49、 二叉树遍历的概念二叉树遍历的概念7.5.2 二叉树遍历递归算法二叉树遍历递归算法7.5.3 二叉树遍历非递归算法二叉树遍历非递归算法 7.5.4 层次遍历层次遍历 7.5.1 二叉树遍历的概念二叉树遍历的概念 二叉树的遍历是指按照一定次序访问树中所有结点二叉树的遍历是指按照一定次序访问树中所有结点,并并且每个结点仅被访问一次的过程。它是最基本的运算且每个结点仅被访问一次的过程。它是最基本的运算,是二叉是二叉树中所有其他运算的基础。树中所有其他运算的基础。1. 先序遍历过程先序遍历过程先序遍历二叉树的过程是：先序遍历二叉树的过程是：(1) 访问根结点；访问根结点；(2) 先序遍历左子树；先序遍
50、历左子树；(3) 先序遍历右子树。先序遍历右子树。ABCDEFGHK先序序列：先序序列：A B C D EHGKF2. 中序遍历过程中序遍历过程中序遍历二叉树的过程是：中序遍历二叉树的过程是：(1) 中序遍历左子树；中序遍历左子树；(2) 访问根结点；访问根结点；(3) 中序遍历右子树。中序遍历右子树。ABCDEFGHK中序序列：中序序列：ABCDE H G K F3. 后序遍历过程后序遍历过程后序遍历二叉树的过程是：后序遍历二叉树的过程是：(1) 后序遍历左子树；后序遍历左子树；(2) 后序遍历右子树；后序遍历右子树；(3) 访问根结点。访问根结点。ABCDEFGHK后序序列：后序序列：AB
51、CDEHGKF7.5.3 二叉树遍历递归算法二叉树遍历递归算法 由二叉树的三种遍历过程直接得到如下三种递归算法。由二叉树的三种遍历过程直接得到如下三种递归算法。先序遍历的递归算法：先序遍历的递归算法： void PreOrder(BTNode *b) if (b!=NULL) printf(%c ,b-data); /访问根结点访问根结点 PreOrder(b-lchild); PreOrder(b-rchild); 重点重点ABCDEFGHK先序序列：先序序列：A 形参形参T T取值取值 下层调用结束后返回到下层调用结束后返回到主调应该执行的语句主调应该执行的语句A B C D EHGKFB
52、 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) PreOrder(NULL) PreOrder(C) 访问访问 C PreOrder(E) 访问访问 E PreOrder(NULL) PreOrder(NULL) PreOrder(F) 访问访问 F PreOrder(NU
53、LL) PreOrder(NULL) 递归算法执行过程：递归算法执行过程：中序遍历的递归算法：中序遍历的递归算法： void InOrder(BTNode *b) if (b!=NULL) InOrder(b-lchild); printf(%c ,b-data); /访问根结点访问根结点 InOrder(b-rchild); 重点重点后序遍历递归算法：后序遍历递归算法：void PostOrder(BTNode *b) if (b!=NULL) PostOrder(b-lchild); PostOrder(b-rchild); printf(%c ,b-data); /访问根结点访问根结点
54、重点重点思考题：思考题：每种遍历序列提供了什么信息？每种遍历序列提供了什么信息？为什么三种遍历都采用递归求解？为什么三种遍历都采用递归求解？ 例例7.8 假设二叉树采用二叉链存储结构存储假设二叉树采用二叉链存储结构存储,试设计一个算试设计一个算法法,输出一棵给定二叉树的所有叶子结点。输出一棵给定二叉树的所有叶子结点。 解：输出一棵二叉树的所有叶子结点的递归模型解：输出一棵二叉树的所有叶子结点的递归模型f()如下：如下： f(b)：不做任何事件：不做任何事件 若若b=NULL f(b)：输出：输出*b结点的结点的data域域 若若*b为叶子结点为叶子结点 f(b)：f(b-lchild);f(b
55、-rchild) 其他情况其他情况void DispLeaf(BTNode *b) if (b!=NULL) if (b-lchild=NULL & b-rchild=NULL) printf(%c ,b-data); else DispLeaf(b-lchild); DispLeaf(b-rchild); void DispLeaf(BTNode *b) if (b!=NULL) if (b-lchild=NULL & b-rchild=NULL) printf(%c ,b-data); DispLeaf(b-lchild); DispLeaf(b-rchild); 与与先序遍历先序遍历算法
56、完全相同，只是访问的方式不同。算法完全相同，只是访问的方式不同。 例例7.9 假设二叉树采用二叉链存储结构假设二叉树采用二叉链存储结构,设计一个算法设计一个算法Level()求二叉树中指定结点的层数。求二叉树中指定结点的层数。设设 Level(b,x,h)返回二叉链返回二叉链b中中data值为值为x的结点的层数，的结点的层数，其中其中h表示表示b所指结点的层数。所指结点的层数。b调用调用Level(b,x,0)返回返回x结结点的层数。点的层数。int Level(BTNode *b,ElemType x,int h) /找到找到*p结点后结点后h为其层次为其层次,否则为否则为0 if (b=N
57、ULL) return 0; /空树时返回空树时返回0 else if (b-data=x) return h; /找到结点时找到结点时 else l=Level(b-lchild,x,h+1);/在左子树中查找在左子树中查找 if (l=0) /左子树中未找到时在右子树中查找左子树中未找到时在右子树中查找 return Level(b-rchild,x,h+1); else return l; 基于基于先序遍历先序遍历算法思想。算法思想。 例例7.10 假设二叉树采用二叉链存储结构假设二叉树采用二叉链存储结构,设计一个算法设计一个算法判断两棵二叉树是否相似判断两棵二叉树是否相似,所谓二叉树所
58、谓二叉树t1和和t2是相似的指的是是相似的指的是t1和和t2都是空的二叉树；或者都是空的二叉树；或者t1和和t2的根结点是相似的的根结点是相似的,以及以及t1的左子树和的左子树和t2的左子树是相似的且的左子树是相似的且t1的右子树与的右子树与t2的右子的右子树是相似的。树是相似的。 解：判断两棵二叉树是否相似的递归模型解：判断两棵二叉树是否相似的递归模型f()如下：如下：f(t1,t2)=true 若若t1=t2=NULLf(t1,t2)=false 若若t1、t2之一为之一为NULL,另一不为另一不为NULLf(t1,t2)=f(t1-lchild,t2-lchild) & 其他情况其他情况
59、 f(t1-rchild,t2-rchild) 对应的算法如下：对应的算法如下：int Like(BTNode *b1,BTNode *b2)/t1和和t2两棵二叉树相似时返回两棵二叉树相似时返回1,否则返回否则返回0 int like1,like2; if (b1=NULL & b2=NULL) return 1; else if (b1=NULL | b2=NULL) return 0; else like1=Like(b1-lchild,b2-lchild); like2=Like(b1-rchild,b2-rchild); return (like1 & like2);基于基于后序遍历
60、后序遍历算法思想。算法思想。7.5.3 7.5.3 二叉树遍历非递归算法二叉树遍历非递归算法 1. 1. 先序遍历先序遍历非递归算法非递归算法步骤如下：步骤如下：if (当前当前b树不空树不空) 根结点根结点b进栈进栈; while (栈不空栈不空) 出栈结点出栈结点p并访问之并访问之; 若若*p结点有右孩子，将其右孩子进栈；结点有右孩子，将其右孩子进栈； 若若*p结点有左孩子，将其左孩子进栈；结点有左孩子，将其左孩子进栈； 根左右根左右b先序遍历先序遍历A B C D EHGKFABCDEFGHKAB C D E F G H K 改为与算法一致改为与算法一致先序序列：先序序列：void Pr
61、eOrder1(BTNode *b)BTNode *StMaxSize,*p; int top=-1; top+; Sttop=b; /根结点入栈根结点入栈 while (top-1) /栈不为空时循环栈不为空时循环 p=Sttop; top-; /退栈并访问该结点退栈并访问该结点 printf(%c ,p-data); if (p-rchild!=NULL) /右孩子结点入栈右孩子结点入栈 top+; Sttop=p-rchild; if (p-lchild!=NULL)/左孩子结点入栈左孩子结点入栈 top+; Sttop=p-lchild; 2. 中序遍历非递归算法中序遍历非递归算法 步
62、骤如下：步骤如下：if (当前当前b树不空树不空) pb; while (栈不空或者栈不空或者p!=NULL) while (p有左孩子，将进栈有左孩子，将进栈)； if (栈不空栈不空) 出栈出栈p并访问之；并访问之；pp-rchild; 左根右左根右bpb b的最左下结点的最左下结点说明：说明：（1）所有左下孩子进栈，体现先访问左子树的特点。）所有左下孩子进栈，体现先访问左子树的特点。（2）当所有左下孩子进栈后，栈顶结点）当所有左下孩子进栈后，栈顶结点p没有左孩子（也没有左孩子（也就是没有左子树）或者其左子树均已访问，所以可以访问就是没有左子树）或者其左子树均已访问，所以可以访问p结点。结
63、点。（3）当访问）当访问p结点后，转向其右孩子，采用同样的方式中结点后，转向其右孩子，采用同样的方式中序遍历右子树。序遍历右子树。中序遍历中序遍历ABCDE H G K FABCDEFGHKAB C D E F G H K 中序序列：中序序列：void InOrder1(BTNode *b) BTNode *StMaxSize,*p; int top=-1; p=b; while (top-1 | p!=NULL) while (p!=NULL) /扫描扫描*p的所有左结点并进栈的所有左结点并进栈 top+; Sttop=p; p=p-lchild; if (top-1) p=Sttop;to
64、p-; /出栈出栈*p结点结点 printf(%c ,p-data); /访问之访问之 p=p-rchild; /处理右子树处理右子树 找找*b的最左下结点的最左下结点3. 后序遍历非递归算法后序遍历非递归算法 步骤如下：步骤如下：if (当前当前b树不空树不空) do while (b!=NULL, b有左孩子有左孩子,将进栈将进栈) ; 出栈结点出栈结点b; if (b的右子树已访问的右子树已访问)则访问则访问b并退栈；并退栈； else bb-rchild; while (栈不空栈不空);左右根左右根难点：难点：如何判断一个结点如何判断一个结点*b的右孩子结点已访问过。的右孩子结点已访问
65、过。方法：用方法：用p保存刚刚访问过的结点（初值为保存刚刚访问过的结点（初值为NULL），），若若b-rchild=p成立，说明成立，说明*b的左右子树均已访问，的左右子树均已访问，现在应访问现在应访问*b。 原因：原因：在后序遍历中，在后序遍历中，*b的右孩子结点一定刚好在的右孩子结点一定刚好在*b之前访问。之前访问。左右根左右根pb后序遍历后序遍历ABCDEHGKFABCDEFGHKA B C D E F G H K 后序序列：后序序列：void PostOrder1(BTNode *b) BTNode *StMaxSize;BTNode *p; int flag,top=-1; /栈指针
66、置初值栈指针置初值 do while (b!=NULL) /将将*b的所有左结点进栈的所有左结点进栈 top+; Sttop=b; b=b-lchild; p=NULL;/p指向栈顶结点的前一个已访问的结点指向栈顶结点的前一个已访问的结点 flag=1; /表示表示*b的左子树已访问或为空的左子树已访问或为空找最左下结点找最左下结点 while (top!=-1 & flag=1) b=Sttop; /取出当前的栈顶元素取出当前的栈顶元素 if (b-rchild=p) printf(%c ,b-data);/访问访问*b结点结点 top-;p=b; /p指向则被访问的结点指向则被访问的结点 else b=b-rchild;/b指向右孩子结点指向右孩子结点 flag=0; /b的左子树未访问的左子树未访问 while (top!=-1); b的右孩子不存在或已访问过的右孩子不存在或已访问过 从上述过程可知，栈中保存的是当前结点从上述过程可知，栈中保存的是当前结点*b的的所有祖先结点（均未访问过）。所有祖先结点（均未访问过）。 例如，求一个结点的所有祖先结点。例如，求一个结点的所有祖先结
