5树和二叉树解析优秀PPT.ppt

树和二叉树树和二叉树树和二叉树树和二叉树 预习检查预习检查v什么是二叉树v树的遍历有哪几种方式v树有那些应用2022/10/303 本章目标本章目标了解树的定义和基本术语 了解二叉树的定义、性质、和存储结构驾驭二叉树的遍历本章结构本章结构树的逻辑结构和存储结构树的逻辑结构和存储结构树和二叉树树和二叉树二叉树遍历二叉树2022/10/305 5 5.1.1.1.1树型结构实例树型结构实例树型结构实例树型结构实例 1 1家族树家族树家族树家族树 5-15-1 树的逻辑结构和存储结构树的逻辑结构和存储结构树的逻辑结构和存储结构树的逻辑结构和存储结构 图图图图5-15-1家族树家族树家族树家族树 2022/10/3062 2书的书目结构书的书目结构书的书目结构书的书目结构 图图图图5-2 5-2 5-2 5-2 书的书目书的书目书的书目书的书目 5-1 5-1 书的书目结构书的书目结构书的书目结构书的书目结构2022/10/3075.1.25.1.2树的定义树的定义树的定义树的定义 1 1树的定义树的定义树的定义树的定义 树树树树(Tree)(Tree)是是是是n(n0)n(n0)个结点的有限集个结点的有限集个结点的有限集个结点的有限集(记为记为记为记为T)T)，T T为空为空为空为空时称为空树，否则它满足以下两个条件：时称为空树，否则它满足以下两个条件：时称为空树，否则它满足以下两个条件：时称为空树，否则它满足以下两个条件：(1)(1)有且仅有一个结点没有前驱，称该结点为根结有且仅有一个结点没有前驱，称该结点为根结有且仅有一个结点没有前驱，称该结点为根结有且仅有一个结点没有前驱，称该结点为根结点点点点(Root)(Root)；(2)(2)除根结点以外，其余结点可分为除根结点以外，其余结点可分为除根结点以外，其余结点可分为除根结点以外，其余结点可分为m(m0)m(m0)个互不个互不个互不个互不相交的有限集合相交的有限集合相交的有限集合相交的有限集合T0T0，TlTl，Tm-1Tm-1。其中每个集合。其中每个集合。其中每个集合。其中每个集合又构成一棵树，树又构成一棵树，树又构成一棵树，树又构成一棵树，树T0T0，TlTl，Tm-1Tm-1被称为根结被称为根结被称为根结被称为根结点的子树点的子树点的子树点的子树(Subree)(Subree)。每棵子树的根结点有且仅有一个。每棵子树的根结点有且仅有一个。每棵子树的根结点有且仅有一个。每棵子树的根结点有且仅有一个干脆前驱，但可以有干脆前驱，但可以有干脆前驱，但可以有干脆前驱，但可以有0 0个或多个后继。个或多个后继。个或多个后继。个或多个后继。树的逻辑结构表示数据之间的关系是一对多，或树的逻辑结构表示数据之间的关系是一对多，或树的逻辑结构表示数据之间的关系是一对多，或树的逻辑结构表示数据之间的关系是一对多，或者多对一的关系。它的结构特点具有明显的层次关者多对一的关系。它的结构特点具有明显的层次关者多对一的关系。它的结构特点具有明显的层次关者多对一的关系。它的结构特点具有明显的层次关系，是一种特殊重要的非线性的数据结构。系，是一种特殊重要的非线性的数据结构。系，是一种特殊重要的非线性的数据结构。系，是一种特殊重要的非线性的数据结构。5-15-1 树的逻辑结构和存储结构树的逻辑结构和存储结构树的逻辑结构和存储结构树的逻辑结构和存储结构 2022/10/308图图图图5-35-3树的示例树的示例树的示例树的示例 图图图图5-3(a)5-3(a)是一棵只有一个根结点的树；是一棵只有一个根结点的树；是一棵只有一个根结点的树；是一棵只有一个根结点的树；图图图图5-35-3(b)(b)是是是是一一一一棵棵棵棵有有有有1212个个个个结结结结点点点点的的的的树树树树，即即即即T=AT=A，B B，C C，KK，LL。A A是是是是棵棵棵棵根根根根，除除除除根根根根结结结结点点点点A A之之之之外外外外，其其其其余余余余的的的的1111个个个个结结结结点点点点分分分分为为为为三三三三个个个个互互互互不不不不相相相相交交交交的的的的集集集集合合合合。T1T1T1T1，T2T2T2T2和和和和T3T3T3T3是是是是根根根根A A A A的的的的三三三三棵棵棵棵子子子子树树，且且且且本本本本身身身身又又又又都都都都是是是是一一一一棵棵棵棵树树。所以树的所以树的所以树的所以树的定义定义是递归的是递归的是递归的是递归的 。2022/10/3092 2 2 2树树的基本的基本的基本的基本术语术语 树树的的的的结结点包含一个数据元素及若干指向其子点包含一个数据元素及若干指向其子点包含一个数据元素及若干指向其子点包含一个数据元素及若干指向其子树树的分支。的分支。的分支。的分支。1.1.1.1.树树的的的的结结点点点点:包含一个包含一个包含一个包含一个DEDEDEDE和指向其子和指向其子和指向其子和指向其子树树的全部分支的全部分支的全部分支的全部分支;2.2.2.2.结结点的度点的度点的度点的度:一个一个一个一个结结点点点点拥拥有的子有的子有的子有的子树树个数个数个数个数,度度度度为为零的零的零的零的结结点称点称点称点称为为叶叶叶叶结结点点点点;3.3.3.3.树树的度的度的度的度:树树中全部中全部中全部中全部结结点的度的最大点的度的最大点的度的最大点的度的最大值值 Max(D(I)Max(D(I)Max(D(I)Max(D(I)含含含含义义:树树中最大分支数中最大分支数中最大分支数中最大分支数为树为树的度的度的度的度;4.4.4.4.结结点点点点的的的的层层次次次次及及及及树树的的的的深深深深度度度度:根根根根为为第第第第一一一一层层,根根根根的的的的孩孩孩孩子子子子为为其其其其次次次次层层,若若若若某某某某结结点点点点为为第第第第k k k k层层,则则其孩子其孩子其孩子其孩子为为k+1k+1k+1k+1层层.树树中中中中结结点的最大点的最大点的最大点的最大层层次称次称次称次称为树为树的深度或高度的深度或高度的深度或高度的深度或高度5.5.5.5.森林森林森林森林:是是是是m(m=0)m(m=0)m(m=0)m(m=0)棵互不相的棵互不相的棵互不相的棵互不相的树树的集合的集合的集合的集合 森林与森林与森林与森林与树树概念相近概念相近概念相近概念相近,相互很相互很相互很相互很简洁转换简洁转换.6 6 6 6.有有有有序序序序树树、无无无无序序序序树树 假假假假如如如如树树中中中中每每每每棵棵棵棵子子子子树树从从从从左左左左向向向向右右右右的的的的排排排排列列列列拥拥有有有有确确确确定定定定的的的的依次，不得互依次，不得互依次，不得互依次，不得互换换，则则称称称称为为有序有序有序有序树树，否，否，否，否则则称称称称为为无序无序无序无序树树。2022/10/30107.7.森林森林:是是m m（m0m0）棵互不相交的树的集合。）棵互不相交的树的集合。在树结构中，结点之间的关系又可以用家族关系描述，定义如下：在树结构中，结点之间的关系又可以用家族关系描述，定义如下：8.8.孩子、双亲孩子、双亲:结点子树的根称为这个结点的孩子，而这个结点又结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。被称为孩子的双亲。9.9.子孙子孙:以某结点为根的子树中的全部结点都被称为是该结点的子以某结点为根的子树中的全部结点都被称为是该结点的子孙。孙。10.10.祖先祖先:从根结点到该结点路径上的全部结点。从根结点到该结点路径上的全部结点。11.11.兄弟兄弟:同一个双亲的孩子之间互为兄弟。同一个双亲的孩子之间互为兄弟。12.12.堂兄弟堂兄弟:双亲在同一层的结点互为堂兄弟。双亲在同一层的结点互为堂兄弟。2022/10/30113.3.树的基本运算树的基本运算树的基本运算树的基本运算树的基本运算主要有：树的基本运算主要有：树的基本运算主要有：树的基本运算主要有：初始化操作初始化操作初始化操作初始化操作INITIATE(T)INITIATE(T)：创建一棵空树。：创建一棵空树。：创建一棵空树。：创建一棵空树。求求求求根根根根函函函函数数数数ROOT(T)ROOT(T)：求求求求树树树树T T的的的的根根根根；ROOT(X)ROOT(X)：求求求求结结结结点点点点x x所在树的根。所在树的根。所在树的根。所在树的根。求双亲函数求双亲函数求双亲函数求双亲函数PARENT(T,x)PARENT(T,x)：在树：在树：在树：在树T T中求中求中求中求x x的双亲。的双亲。的双亲。的双亲。求求求求第第第第i i个个个个孩孩孩孩子子子子函函函函数数数数CHILD(T,x,i)CHILD(T,x,i)：在在在在树树树树T T中中中中求求求求结结结结点点点点x x的的的的第第第第i i个孩子。个孩子。个孩子。个孩子。建建建建树树树树函函函函数数数数CRT-TREE(x,F)CRT-TREE(x,F)：建建建建立立立立以以以以结结结结点点点点x x为为为为根根根根，森森森森林林林林F F为为为为子树的树。子树的树。子树的树。子树的树。6.6.遍历树操作遍历树操作遍历树操作遍历树操作TRAVERSE(T)TRAVERSE(T)：按依次访问树：按依次访问树：按依次访问树：按依次访问树T T中各个结点。中各个结点。中各个结点。中各个结点。2022/10/30121 1树的遍历树的遍历树的遍历树的遍历 所所所所谓谓谓谓树树树树的的的的遍遍遍遍历历历历，就就就就是是是是依依依依据据据据某某某某种种种种依依依依次次次次依依依依次次次次访访访访问问问问树树树树中中中中各各各各个个个个结结结结点点点点，并并并并使使使使得得得得每每每每个个个个结结结结点点点点只只只只被被被被访访访访问问问问一一一一次次次次。也也也也就就就就是是是是把把把把非非非非线线线线性性性性结结结结构构构构的的的的树树树树结结结结点点点点变变变变成成成成线线线线性序列的一种方式性序列的一种方式性序列的一种方式性序列的一种方式。树树树树的的的的遍遍遍遍历历历历可可可可以以以以按按按按深深深深度度度度优优优优先先先先遍遍遍遍历历历历，也也也也可可可可以以以以依依依依据据据据广广广广度度度度优优优优先先先先（按按按按层层层层次次次次）遍历。深度优先遍历通常有两种方式：前序遍历和后序遍历。遍历。深度优先遍历通常有两种方式：前序遍历和后序遍历。遍历。深度优先遍历通常有两种方式：前序遍历和后序遍历。遍历。深度优先遍历通常有两种方式：前序遍历和后序遍历。(1)(1)前序遍历的递归定义：前序遍历的递归定义：前序遍历的递归定义：前序遍历的递归定义：若树若树若树若树T T非空，则：非空，则：非空，则：非空，则：访问根结点访问根结点访问根结点访问根结点R R；依依依依据据据据从从从从左左左左到到到到右右右右的的的的依依依依次次次次依依依依次次次次前前前前序序序序遍遍遍遍历历历历根根根根结结结结点点点点R R的的的的各各各各子子子子树树树树T1T1，T2T2，TkTk。5-1-55-1-5 树的遍历树的遍历树的遍历树的遍历2022/10/3013(2)(2)后序遍历的递归定义：后序遍历的递归定义：后序遍历的递归定义：后序遍历的递归定义：若树若树若树若树T T非空，则：非空，则：非空，则：非空，则：依依依依据据据据从从从从左左左左到到到到右右右右的的的的依依依依次次次次依依依依次次次次后后后后序序序序遍遍遍遍历历历历根根根根T T的的的的各各各各子子子子树树树树TlTl，T2T2，TkTk；访问根结点访问根结点访问根结点访问根结点R R。(3)(3)广度优先（按层）遍历广度优先（按层）遍历广度优先（按层）遍历广度优先（按层）遍历广广广广度度度度优优优优先先先先（按按按按层层层层次次次次）遍遍遍遍历历历历定定定定义义义义为为为为：先先先先访访访访问问问问第第第第一一一一层层层层结结结结点点点点（即即即即树树树树根根根根结结结结点点点点），再再再再从从从从左左左左至至至至右右右右访访访访问问问问其其其其次次次次层层层层结结结结点点点点，依依依依次次次次按按按按层层层层访访访访问问问问，直直直直到到到到树树树树中中中中结结结结点点点点全全全全部部部部被被被被访访访访问问问问为为为为止止止止。对对对对图图图图6-66-6(a)(a)中中中中的的的的树树树树进进进进行行行行按按按按层层层层次次次次遍遍遍遍历历历历得得得得到到到到树树树树的广度优先遍历序列为：的广度优先遍历序列为：的广度优先遍历序列为：的广度优先遍历序列为：ABCDEFGABCDEFG。说明：说明：说明：说明：前前前前序序序序遍遍遍遍历历历历一一一一棵棵棵棵树树树树恰恰恰恰好好好好等等等等价价价价于于于于前前前前序序序序遍遍遍遍历历历历该该该该树树树树所所所所对对对对应应应应的的的的二二二二叉叉叉叉树树树树。（6.26.2节将介绍二叉树）节将介绍二叉树）节将介绍二叉树）节将介绍二叉树）后序遍历树恰好等价于中序遍历该树所对应的二叉树。后序遍历树恰好等价于中序遍历该树所对应的二叉树。后序遍历树恰好等价于中序遍历该树所对应的二叉树。后序遍历树恰好等价于中序遍历该树所对应的二叉树。2022/10/3014树的先序遍历算法描述如下：树的先序遍历算法描述如下：树的先序遍历算法描述如下：树的先序遍历算法描述如下：void Preorder(Btree*root)/先根遍历先根遍历k叉树叉树 if(root!=NULL)printf(“%cn”,root-data);/访问访问根根结结点点for(i=0;iti);/递归递归前序遍前序遍历历每一个子每一个子结结点点 2022/10/30155.2.15.2.1二叉树的定义与性质二叉树的定义与性质二叉树的定义与性质二叉树的定义与性质 二叉树二叉树二叉树二叉树(BinaryTree)(BinaryTree)是另一种重要的树型结构。是另一种重要的树型结构。是另一种重要的树型结构。是另一种重要的树型结构。是度为是度为是度为是度为2 2的有序树，它的特点是每个结点至多有两棵的有序树，它的特点是每个结点至多有两棵的有序树，它的特点是每个结点至多有两棵的有序树，它的特点是每个结点至多有两棵子树。和树结构的定义类似，二叉树的定义也可以子树。和树结构的定义类似，二叉树的定义也可以子树。和树结构的定义类似，二叉树的定义也可以子树。和树结构的定义类似，二叉树的定义也可以用递归形式给出。用递归形式给出。用递归形式给出。用递归形式给出。1 1二叉树的递归定义二叉树的递归定义二叉树的递归定义二叉树的递归定义 二叉树二叉树二叉树二叉树(BinaryTree)(BinaryTree)是是是是n(n0)n(n0)个结点的有限集。它个结点的有限集。它个结点的有限集。它个结点的有限集。它或者是空集或者是空集或者是空集或者是空集(n=0)(n=0)，或者同时满足以下两个条件：，或者同时满足以下两个条件：，或者同时满足以下两个条件：，或者同时满足以下两个条件：(1)(1)有且仅有一个根结点；有且仅有一个根结点；有且仅有一个根结点；有且仅有一个根结点；(2)(2)其余的结点分成两棵互不相交的左子树和右子其余的结点分成两棵互不相交的左子树和右子其余的结点分成两棵互不相交的左子树和右子其余的结点分成两棵互不相交的左子树和右子树。树。树。树。5-25-2 二叉树二叉树二叉树二叉树2022/10/3016 二二叉叉树树与与树树有有区区分分：树树至至少少应应有有一一个个结结点点，而而二二叉叉树树可可以以为为空空；树树的的子子树树没没有有依依次次，但但假假如如二二叉叉树树的的根根结结点点只只有有一一棵棵子子树树，必必需需明明确确区区分分它它是是左左子子树树还还是是右右子子树树，因因为为两两者者将将构构成成不不同同形形态态的的二二叉叉树树。因因此此，二二叉叉树树不不是是树树的的特特例例。它它们们是是两两种种不不同同的的数数据据结构。结构。二叉树有二叉树有5 5种基本形态：种基本形态：图图图图5-75-7二叉树的五种基本形态二叉树的五种基本形态二叉树的五种基本形态二叉树的五种基本形态(a)a)a)a)空二叉树空二叉树空二叉树空二叉树 (b)b)b)b)只有根结点的二叉树只有根结点的二叉树只有根结点的二叉树只有根结点的二叉树(c)c)c)c)右子树为空的二叉树右子树为空的二叉树右子树为空的二叉树右子树为空的二叉树 (d)d)左子树为空的二叉树左子树为空的二叉树左子树为空的二叉树左子树为空的二叉树(e)e)左右子树均不为空的二叉树左右子树均不为空的二叉树左右子树均不为空的二叉树左右子树均不为空的二叉树 2022/10/3017两种特殊形两种特殊形态的二叉的二叉树：满二叉二叉树和完全二叉和完全二叉树。(1)(1)满二叉二叉树(FullBinaryTree)(FullBinaryTree)深度深度为k k，且有，且有2k-12k-1个个结点的二叉点的二叉树。特点：（特点：（1 1）每一）每一层上上结点数都达到最大点数都达到最大 （2 2）度）度为1 1的的结点点n1=0n1=0，树叶都在最下一叶都在最下一层上。上。结点点层序序编号号方方法法：从从根根结点点起起从从上上到到下下逐逐层（层内内从从左左到到右右）对二二叉叉树的的结点点进行行连续编号。号。1237654K=3n=23-1=7 满二叉树2022/10/3018 (2)(2)完全二叉树完全二叉树(Complete BinaryTree)Complete BinaryTree)深度为深度为k k，结点数为结点数为n n的二叉树，当且仅当每个结点的编号都与相同深的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从度的满二叉树中从1 1到到n n的结点一一对应时，称为完全二叉树。的结点一一对应时，称为完全二叉树。图图5-8 5-8 完全二叉树完全二叉树完全二叉树的特点：完全二叉树的特点：（1 1）每每个个结结点点i i的的左左子子树树的的深深度度Lhi-Lhi-其其结结点点i i的的右右子子树树的的深深度度RhiRhi等等于于0 0或或1 1，即叶结点只可能出现在层次最大或次最大的两层上。，即叶结点只可能出现在层次最大或次最大的两层上。（2 2）完全二叉树结点数）完全二叉树结点数n n满足满足2k-1-12k-1-1n2k-1 n2k-1（3 3）满二叉树确定是完全二叉树，反之不成立。）满二叉树确定是完全二叉树，反之不成立。452132022/10/30191324653241LH1=3RH1=1LH1-RH1=2 非完全二叉树非完全二叉树非完全二叉树非完全二叉树LHLH2 2=0=0RHRH2 2=1=1LH2-RH2=0-1=-12022/10/30202 2 2 2二叉树的性质二叉树的性质二叉树的性质二叉树的性质 性质性质性质性质1 1 1 1 在二叉树的第在二叉树的第在二叉树的第在二叉树的第i i i i层上至多有层上至多有层上至多有层上至多有2i-1 2i-1 2i-1 2i-1 个结点个结点个结点个结点(i1)(i1)(i1)(i1)。性质性质性质性质2 2 2 2 深度为深度为深度为深度为k k k k的二叉树至多有的二叉树至多有的二叉树至多有的二叉树至多有2k-12k-12k-12k-1个结点个结点个结点个结点(k1)(k1)(k1)(k1)。（深度确定，二叉树的最大结点数也确定）（深度确定，二叉树的最大结点数也确定）（深度确定，二叉树的最大结点数也确定）（深度确定，二叉树的最大结点数也确定）性质性质性质性质3 3 3 3 二叉树中二叉树中二叉树中二叉树中,终端结点数终端结点数终端结点数终端结点数n0n0n0n0与度为与度为与度为与度为2 2 2 2的结点数的结点数的结点数的结点数n2n2n2n2有如下关系有如下关系有如下关系有如下关系:n0=n2+1 n0=n2+1 n0=n2+1 n0=n2+1 性质性质性质性质4 4 4 4 结点数为结点数为结点数为结点数为n n n n的完全二叉树，其深度为的完全二叉树，其深度为的完全二叉树，其深度为的完全二叉树，其深度为 log2nlog2nlog2nlog2n +l +l +l +l 性性性性质质质质5 5 5 5 在在在在按按按按层层层层序序序序编编编编号号号号的的的的n n n n个个个个结结结结点点点点的的的的完完完完全全全全二二二二叉叉叉叉树树树树中中中中，随随随随意意意意一一一一结结结结点点点点i(1in)i(1in)i(1in)i(1in)有：有：有：有：i=1i=1i=1i=1时时时时，结结结结点点点点i i i i是是是是树树树树的的的的根根根根；否否否否则则则则，结结结结点点点点i i i i的的的的双双双双亲亲亲亲为为为为结结结结点点点点 i/2 i/2 i/2 i/2 (i1)(i1)(i1)(i1)。2i2i2i2in n n n时时时时，结结结结点点点点i i i i无无无无左左左左孩孩孩孩子子子子，为为为为叶叶叶叶结结结结点点点点；否否否否则则则则，结结结结点点点点i i i i的的的的左左左左孩孩孩孩子子子子为为为为结结结结点点点点2i2i2i2i。2i+1 2i+1 2i+1 2i+1n n n n时，结点时，结点时，结点时，结点i i i i无右孩子；否则，结点无右孩子；否则，结点无右孩子；否则，结点无右孩子；否则，结点i i i i的右孩子为结点的右孩子为结点的右孩子为结点的右孩子为结点2i+12i+12i+12i+1。2022/10/3021链式存储结构链式存储结构链式存储结构链式存储结构 （二叉链表）二叉链表）设计不同的结点结构，可以构成不同的链式存储结构。常用的有：设计不同的结点结构，可以构成不同的链式存储结构。常用的有：二叉链表二叉链表 三叉链表三叉链表 线索链表线索链表 用空链域存放指向前驱或后继的线索用空链域存放指向前驱或后继的线索2022/10/3022 由由于于二二叉叉树树每每个个结结点点至至多多只只有有2个个孩孩子子，分分别别为为左左孩孩子子和和右右孩孩子子。因因此此可可以以把把每每个个结结点点分分成成三三个个域域：一一个个域域存存放放结结点点本本身身的的信信息息，另另外外两两个个是是指针域，分别存放左、右孩子的地址。每个结点的结构表示为：指针域，分别存放左、右孩子的地址。每个结点的结构表示为：其其中中左左链链域域lchildlchild为为指指向向左左孩孩子子的的指指针针，右右链链域域rchildrchild为为指指向向右右孩孩子子的的指指针针，数数据据域域datadata表表示示结结点点的的值值。若若某某结结点点没没有有左左孩孩子子或或右右孩孩子子，其其相应的链域为空指针。相应的链域为空指针。对应的结构类型定义如下：对应的结构类型定义如下：对应的结构类型定义如下：对应的结构类型定义如下：typedef struct nodetypedef struct node ElemType data;ElemType data;struct node*lchild;struct node*lchild;struct node*rchild;struct node*rchild;BTree,*tree;BTree,*tree;其中，其中，其中，其中，treetree是指向根结点的指针。是指向根结点的指针。是指向根结点的指针。是指向根结点的指针。2022/10/3023二叉链表的结点结构二叉链表的结点结构 lchild data rchildD 二叉树二叉树CEBAACBDE二叉链表二叉链表说明：说明：说明：说明：一一一一个个个个二二二二叉叉叉叉链链链链表表表表由由由由根根根根指指指指针针针针rootrootrootroot唯唯唯唯一一一一确确确确定定定定。若若若若二二二二叉叉叉叉树树树树为为为为空空空空，则则则则root=NULLroot=NULLroot=NULLroot=NULL；若若若若结点的某个孩子不存在，则相应的指针为空。结点的某个孩子不存在，则相应的指针为空。结点的某个孩子不存在，则相应的指针为空。结点的某个孩子不存在，则相应的指针为空。具具具具有有有有n n个个个个结结结结点点点点的的的的二二二二叉叉叉叉链链链链表表表表中中中中，共共共共有有有有2 2n n个个个个指指指指针针针针域域域域。其其其其中中中中只只只只有有有有n-1n-1个个个个用用用用来来来来指指指指示示示示结点的左、右孩子，其余的结点的左、右孩子，其余的结点的左、右孩子，其余的结点的左、右孩子，其余的n+1n+1个指针域为空。个指针域为空。个指针域为空。个指针域为空。2022/10/3024 lchild data parent rchildD 二叉树二叉树CEBAACBDE三叉链表三叉链表3 3带带双双双双亲亲指指指指针针的二叉的二叉的二叉的二叉链链表表表表 由由由由于于于于常常常常常常常常要要要要在在在在二二二二叉叉叉叉树树中中中中找找找找寻寻某某某某结结点点点点的的的的双双双双亲亲时时，可可可可在在在在每每每每个个个个结结点点点点上上上上再再再再加加加加一一一一个个个个指指指指向向向向其其其其双双双双亲亲的指的指的指的指针针parentparent，形成一个，形成一个，形成一个，形成一个带带双双双双亲亲指指指指针针的二叉的二叉的二叉的二叉链链表。就是三叉表。就是三叉表。就是三叉表。就是三叉链链表。表。表。表。三叉三叉三叉三叉链链表的表的表的表的结结点点点点结结构构构构性质性质性质性质6 6 6 6 含有含有含有含有n n n n个结点的二叉链表中，有个结点的二叉链表中，有个结点的二叉链表中，有个结点的二叉链表中，有n+1n+1n+1n+1个空链域。个空链域。个空链域。个空链域。二叉树存储方法的选择，主要依靠于所要实施的各种运算的频度。二叉树存储方法的选择，主要依靠于所要实施的各种运算的频度。二叉树存储方法的选择，主要依靠于所要实施的各种运算的频度。二叉树存储方法的选择，主要依靠于所要实施的各种运算的频度。2022/10/30251 1 1 1二叉树的基本运算二叉树的基本运算二叉树的基本运算二叉树的基本运算（1 1 1 1）Inittree(&T)Inittree(&T)Inittree(&T)Inittree(&T)功能：初始化操作功能：初始化操作功能：初始化操作功能：初始化操作(建立一棵空的二叉树建立一棵空的二叉树建立一棵空的二叉树建立一棵空的二叉树)。（2 2 2 2）Root(T)Root(T)Root(T)Root(T)功能：求二叉树的根。功能：求二叉树的根。功能：求二叉树的根。功能：求二叉树的根。（3 3 3 3）Parent(T,x)Parent(T,x)Parent(T,x)Parent(T,x)功能：求二叉树功能：求二叉树功能：求二叉树功能：求二叉树T T T T中值为中值为中值为中值为x x x x的结点的双亲。的结点的双亲。的结点的双亲。的结点的双亲。（4 4 4 4）Lchild(T,x)Lchild(T,x)Lchild(T,x)Lchild(T,x)功能：求结点的左孩子。功能：求结点的左孩子。功能：求结点的左孩子。功能：求结点的左孩子。（5 5 5 5）Rchild(T,x)Rchild(T,x)Rchild(T,x)Rchild(T,x)功能：求结点的右孩子。功能：求结点的右孩子。功能：求结点的右孩子。功能：求结点的右孩子。（6 6 6 6）Traverse(T)Traverse(T)Traverse(T)Traverse(T)功能：遍历或访问二叉树功能：遍历或访问二叉树功能：遍历或访问二叉树功能：遍历或访问二叉树T T T T。（7 7 7 7）creatree(&T)creatree(&T)creatree(&T)creatree(&T)功能：创建二叉树功能：创建二叉树功能：创建二叉树功能：创建二叉树T T T T5-2-35-2-3 二叉树的基本运算节实现二叉树的基本运算节实现二叉树的基本运算节实现二叉树的基本运算节实现2022/10/3026 2 2二叉树部分运算的算法描述二叉树部分运算的算法描述二叉树部分运算的算法描述二叉树部分运算的算法描述 (1)(1)创建二叉树创建二叉树创建二叉树创建二叉树creatree(&root,str)creatree(&root,str)：功能：创建二叉树功能：创建二叉树T T。算法描述如下：算法描述如下：voidcreatree(BTree*b,char*str)BTree*stackMAXSIZE,p=NULL;inttop=-1,k,j=0;charch;*b=NULL;ch=strj;while(ch!=0)switch(ch)case(：top+;stacktop=p;k=1,break;/为左结点为左结点case)：top-;break;case,：k=2;break;/为右结点为右结点default：p=(BTree*)malloc(sizeof(BTree);p-data=ch;p-lchild=p-rchild=NULL;2022/10/3027p-data=ch;p-lchild=p-rchild=NULL;if(*b=NULL)/为根结点为根结点*b=p;elseswitch(k)case1：stacktop-lchild=p;break;case2：stacktop-rchild=p;break;j+;ch=strj;2022/10/3028(2)(2)查找给定的结点查找给定的结点find(root(root，x)x)(3)(3)找左孩子结点找左孩子结点找左孩子结点找左孩子结点lchild(p)lchild(p)或右孩子结点或右孩子结点或右孩子结点或右孩子结点rchild(p)rchild(p)(4)(4)输出二叉树输出二叉树输出二叉树输出二叉树disptree(root)disptree(root)2022/10/30295.3.15.3.15.3.15.3.1遍历二叉树遍历二叉树遍历二叉树遍历二叉树 在在在在二二二二叉叉叉叉树树树树的的的的一一一一些些些些应应应应用用用用中中中中，常常常常常常常常要要要要求求求求在在在在树树树树中中中中查查查查找找找找具具具具有有有有某某某某种种种种特特特特征征征征的的的的结结结结点点点点，或或或或者者者者对对对对树树树树中中中中全全全全部部部部结结结结点点点点逐逐逐逐一一一一进进进进行行行行某某某某种种种种处处处处理理理理。这这这这就就就就引引引引入入入入了了了了遍遍遍遍历历历历二二二二叉叉叉叉树树树树的的的的问问问问题题题题，即即即即如如如如何何何何按按按按某某某某条条条条搜搜搜搜寻寻寻寻路路路路径径径径访访访访问问问问树树树树中中中中的每一个结点，使得每一个结点仅切仅被访问一次。的每一个结点，使得每一个结点仅切仅被访问一次。的每一个结点，使得每一个结点仅切仅被访问一次。的每一个结点，使得每一个结点仅切仅被访问一次。遍遍遍遍历历历历二二二二叉叉叉叉树树树树：指指指指按按按按确确确确定定定定的的的的规规规规律律律律对对对对二二二二叉叉叉叉树树树树的的的的每每每每个个个个结结结结点点点点，访访访访问且仅访问一次的处理过程。问且仅访问一次的处理过程。问且仅访问一次的处理过程。问且仅访问一次的处理过程。遍遍遍遍历历历历对对对对线线线线性性性性结结结结构构构构是是是是简简简简洁洁洁洁解解解解决决决决的的的的。而而而而二二二二叉叉叉叉树树树树是是是是非非非非线线线线性性性性的的的的，因因因因而而而而须须须须要要要要找找找找寻寻寻寻一一一一种种种种规规规规律律律律，使使使使二二二二叉叉叉叉树树树树上上上上的的的的结结结结点点点点能能能能排排排排列列列列在在在在一一一一个个个个线线线线性队列上，从而便于遍历。性队列上，从而便于遍历。性队列上，从而便于遍历。性队列上，从而便于遍历。5-35-3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树遍历二叉树和线索二叉树遍历二叉树和线索二叉树 2022/10/3030 访访问问是是一一种种抽抽象象操操作作，是是对对结结点点的的某某种种处处理理，例例如如可可以以是是求求结结点的度、或层次、打印结点的信息，或做其他任何工作。点的度、或层次、打印结点的信息，或做其他任何工作。一一次次遍遍历历后后，使使树树中中结结点点的的非非线线性性排排列列，按按访访问问的的先先后后依依次次变变为某种线性排列。为某种线性排列。遍遍历历的的次次序序：假假如如以以L L、D D、R R分分别别表表示示遍遍历历左左子子树树、遍遍历历根根结结点点和和遍遍历历右右子子树树，遍遍历历整整个个二二叉叉树树则则有有DLRDLR、LDRLDR、LRDLRD、DRLDRL、RDLRDL、RLDRLD六六种种遍遍历历方方案案。若若规规定定先先左左后后右右，则则只只有有前前三三种种状状况况，分分别别规规定为：定为：DLR DLR先（根）序遍历，先（根）序遍历，LDR LDR中（根）序遍历，中（根）序遍历，LRD LRD后（根）序遍历。后（根）序遍历。1 1遍历方案遍历方案 LDR LDR 中序遍历；中序遍历；LRD LRD 后序遍历；后序遍历；DLR DLR 先序遍历先序遍历2022/10/30311 1）中序遍历二叉树）中序遍历二叉树算法思想算法思想:若二叉树非空，则：若二叉树非空，则：1）中序遍历左子树）中序遍历左子树2）访问根结点）访问根结点3）中序遍历右子树）中序遍历右子树算法描述算法描述:voidInorder(BiTreebt)/bt为根结点指针为根结点指针if(bt)/根非空根非空Inorder(bt-lchild);visit(bt-data)visit(bt-data)；Inorder(bt-rchild);2 2）后序遍历二叉树）后序遍历二叉树算法思想算法思想:若二叉树非空，则：若二叉树非空，则：1）后序遍历左子树）后序遍历左子树2）后序遍历右子树）后序遍历右子树3）访问根结点）访问根结点算法描述算法描述:voidPostorder(BiTreebt)/bt为根结点指针为根结点指针if(bt)Postorder(bt-lchild);Postorder(bt-rchild);visit(bt-data)visit(bt-data)；2022/10/30323 3）先序遍历二叉树）先序遍历二叉树算法思想算法思想:若二叉树非空，则：若二叉树非空，则：1）访问根结点）访问根结点2）先序遍历左子树）先序遍历左子树3）先序遍历右子树）先序遍历右子树算法描述算法描述:voidPreorder(BiTreebt)/bt为根结点指针为根结点指针if(bt)/根非空根非空visit(bt-data)visit(bt-data)；Preorder(bt-lchild);Preorder(bt-rchild);例：表达式例：表达式a+b(c-d)-e/facdefb+遍历结果遍历结果:中序中序:a+bc-d-e/f后序后序:abcd-+ef/-先序先序:-+ab-cd/ef2022/10/3033（1 1 1 1）先序遍历的递归算法如下（假定结点的元素值为字符型）：）先序遍历的递归算法如下（假定结点的元素值为字符型）：）先序遍历的递归算法如下（假定结点的元素值为字符型）：）先序遍历的递归算法如下（假定结点的元素值为字符型）：#include stdio.h#include stdio.h#include stdio.h#include stdio.htypedef char ElemType;typedef char ElemType;typedef char ElemType;typedef char ElemType;typedef struct node /typedef struct node /typedef struct node /typedef struct node /定义链表结构定义链表结构定义链表结构定义链表结构 ElemType data;/ElemType data;/ElemType data;/ElemType da