【精品】【考研计算机专业课】武汉大学数据结构PPT课件 第7章树形结构精品ppt课件.ppt

【考研计算机专业课】武汉大学数据结构PPT课件 第7章 树形结构7.1.1 树的定义树的定义 形式化定义：形式化定义：树树：TK,R。K是是包包含含n个个结结点点的的有有穷穷集集合合（n0）,关系关系R满足以下条件满足以下条件:l有且仅有一个结点有且仅有一个结点k0K,它对于关系它对于关系R来说没有来说没有前驱结点前驱结点,结点结点k0称作树的称作树的根结点根结点。l 除结点除结点k0外外,K中的每个结点对于关系中的每个结点对于关系R来说都有来说都有且且仅有一个前驱结点仅有一个前驱结点。l K中每个结点对于关系中每个结点对于关系R来说可以有来说可以有零个或多个零个或多个后继结点后继结点。7.1 树的基本概念树的基本概念 递归定义：递归定义：树树是由是由n（n0）个结点组成的有限集合（记为）个结点组成的有限集合（记为T）。其中：）。其中：l如果如果n=0,它是一棵空树它是一棵空树,这是树的特例；这是树的特例；l如果如果n0，这，这n个结点中存在（有仅存在）一个结点个结点中存在（有仅存在）一个结点作为树的根结点作为树的根结点,简称为根结点（简称为根结点（root），其余结点可），其余结点可分为分为m（m0）个互不相交的有限集）个互不相交的有限集T1,T2,Tm，其，其中每一棵子集本身又是一棵符合本定义的中每一棵子集本身又是一棵符合本定义的树树，称为，称为根根root的子树。的子树。rootT1T2Tm7.1.2 树的表示树的表示 （1）树树形形表表示示法法。这这是是树树的的最最基基本本的的表表示示,使使用用一一棵棵倒倒置置的树表示树结构的树表示树结构,非常直观和形象。下图就是采用这种表示法。非常直观和形象。下图就是采用这种表示法。ABCDEFGJHIKLM逻辑结构表示逻辑结构表示1 （2）文文氏氏图图表表示示法法。使使用用集集合合以以及及集集合合的的包包含含关关系系描描述述树树结结构构。下下图图就就是是树树的的文文氏氏图表示法。图表示法。ABCDEFGJHIKLM逻辑结构表示逻辑结构表示2AEFBCGJHDKLMI思考题：思考题：树的逻辑结构定义？适合表示什么类型的数据？树的逻辑结构定义？适合表示什么类型的数据？7.1.3 树的基本术语树的基本术语 1.结结点点的的度度与与树树的的度度：树树中中某某个个结结点点的的子子树树的的个个数数称称为为该该结结点点的的度度。树树中中各各结结点点的的度度的的最最大大值值称称为为树树的的度度,通通常常将将度为度为m的树称为的树称为m次树次树。2.分分支支结结点点与与叶叶结结点点：度度不不为为零零的的结结点点称称为为非非终终端端结结点点,又又叫叫分分支支结结点点。度度为为零零的的结结点点称称为为终终端端结结点点或或叶叶结结点点。在在分分支支结结点点中中,每每个个结结点点的的分分支支数数就就是是该该结结点点的的度度。如如对对于于度度为为1的的结结点点,其其分分支支数数为为1,被被称称为为单单分分支支结结点点；对对于于度度为为2的的结结点点,其分支数为其分支数为2,被称为双分支结点被称为双分支结点,其余类推。其余类推。ABCDEFGJHIKLM 3.路路径径与与路路径径长长度度：对对于于任任意意两两个个结结点点ki和和kj,若若树树中中存存在在一一个个结结点点序序列列ki,ki1,ki2,kin,kj,使使得得序序列列中中除除ki外外的的任任一一结结点点都都是是其其在在序序列列中中的的前前一一个个结结点点的的后后继继,则则称称该该结结点点序序列列为为由由ki到到kj的的一一条条路路径径,用用 路路 径径 所所 通通 过过 的的 结结 点点 序序 列列(ki,ki1,ki2,kj)表示这条路径表示这条路径。路路径径长长度度等等于于路路径径所所通通过过的的结结点点数目减数目减1（即路径上分支数目）。（即路径上分支数目）。ABCDEFGJHIKLM 4.孩孩子子结结点点、双双亲亲结结点点和和兄兄弟弟结结点点：在在一一棵棵树树中中,每每个个结结点点的的后后继继,被被称称作作该该结结点点的的孩孩子子结结点点(或或子子女女结结点点)。相相应应地地,该该结结点点被被称称作作孩孩子子结结点点的的双双亲亲结点结点(或父母结点或父母结点)。具具有有同同一一双双亲亲的的孩孩子子结结点点互互为为兄兄弟弟结结点点。进进一一步步推推广广这这些些关关系系,可可以以把把每每个个结结点点的的所所有有子子树树中中的的结结点点称称为为该该结结点的点的子孙结点子孙结点。从从树树根根结结点点到到达达该该结结点点的的路路径径上上经经过过的的所所有有结结点点被被称称作作该该结结点点的的祖祖先先结结点点。ABCDEFGJHIKLM 5.结结点点的的层层次次和和树树的的高高度度：树树中中的的每每个个结结点点都都处处在在一一定定的的层层次次上上。结结点点的的层层次次从从树树根根开开始始定定义义,根根结结点点为为第第1层层,它它的的孩孩子子结结点点为为第第2层层,以以此此类类推推,一一个个结结点点所所在在的的层层次次为为其其双双亲亲结结点点所所在在的的层层次次加加1。树树中中结结点点的的最最大大层层次次称称为为树树的的高高度度（或或树树的的深度深度）。）。6.有有序序树树和和无无序序树树：若若树树中中各各结结点点的的子子树树是是按按照照一一定定的的次次序序从从左左向向右右安安排排的的,且且相相对对次次序序是是不不能能随随意意变变换换的的,则则称称为为有有序序树树,否否则则称称为为无无序树序树。ABCDEFGJHIKLM 7.森森林林：n（n0）个个互互不不相相交交的的树树的的集集合合称称为为森森林林。森森林林的的概概念念与与树树的的概概念念十十分分相相近近,因因为为只只要要把把树树的的根根结结点点删删去去就就成成了了森森林林。反反之之,只只要要给给n棵棵独独立立的的树树加加上上一一个个结结点点,并把这并把这n棵树作为该结点的子树棵树作为该结点的子树,则森林就变成了树。则森林就变成了树。7.1.4 树的性质树的性质性性质质1 树树中中的的结结点点数数等等于于所所有有结点的度数加结点的度数加1。证证明明：根根据据树树的的定定义义,在在一一棵棵树树中中,除除树树根根结结点点外外,每每个个结结点点有有且且仅仅有有一一个个前前驱驱结结点点。也也就就是是说说,每每个个结结点点与与指指向向它它的的一一个个分分支支一一一一对对应应,所所以以除除树树根根之之外外的的结结点点数数等等于于所所有有结结点点的的分分支支数数（度度数数）,从从而而可可得得树树中中的的结结点点数数等等于于所有结点的度数加所有结点的度数加1。度之和分支数度之和分支数分支数分支数=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的节点，的节点，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，也也同同样样得得到到只只有有一一个个结点，显然结论成立。结点，显然结论成立。假假设设对对于于第第(i-1)层层（i1）命命题题成成立立，即即度度为为m的的树树中中第第(i-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的的树树)上上每每一一层层都达到最多结点数时都达到最多结点数时,整个整个m次树具有最多结点数次树具有最多结点数,因此有：因此有：整整 个个 树树 的的 最最 多多 结结 点点 数数=每每 一一 层层 最最 多多 结结 点点 数数 之之 和和=m0+m1+m2+mh-1=。性性质质4 具具有有n个个结结点点的的m次次树树的的最最小小高高度度为为 logm(n(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为底取对数后得：为底取对数后得：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)结论得证。结论得证。例例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 树的基本运算树的基本运算 树的运算主要分为三大类：树的运算主要分为三大类：第第一一类类,寻寻找找满满足足某某种种特特定定关关系系的的结结点点,如如寻寻找找当当前前结结点的双亲结点等；点的双亲结点等；第第二二类类,插插入入或或删删除除某某个个结结点点,如如在在树树的的当当前前结结点点上上插插入一个新结点或删除当前结点的第入一个新结点或删除当前结点的第i i个孩子结点等；个孩子结点等；第三类第三类,遍历树中每个结点遍历树中每个结点,这里着重介绍。这里着重介绍。树树的的遍遍历历运运算算是是指指按按某某种种方方式式访访问问树树中中的的每每一一个个结结点点且且每每一个结点只被访问一次。一个结点只被访问一次。有以下三种遍历方法：有以下三种遍历方法：树的遍历树的遍历 先根遍历先根遍历 后根遍历后根遍历 层次遍历层次遍历注意：先根和后根遍历算法都是递归的。注意：先根和后根遍历算法都是递归的。按层次遍历按层次遍历:先根遍历先根遍历:后根遍历后根遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。若树不空，则先访问根结点，然后依次先根遍历各棵子树。若树不空，则先依次后根遍历各棵子树，然后访问根结点。若树不空，则先依次后根遍历各棵子树，然后访问根结点。若树不空，则自上而下自左至右访问树中每个结点。若树不空，则自上而下自左至右访问树中每个结点。层次遍历的顶点访问次序：层次遍历的顶点访问次序：ABCDEFGHJIK 先根遍历的顶点访问次序：先根遍历的顶点访问次序：A B 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 K7.1.6 树的存储结构树的存储结构1.1.双亲存储结构双亲存储结构 这这种种存存储储结结构构是是一一种种顺顺序序存存储储结结构构,用用一一组组连连续续空空间间存存储储树树的的所所有有结结点点,同同时时在在每每个个结结点点中中附附设设一一个个伪伪指指针针指指示示其双亲结点的位置。其双亲结点的位置。树的双亲存储结构示意图树的双亲存储结构示意图双亲存储结构的类型定义如下：双亲存储结构的类型定义如下：typedef struct ElemType data;/结点的值结点的值 int parent;/指向双亲的位置指向双亲的位置 PTreeMaxSize;思考题：该存储结构的优缺点？思考题：该存储结构的优缺点？2.孩子链存储结构孩子链存储结构 孩孩子子链链存存储储结结构构可可按按树树的的度度(即即树树中中所所有有结结点点度度的的最最大大值值)设设计计结结点点的的孩孩子子结结点点指指针针域域个个数数。下下图图(a)的的树树对对应应的的孩孩子子链链存存储储结构如图结构如图(b)所示。所示。树的树的孩子链孩子链存储结构示意图存储结构示意图孩子链存储结构的结点类型定义如下：孩子链存储结构的结点类型定义如下：typedef struct node ElemType data;/结点的值结点的值 struct node*sonsMaxSons;/指向孩子结点指向孩子结点 TSonNode;其中，其中，MaxSons为最多的孩子结点个数。为最多的孩子结点个数。思考题：思考题：n个结点的个结点的m次树有多少个空指针域？次树有多少个空指针域？思考题：该存储结构的优缺点？思考题：该存储结构的优缺点？3.孩子兄弟链存储结构孩子兄弟链存储结构 孩孩子子兄兄弟弟链链存存储储结结构构是是为为每每个个结结点点设设计计三三个个域域：一一个个数数据据元元素素域域,一一个个该该结结点点的的第第一一个个孩孩子子结结点点指指针针域域,一一个个该该结结点点的下一个兄弟结点指针域。的下一个兄弟结点指针域。树的树的孩子兄弟链孩子兄弟链存储结构示意图存储结构示意图兄弟链存储结构中结点的类型定义如下：兄弟链存储结构中结点的类型定义如下：typedef struct tnode ElemType data;/结点的值结点的值 struct tnode*hp;/指向兄弟指向兄弟 struct tnode*vp;/指向孩子结点指向孩子结点 TSBNode;每个结点固定只有两个指针域。每个结点固定只有两个指针域。思考题：该存储结构的优缺点？思考题：该存储结构的优缺点？7.2.1 二叉树概念二叉树概念 二叉树是有限的结点集合。二叉树是有限的结点集合。这个集合或者是空。这个集合或者是空。或或者者由由一一个个根根结结点点和和两两棵棵互互不不相相交交的的称称为为左左子子树树和和右右子树的二叉树组成。子树的二叉树组成。注意：二叉树的定义是一种递归定义。注意：二叉树的定义是一种递归定义。7.2 二叉树概念和性质二叉树概念和性质 二叉树的五种基本形态：二叉树的五种基本形态：空树空树只含根结点只含根结点右子树为空树右子树为空树左子树为空树左子树为空树左右子树均左右子树均不为空树不为空树NNLRNLNR 从从定定义义看看到到,二二叉叉树树是是一一种种特特殊殊的的树树,其其表表示示法法也也与与树树的表示法一样：的表示法一样：树形表示法树形表示法 文氏图表示法文氏图表示法 凹入表示法凹入表示法 括号表示法括号表示法 在在一一棵棵二二叉叉树树中中,如如果果所所有有分分支支结结点点都都有有左左孩孩子子结结点点和和右右孩孩子子结结点点,并并且且叶叶结结点点都都集集中中在在二二叉叉树树的的最最下下一一层层,这这样样的的二二叉叉树树称为称为满二叉树满二叉树。下下图图所所示示就就是是一一棵棵满满二二叉叉树树。可可以以对对满满二二叉叉树树的的结结点点进进行行连连续续编编号号,约约定定编编号号从从树树根根为为1开开始始,按按照照层层数数从从小小到到大大、同同一一层层从从左左到到右右的的次次序序进进行行。图图中中每每个个结结点点外外边边的的数数字字为为对对该该结结点点的的编号。编号。若若二二叉叉树树中中最最多多只只有有最最下下面面两两层层的的结结点点的的度度数数可可以以小小于于2,并并且且最最下下面面一一层层的的叶叶结结点点都都依依次次排排列列在在该该层层最最左左边边的的位位置置上上,则则这样的二叉树称为这样的二叉树称为完全二叉树完全二叉树。如如下下图图所所示示为为一一棵棵完完全全二二叉叉树树。同同样样可可以以对对完完全全二二叉叉树树中中每每个个结结点点进进行行连连续续编编号号,编编号号的的方方法法同同满满二二叉叉树树相相同同。图图中中每每个个结结点外边的数字为对该结点的编号。点外边的数字为对该结点的编号。7.2.2 二叉树性质二叉树性质 性性质质1 非非空空二二叉叉树树上上叶叶结结点点数数等等于于双双分分支支结结点点数数加加1。证证明明：设设二二叉叉树树上上叶叶结结点点数数为为n0,单单分分支支结结点点数数为为n1,双双分分支支结结点点数数为为n2,则则总总结结点点数数=n0+n1+n2。在在一一棵棵二二叉叉树树中中,所所有有结结点点的的分分支支数数(即即度度数数)应应等等于于单单分分支支结结点点数数加加上上双双分分支支结结点点数数的的2倍倍,即总的分支数即总的分支数=n1+2n2。由由于于二二叉叉树树中中除除根根结结点点以以外外,每每个个结结点点都都有有唯唯一一的的一一个个分分支支指指向它向它,因此二叉树中有：总的分支数因此二叉树中有：总的分支数=总结点数总结点数-1。由上述三个等式可得：由上述三个等式可得：n1+2n2=n0+n1+n2-1即：即：n0=n2+1求解二叉树的节点个数问题：求解二叉树的节点个数问题：通常利用二叉树的性质通常利用二叉树的性质1，即，即n0=n2+1来求解这类问题，也常利用以下关系求解：来求解这类问题，也常利用以下关系求解：n=n0+n1+n2 度之和度之和=n-1 度之和度之和=n1+2n2所以有：所以有：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)求解方法归纳求解方法归纳例如，例如，已知一棵完全二叉树的第已知一棵完全二叉树的第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求解方法归纳求解方法归纳例如例如，一棵满二叉树中共有，一棵满二叉树中共有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 n/2，即即2in，则则编编号号为为i的的结结点点为为分分支支结结点点，否则为叶子结点。否则为叶子结点。（2）若若n为为奇奇数数,则则每每个个分分支支结结点点都都既既有有左左孩孩子子结结点点，也也有有右右孩孩子子结结点点；若若n为为偶偶数数，则则编编号号最最大大的的分分支支结结点点只只有有左左孩孩子子结结点点，没没有有右右孩孩子子结结点点，其其余余分分支支结结点点都都有有左左、右右孩孩子子结点。结点。i/2i2i2i+1 （3）若若编编号号为为i的的结结点点有有左左孩孩子子结结点点,则则左左孩孩子子结结点点的的编编号号为为2i；若若编编号号为为i的的结结点点有有右右孩孩子子结结点点,则则右右孩孩子子结结点点的的编编号号为为(2i+1)。（4）除除树树根根结结点点外外,若若一一个个结结点点的的编编号号为为i,则则它它的的双双亲亲结结点点的的编编号号为为 i/2,也也就就是是说说,当当i为为偶偶数数时时,其其双双亲亲结结点点的的编编号号为为i/2,它它是是双双亲亲结结点点的的左左孩孩子子结结点点,当当i为为奇奇数数时时,其其双双亲亲结结点点的的编编号为号为(i-1)/2,它是双亲结点的右孩子结点。它是双亲结点的右孩子结点。思考题：思考题：性质性质4的特点？的特点？性性质质5 具具有有n个个(n0)结结点点的的完完全全二二叉叉树树的的高高度度为为 log2n+1 或或 log2n+1。由完全二叉树的定义和树的性质由完全二叉树的定义和树的性质3可推出。可推出。7.2.3 二叉树与树、森林之间的转换二叉树与树、森林之间的转换1森林、树转换为二叉树森林、树转换为二叉树 步骤如下：步骤如下：（1）在在所所有有相相邻邻兄兄弟弟结结点点(森森林林中中每每棵棵树树的的根根结结点点可可看看成成是兄弟结点是兄弟结点)之间加一水平连线。之间加一水平连线。（2）对对每每个个非非叶叶结结点点k,除除了了其其最最左左边边的的孩孩子子结结点点外外,删删去去k与其他孩子结点的连线。与其他孩子结点的连线。（3）所有水平线段以左边结点为轴心顺时针旋转）所有水平线段以左边结点为轴心顺时针旋转45度。度。通过以上步骤通过以上步骤,原来的森林就转换为一棵二叉树。原来的森林就转换为一棵二叉树。一一般般的的树树是是森森林林中中的的特特殊殊情情况况,由由一一般般的的树树转转换换的的二二叉叉树树的的根根结结点点的的右右孩孩子子结结点点始始终终为为空空,原原因因是是一一般般的的树树的的根根结结点点不不存在兄弟结点和相邻的树。存在兄弟结点和相邻的树。ABCDEFGHII将森林转换为二叉树的过程将森林转换为二叉树的过程2.二叉树还原为森林、树二叉树还原为森林、树 步骤如下：步骤如下：（1）对对于于一一棵棵二二叉叉树树中中任任一一结结点点k0,沿沿着着k0的的左左孩孩子子结结点点k1的的右右子子树树方方向向搜搜索索所所有有右右孩孩子子结结点点,即即搜搜索索结结点点序序列列k2,k3,km,其其中中ki+1为为ki的的右右孩孩子子结结点点(1im),km没没有有右右孩孩子结点。子结点。（2）删去）删去k1,k2,km之间连线。之间连线。（3）若）若k1有双亲结点有双亲结点k,则连接则连接k与与ki(2im)。（4）将图形规整化）将图形规整化,使各结点按层次排列使各结点按层次排列。将一棵二叉树还原为树的过程将一棵二叉树还原为树的过程 例例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设计题：设计题：设计一棵二叉树，表示夫妻、父子和兄弟关系。设计一棵二叉树，表示夫妻、父子和兄弟关系。思考题：思考题：树树二叉树，二叉树二叉树，二叉树树树为什么没有讨论树的算法？为什么没有讨论树的算法？7.3.1 二叉树的顺序存储结构二叉树的顺序存储结构 二叉树的顺序存储结构中结点的存放次序是：二叉树的顺序存储结构中结点的存放次序是：对该树中每个结点进行编号对该树中每个结点进行编号,其编号从小到大的顺其编号从小到大的顺序就是结点存放在连续存储单元的先后次序。序就是结点存放在连续存储单元的先后次序。若把二叉树存储到一维数组中若把二叉树存储到一维数组中,则该编号就是下标值则该编号就是下标值加加1(注意注意,C/C+语言中数组的起始下标为语言中数组的起始下标为0)。树中各结点。树中各结点的编号与等高度的完全二叉树中对应位置上结点的编号相的编号与等高度的完全二叉树中对应位置上结点的编号相同。同。利用二叉树的性质利用二叉树的性质4。7.3 二叉树存储结构二叉树存储结构 顺序存储结构（不用下标为顺序存储结构（不用下标为0的元素）的元素）ABCDEF A B D C E F 1 2 3 4 5 6 7 8 9 10 11 12 13 142511437一般的二叉树先用空结点一般的二叉树先用空结点补全成为完全二叉树，然补全成为完全二叉树，然后对结点编号后对结点编号typedef ElemType SqBTreeMaxSize;7.3.2 二叉树的链式存储结构二叉树的链式存储结构 在二叉树的链接存储中在二叉树的链接存储中,结点的结构如下结点的结构如下:typedef struct node ElemType data;struct node*lchild,*rchild;BTNode;其其中中,data表表示示值值域域,用用于于存存储储对对应应的的数数据据元元素素,lchild和和rchild分分别别表表示示左左指指针针域域和和右右指指针针域域,用用于于分分别别存存储储左左孩孩子子结结点点和和右右孩子结点（即左、右子树的根结点）的存储位置。孩子结点（即左、右子树的根结点）的存储位置。二叉树及其链式存储结构：二叉链二叉树及其链式存储结构：二叉链 ABCDEGFABDGCEFb7.4.1 二叉树的基本运算概述二叉树的基本运算概述 归纳起来，二叉树有以下基本运算：归纳起来，二叉树有以下基本运算：（1）创创建建二二叉叉树树CreateBTNode(*b,*str)：根根据据二二叉叉树树括括号表示法的字符串号表示法的字符串*str生成对应的链式存储结构。生成对应的链式存储结构。（2）查查找找结结点点FindNode(*b,x)：在在二二叉叉树树b中中寻寻找找data域域值为值为x的结点，并返回指向该结点的指针。的结点，并返回指向该结点的指针。（3）找找孩孩子子结结点点LchildNode(p)和和Rchild-Node(p)：分分别别求二叉树中结点求二叉树中结点*p的左孩子结点和右孩子结点。的左孩子结点和右孩子结点。7.4 二叉树的基本运算及其实现二叉树的基本运算及其实现 （4）求求高高度度BTNodeDepth(*b)：求求二二叉叉树树b的的高高度度。若若二二叉叉树树为为空空，则则其其高高度度为为0；否否则则，其其高高度度等等于于左左子子树树与与右右子子树树中的最大高度加中的最大高度加l。（5）输输出出二二叉叉树树DispBTNode(*b)：以以括括号号表表示示法法输输出出一一棵二叉树。棵二叉树。7.4.2 二叉树的基本运算算法实现二叉树的基本运算算法实现 （1）创建二叉树）创建二叉树CreateBTNode(*b,*str)用用ch扫扫描描采采用用括括号号表表示示法法表表示示二二叉叉树树的的字字符符串串。分分以以下下几几种种情况：情况：若若ch=(：则则将将前前面面刚刚创创建建的的结结点点作作为为双双亲亲结结点点进进栈栈，并并置置k=1，表示其后创建的结点将作为这个结点的左孩子结点；，表示其后创建的结点将作为这个结点的左孩子结点；若若ch=)：表示栈中结点的左右孩子结点处理完毕，退栈；：表示栈中结点的左右孩子结点处理完毕，退栈；若若ch=,：表示其后创建的结点为右孩子结点；：表示其后创建的结点为右孩子结点；其他情况：其他情况：当当k=1时，表示这个结点作为栈中结点的左孩子结点；时，表示这个结点作为栈中结点的左孩子结点；当当k=2时时，表表示示这这个个结结点点作作为为栈栈中中结结点点的的右右孩孩子子结结点点。如如此循环直到此循环直到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,char*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=ch;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,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 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-lchild);/求左子树的高度为求左子树的高度为lchilddep rchilddep=BTNodeDepth(b-rchild);/求右子树的高度为求右子树的高度为rchilddep return(lchilddeprchilddep)?(lchilddep+1):(rchilddep+1);（5）输出二叉树）输出二叉树DispBTNode(*b)用括弧表示法输出二叉树。用括弧表示法输出二叉树。对对于于非非空空二二叉叉树树b，先先输输出出其其元元素素值值，当当存存在在左左孩孩子子结结点点或或右右孩孩子子结结点点时时，输输出出一一个个“(”符符号号，然然后后递递归归处处理理左左子子树树，输出一个输出一个“,”符号，递归处理右子树，最后输出一个符号，递归处理右子树，最后输出一个“)”符号。符号。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.1 二叉树遍历的概念二叉树遍历的概念 二二叉叉树树的的遍遍历历是是指指按按照照一一定定次次序序访访问问树树中中所所有有结结点点,并并且且每每个个结结点点仅仅被被访访问问一一次次的的过过程程。它它是是最最基基本的运算本的运算,是二叉树中所有其他运算的基础。是二叉树中所有其他运算的基础。7.5 二叉树的遍历二叉树的遍历1.先序遍历过程先序遍历过程先序遍历二叉树的过程是：先序遍历二叉树的过程是：l 访问根结点；访问根结点；l 先序遍历左子树；先序遍历左子树；l 先序遍历右子树。先序遍历右子树。ABCDEFGHK先序序列：先序序列：A B C D EHGKF2.中序遍历过程中序遍历过程中序遍历二叉树的过程是：中序遍历二叉树的过程是：l 中序遍历左子树；中序遍历左子树；l 访问根结点；访问根结点；l 中序遍历右子树。中序遍历右子树。ABCDEFGHK中序序列：中序序列：ABCDE H G K F3.后序遍历过程后序遍历过程后序遍历二叉树的过程是：后序遍历二叉树的过程是：l 后序遍历左子树；后序遍历左子树；l 后序遍历右子树；后序遍历右子树；l 访问根结点。访问根结点。ABCDEFGHK后序序列：后序序列：ABCDEHGKF7.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 445C 4D 4 555E 4 5G 4 5H 4 5K 4 5F 4 5递递归归算算法法执执行行时时系系统统栈栈的的变变化化递归算法执行过程：递归算法执行过程：中序遍历的递归算法：中序遍历的递归算法：