数据结构树和二叉树实用课件.ppt

数据结构PPT树和二叉树数据结构PPT树和二叉树6.1 树的定义和基本术语树的定义和基本术语v 什么是树？什么是树？树是由树是由 n(n 0)个结点的有限集合。如果个结点的有限集合。如果 n=0，称为空树；如果称为空树；如果 n 0，则则 有且仅有一个特定的称之为根有且仅有一个特定的称之为根(Root)的结点，它只有直的结点，它只有直接后继，但没有直接前驱；接后继，但没有直接前驱；当当n 1，除根以外的其它结点划分为除根以外的其它结点划分为 m(m 0)个互不个互不相交的有限集相交的有限集 T1,T2,Tm，其中每个集合本身又是其中每个集合本身又是一棵树，并且称为根的子树一棵树，并且称为根的子树(SubTree)。T=A，B，C，D，E，F，G，H，I，J，K，L，MA是根，其余结点可以划分为是根，其余结点可以划分为3个互不相交的集合：个互不相交的集合：T1=B，E，F，K，L T2=C，G T3=D，H，I，J，M 这些集合中的每一集合都本身又是一棵树，它们是这些集合中的每一集合都本身又是一棵树，它们是A的子树。的子树。对于对于T1，B是根，其余结点可以划分为是根，其余结点可以划分为2个互不相交的集合：个互不相交的集合：T11=E，K，L T12=F T11，T12是是B的子树。的子树。HBAJFEDKLCMIGq 树的示例树的示例1.树中只有根结点没有前趋；树中只有根结点没有前趋；2.除根外，其余结点都有且仅一个前趋；除根外，其余结点都有且仅一个前趋；3.树的结点，可以有零个或多个后继；树的结点，可以有零个或多个后继；4.除根外的其它结点，都存在唯一条从除根外的其它结点，都存在唯一条从根到该结点的路径；根到该结点的路径；5.树是一种分支结构。树是一种分支结构。HBAJFEDKLCMIGq 树的逻辑结构特点树的逻辑结构特点 树可表示具有分支结构关系的对象树可表示具有分支结构关系的对象例例1.家族族谱家族族谱 设某家庭有设某家庭有13个成员个成员A、B、C、D、E、F、G、H、I、J、K、L、M，他们之间的关系可如图所示的树表示。他们之间的关系可如图所示的树表示。例例2.单位行政机构的组织关系单位行政机构的组织关系HBAJFEDKLCMIGq 树的应用树的应用 树是常用的数据组织形式树是常用的数据组织形式 有些应用中数据元素之间并不存在分支结构关系，但是为有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。了便于管理和使用数据，将它们用树的形式来组织。例例3.计算机的文件系统计算机的文件系统 不论是不论是DOS文件系统还是文件系统还是window文件系统，所有的文件文件系统，所有的文件是用树的形式来组织的。是用树的形式来组织的。文件夹文件夹1文件夹文件夹2文件文件1文件文件2文件夹文件夹11 文件夹文件夹11 文件文件11文件文件12Cq 树的应用树的应用树的结点：包含一个数据元素的树的结点：包含一个数据元素的内容及若干指向子树的分支。内容及若干指向子树的分支。孩子结点：结点的子树的根称为孩子结点：结点的子树的根称为该结点的孩子；如该结点的孩子；如E是是B的孩子。的孩子。双亲结点：双亲结点：B结点是结点是A结点的孩子，结点的孩子，则则A结点是结点是B结点的双亲；如结点的双亲；如B是是E的双亲。的双亲。兄弟结点：同一双亲的孩子结点；如兄弟结点：同一双亲的孩子结点；如H、I、J互为兄弟。互为兄弟。堂兄结点：同一层上结点；如堂兄结点：同一层上结点；如G与与E、F、H、I、J互为堂兄。互为堂兄。祖先结点：结点的祖先是从根到该结点所经分支上的所有结点；祖先结点：结点的祖先是从根到该结点所经分支上的所有结点；如如H的祖先为的祖先为A、D。子孙结点：以某结点为根的子树中的任一结点称为该结点的子孙；子孙结点：以某结点为根的子树中的任一结点称为该结点的子孙；如如A的子孙为的子孙为B、C、D、E、F、G、H、I、J、K、L、M。HBAJFEDKLCMIGq 基本术语基本术语结点的度：结点子树的个数；结点的度：结点子树的个数；如如D的度为的度为3。叶子结点：也叫终端结点，是叶子结点：也叫终端结点，是度为度为0的结点；如的结点；如K、L、F、G、M、I、J。分支结点：度不为分支结点：度不为0的结点；如的结点；如A、B、C、D结点层次：根结点的层定义为结点层次：根结点的层定义为1，根的孩子为第二层结点，依此，根的孩子为第二层结点，依此类推。类推。树的高度：树中结点的最大层次；如图所示树的高度为树的高度：树中结点的最大层次；如图所示树的高度为4。树的度：树的度：树中各结点的度的最大值；如图所示树的度为树中各结点的度的最大值；如图所示树的度为3。森林：森林：m(m=0)棵互不相交的树的集合；棵互不相交的树的集合；HBAJFEDKLCMIGq 基本术语基本术语EnQueue(Q,p-lchild);/入队列结点层次：根结点的层定义为1，根的孩子为第二层结点，依此类推。例 w=5,29,7,8,14,23,3,11计算机的文件系统 不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。pre(T L);访问：C B E G D F AB森林转变为二叉树实现过程访问：C B E G D F A一般二叉树也按完全二叉树形式存储，只有增添一些并不存在的空结点(用表示，表示该处没有元素存在，仅仅为了好理解)，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。(a)空树 (b)只含根结点 (c)右子树为空树遍历一个线性结构很简单，只须从开始结点出发，顺序扫描每个结点即可。即有(2k-1)-k个单元被浪费。访问结点时统计叶子结点的个数按不同的方式遍历二叉树所得到的线索二叉树是不相同的。pre(T L);性质1 在二叉树的第 i 层上至多有 2i-1个结点。五、遍历线索二叉树(续)当i1时，结点i可能是其双亲x的左孩子，也可能是右孩子，若是左孩子，由结论2知，x的左孩子应为2x，即2x=i，x=i/2；v 线性结构线性结构 第一个数据元素第一个数据元素（无前驱）；（无前驱）；最后一个数据元素（无后继）；最后一个数据元素（无后继）；其它数据元素（一个前驱、一个后继）。其它数据元素（一个前驱、一个后继）。v 树型结构树型结构 根结点（无前驱）；根结点（无前驱）；多个叶子结点多个叶子结点（无后继）；（无后继）；其它数据元素（一个前驱、多个后继）。其它数据元素（一个前驱、多个后继）。q 树型结构和线性结构的结构特点对比树型结构和线性结构的结构特点对比6.2.1 二叉树的定义二叉树的定义 l 或为空树，或由根及至多两棵互不相交的左子树、右子或为空树，或由根及至多两棵互不相交的左子树、右子树构成树构成(即不存在度大于即不存在度大于2的结点的结点)，并且左、右子树本身也，并且左、右子树本身也是二叉树。是二叉树。说明：说明：1.二叉树中每个结点最多有两棵子二叉树中每个结点最多有两棵子树，二叉树每个结点度小于等于树，二叉树每个结点度小于等于2；2.左、右子树不能颠倒左、右子树不能颠倒有序树；有序树；3.二叉树是递归结构，在二叉树的定二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念。义中又用到了二叉树的概念。BADCFEG6.2 二叉树二叉树 (a)(b)(c)(d)(e)(a)空树空树 (b)只含根结点只含根结点 (c)右右子树为空树子树为空树 (d)左右子树均不为空树左右子树均不为空树 (e)左子左子树为空树树为空树LLRRq 二叉树的形态二叉树的形态性质性质1 在二叉树的第在二叉树的第 i 层上至多有层上至多有 2i-1个结点。个结点。(i 1)证明用归纳法证明用归纳法证明：当证明：当i=1时，只有根结点，时，只有根结点，2 i-1=2 0=1。假设对所有假设对所有j，1ji，命题成立，即第，命题成立，即第j层上至多有层上至多有2 j-1 个个结点。结点。由归纳假设第由归纳假设第i-1 层上至多有层上至多有 2i-2个结点。个结点。由于二叉树的每个结点的度至多为由于二叉树的每个结点的度至多为2，故在第，故在第i层上的最大结层上的最大结点数为第点数为第i-1层上的最大结点数的层上的最大结点数的2倍，即倍，即22i-2=2 i-1。6.2.2 二叉树的性质二叉树的性质性质性质2 深度为深度为 k 的二叉树至多有的二叉树至多有 2 k-1个结点个结点(k 1)。证明：由性质证明：由性质1可见，深度为可见，深度为k的二叉树的最大结点数为的二叉树的最大结点数为 20+21+2 k-1=2 k-16.2.2 二叉树的性质二叉树的性质性质性质3 对任何一棵二叉树对任何一棵二叉树T，如果其叶结点数为，如果其叶结点数为 n0，度为，度为2的结点数为的结点数为 n2，则，则n0n21。证明：证明：设二叉树中度为设二叉树中度为1的结点数为的结点数为n1，二叉树中总结点数，二叉树中总结点数为：为：nn0n1n2 二叉树中的分支数，除根结点外，其余结点都有一个二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设进入分支，设B为二叉树中的分支总数，为二叉树中的分支总数，则有：则有：nB1。由于这些分支都是由度为由于这些分支都是由度为1和和2的结点射出的，所以有：的结点射出的，所以有：Bn1+2 n2 ;nB1n12n21得到：得到：n0n216.2.2 二叉树的性质二叉树的性质满二叉树：深度为满二叉树：深度为k的二叉树，有的二叉树，有2k-1个结点则称为满二叉个结点则称为满二叉树；树；完全二叉树：如果深度为完全二叉树：如果深度为k、由、由n个结点的二叉树中个结点个结点的二叉树中个结点能够与深度为能够与深度为k的顺序编号的满二叉树从的顺序编号的满二叉树从1到到n标号的结点相标号的结点相对应，则称为完全二叉树。对应，则称为完全二叉树。完全二叉树的特点是：完全二叉树的特点是：1.所有的叶结点都出现在第所有的叶结点都出现在第k层或层或k1层。层。2.对任一结点，如果其右子树的最大层次为对任一结点，如果其右子树的最大层次为l，则其左子，则其左子树的最大层次为树的最大层次为 l 或或 l 1。q 两种特殊的二叉树两种特殊的二叉树62175438910 1113 14 1512621754389 1011 122154367216543非完全二叉树非完全二叉树完全二叉树完全二叉树满满二二叉叉树树q 两种特殊的二叉树两种特殊的二叉树性质性质 4：具有：具有 n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。证明：设完全二叉树的深度为证明：设完全二叉树的深度为 k，则根据性质，则根据性质2和完全二叉和完全二叉树的定义有树的定义有2k-1-1 n 2k-1或或 2k-1 n 2k取对数取对数 k-1 1，则其双亲是结点则其双亲是结点 i/2 。2.如果如果2in，则结点，则结点i为叶子结点，无左孩子；否则，其为叶子结点，无左孩子；否则，其左孩子是结点左孩子是结点2i。3.如果如果2i1n，则结点，则结点i无右孩子；否则，其右孩子是结无右孩子；否则，其右孩子是结点点2i1。6.2.2 二叉树的性质二叉树的性质证明：此性质可采用数学归纳法证明。因为证明：此性质可采用数学归纳法证明。因为1与与2、3是相对应的，是相对应的，所以只需证明所以只需证明2和和3。当当 i=1时时，根据结点编号方法可知，根的左、右孩子编号分，根据结点编号方法可知，根的左、右孩子编号分别是别是2和和3，结论成立。，结论成立。假定假定i-1时结论成立，即结点时结论成立，即结点i-1的左右孩的左右孩子编号满足：子编号满足：LCHILD(i-1)=2(i-1)；RCHILD(i-1)=2(i-1)+1 通过完全二叉树可知，结点通过完全二叉树可知，结点 i 或者与结点或者与结点i-1同层且紧靠其右，同层且紧靠其右，或者结点或者结点i-1在某层最右端，而结点在某层最右端，而结点i在其下一层最左端。但是，无在其下一层最左端。但是，无论如何，结点论如何，结点i的左孩子的编号都是紧接着结点的左孩子的编号都是紧接着结点i-1的右孩子的编号，的右孩子的编号，故：故：LCHILD(i)=RCHILD(i-1)+1=2i；RCHILD(i)=LCHILD(i)+1=2i+1命题成立。命题成立。6.2.2 二叉树的性质二叉树的性质Thrt-rchild=pre;一般二叉树也按完全二叉树形式存储，只有增添一些并不存在的空结点(用表示，表示该处没有元素存在，仅仅为了好理解)，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。void InThreading(BiThrTree p)InThreading(p-lchild);/左子树线索化取对数 k-1 BDCD L R得到的序列为：得到的序列为：A B D Cq 先序遍历二叉树先序遍历二叉树Status PreOrderTraverse(BiTree T)/采用二叉链表存贮二叉树采用二叉链表存贮二叉树 if(T)/若二叉树不为空若二叉树不为空 Visit(T-data)；/访问根结点访问根结点 PreOrderTraverse(T-lchild);/先序遍历先序遍历T的左子树的左子树 PreOrderTraverse(T-rchild);/先序遍历先序遍历T的右子树的右子树 /PreOrderTraverseq 先序遍历二叉树算法实现先序遍历二叉树算法实现viod pre(bint T)if (T)visite(T-data);pre(T-lchild);pre(T-rchild);q 先序遍历二叉树算法实先序遍历二叉树算法实现现BADC主程序主程序Pre(T)TAvisite(A);pre(T L);TBvisite(B);pre(T L);T返回返回pre(T R);TDvisite(D);pre(T L);T返回返回pre(T R);T返回返回pre(T R);TCvisite(C);pre(T L);T返回返回pre(T R);T返回返回先序序列：先序序列：A B D C若二叉树非空，则：若二叉树非空，则：1.中序遍历左子树中序遍历左子树 2.访问根结点访问根结点 3.中序遍历右子树中序遍历右子树BADCL D RBL D RL D RADCL D R得到的序列为：得到的序列为：B D A Cq 中序遍历二叉树中序遍历二叉树若二叉树非空，则：若二叉树非空，则：1.后序遍历左子树后序遍历左子树 2.访问根结点访问根结点 3.后序遍历右子树后序遍历右子树BADC L R DL R DL R DADCL R DB得到的序列为：得到的序列为：D B C Aq 后序遍历二叉树后序遍历二叉树*-bcav 这这一一路路线线正正是是从从根根结结点点开开始始沿沿左左子子树树深深入入下下去去，当当深深入入到到最最左左端端，无无法法再再深深入入下下去去时时，则则返返回回，再再逐逐一一进进入入刚刚才才深深入入时时遇遇到到结结点点的的右右子子树树，再再进进行行如如此此的的深深入入和和返返回回，直直到到最最后后从从根根结结点点的的右右子子树树返返回回到到根根结结点点为为止止。先先序序遍遍历历是是在在深深入入时时遇遇到到结结点点就就访访问问，中中序序遍遍历历是是在在从从左左子子树树返返回回时时遇遇到到结结点点访访问问，后后序序遍遍历历是在从右子树返回时遇到结点访问。是在从右子树返回时遇到结点访问。v 在这一过程中，返回结点的顺序与深入结点的顺序相反，即后深入先返回，在这一过程中，返回结点的顺序与深入结点的顺序相反，即后深入先返回，正好符合栈结构后进先出的特点。因此，可以用栈来帮助实现这一遍历路线。正好符合栈结构后进先出的特点。因此，可以用栈来帮助实现这一遍历路线。q 三种遍历过程示意图例三种遍历过程示意图例-*abc 先序遍历：先序遍历：从二叉树根结点开始，沿左子树一直走到末端从二叉树根结点开始，沿左子树一直走到末端(左子树为空左子树为空)为止，在走的过程中，访问所遇结点，并依为止，在走的过程中，访问所遇结点，并依次把所遇结点进栈，当左子树为空时，从栈顶退出某结点，次把所遇结点进栈，当左子树为空时，从栈顶退出某结点，并将指针指向该结点的右子树。如此重复，直到栈为空或并将指针指向该结点的右子树。如此重复，直到栈为空或指针为空止。指针为空止。中序遍历：中序遍历：从二叉树根结点开始，沿左子树一直走到末端从二叉树根结点开始，沿左子树一直走到末端(左子树为空左子树为空)为止，在走的过程中，把依次遇到的结点进为止，在走的过程中，把依次遇到的结点进栈，待左子树为空时，从栈中退出结点并访问，然后再转栈，待左子树为空时，从栈中退出结点并访问，然后再转向它的右子树。如此重复，直到栈空或指针为空止。向它的右子树。如此重复，直到栈空或指针为空止。q 非递归实现方法非递归实现方法status InOrderTraverse(BiTree T)InitStack(S);Push(S,T);/根结点进栈根结点进栈 while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-lchild);Pop(S,p);/空指针退栈空指针退栈 if(!StackEmpty(S)Pop(S,p);Visit(p-data);Push(S,p-rchild);return OK;q 中序遍历的非递归算法中序遍历的非递归算法q 中序遍历的非递归算法演示中序遍历的非递归算法演示A AB BC CD DE EF FGGp pi iP-AP-A(1)(1)A AB BC CD DE EF FGGp pi iP-AP-AP-BP-B(2)(2)q 中序遍历的非递归算法演示中序遍历的非递归算法演示A AB BC CD DE EF FGGp pi iP-AP-AP-BP-BP-CP-C(3)(3)p=NULLp=NULLA AB BC CD DE EF FGGi iP-AP-AP-BP-B访问：访问：访问：访问：C C(4)(4)void InThreading(BiThrTree p)int n;/结点数if(T-lchild=NULL&T-rchild=NULL)n+=1;赫夫曼树：在一棵二叉树中，若树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为赫夫曼树。若每个字符出现的频率不同，可以采用不等长的二进编码，频率较大的采用位数较少的编码，频率较小的字符采用位数较多的编码，这样可以使字符的整体编码长度最小，这就是最小冗余编码的问题。最后一个数据元素（无后继）；pre(T R);例如，深度为k，且只有k个结Status PreOrderTraverse(BiTree T)if(T)性质1 在二叉树的第 i 层上至多有 2i-1个结点。先序遍历：从二叉树根结点开始，沿左子树一直走到末端(左子树为空)为止，在走的过程中，访问所遇结点，并依次把所遇结点进栈，当左子树为空时，从栈顶退出某结点，并将指针指向该结点的右子树。得到的序列为：A B D CT-data=ch;/建立(根)结点假定i-1时结论成立，即结点i-1的左右孩子编号满足：访问：C B E G D F三、线索链表的类型描述或为空树，或由根及至多两棵互不相交的左子树、右子树构成(即不存在度大于2的结点)，并且左、右子树本身也是二叉树。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。用先序序列的第一个结点作为根结点;if(!StackEmpty(S)多重链表：每个结点有多个指针域，分别指向其子树的根。q 中序遍历的非递归算法演示中序遍历的非递归算法演示p pA AB BC CD DE EF FGGi iP-AP-A访问：访问：访问：访问：C BC B(5)(5)A AB BC CD DE EF FGGi iP-AP-AP-DP-D访问：访问：访问：访问：C BC Bp p(6)(6)q 中序遍历的非递归算法演示中序遍历的非递归算法演示A AB BC CD DE EF FGGi iP-AP-AP-DP-DP-EP-E访问：访问：访问：访问：C BC Bp p(7)(7)A AB BC CD DE EF FGGi iP-AP-AP-DP-D访问：访问：访问：访问：C B EC B Ep p(8)(8)q 中序遍历的非递归算法演示中序遍历的非递归算法演示A AB BC CD DE EF FGGi iP-AP-AP-DP-DP-GP-G访问：访问：访问：访问：C B EC B EP=NULLP=NULL(9)(9)A AB BC CD DE EF FGGi iP-AP-AP-DP-D访问：访问：访问：访问：C B E GC B E Gp p(10)(10)q 中序遍历的非递归算法演示中序遍历的非递归算法演示A AB BC CD DE EF FGGi iP-AP-A访问：访问：访问：访问：C B E G DC B E G Dp p(11)(11)A AB BC CD DE EF FGGi iP-AP-AP-FP-F访问：访问：访问：访问：C B E G DC B E G Dp p(12)(12)q 中序遍历的非递归算法演示中序遍历的非递归算法演示A AB BC CD DE EF FGGi iP-AP-A访问：访问：访问：访问：C B E G D FC B E G D Fp=NULLp=NULL(13)(13)A AB BC CD DE EF FGGi i访问：访问：访问：访问：C B E G D F AC B E G D F Ap p(14)(14)q 中序遍历的非递归算法演示中序遍历的非递归算法演示A AB BC CD DE EF FGGi i访问：访问：访问：访问：C B E G D F AC B E G D F Ap=NULLp=NULL(15)(15)后序遍历：后序遍历：利用栈来实现二叉树的后序遍历要比先序和中利用栈来实现二叉树的后序遍历要比先序和中序遍历复杂得多，在后序遍历中，当搜索指针指向某一个序遍历复杂得多，在后序遍历中，当搜索指针指向某一个结点时，不能马上进行访问，而先要遍历左子树，所以此结点时，不能马上进行访问，而先要遍历左子树，所以此结点应先进栈保存，当遍历完它的左子树后，再次回到该结点应先进栈保存，当遍历完它的左子树后，再次回到该结点，还不能访问它，还需先遍历其右子树，所以该结点结点，还不能访问它，还需先遍历其右子树，所以该结点还必须再次进栈，只有等它的右子树遍历完后，再次退栈还必须再次进栈，只有等它的右子树遍历完后，再次退栈时，才能访问该结点。为了区分同一结点的两次进栈，引时，才能访问该结点。为了区分同一结点的两次进栈，引入一个栈次数的标志，元素第一次进栈标志为入一个栈次数的标志，元素第一次进栈标志为1，第二次进，第二次进标志为标志为2，当退出的元素标志为，当退出的元素标志为2时，访问结点。时，访问结点。q 非递归实现方法非递归实现方法void leaf(BiTree T)/采用二叉链表存贮二叉树，采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的为全局变量，用于累加二叉树的叶子结点个数，本算法在先序遍历二叉树的过程中，统计叶子结叶子结点个数，本算法在先序遍历二叉树的过程中，统计叶子结点的个数，初始化点的个数，初始化n=0if(T)if(T-lchild=NULL&T-rchild=NULL)n+=1;/若若T所指结点为叶子结点则计数所指结点为叶子结点则计数 leaf(T-lchild);leaf(T-rchild);/if /leaf例例1 编写求二叉树的叶子结点个数的算法编写求二叉树的叶子结点个数的算法void leaf(BiTree T)If(T)if(T-lchild=NULL&T-rchild=NULL)n+=1;leaf(T-lchild);leaf(T-rchild);/if /leafStatus PreOrderTraverse(BiTree T)if(T)Visit(T-data)；PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);/PreOrderTraverse访问结点时统计访问结点时统计叶子结点的个数叶子结点的个数访问结点时访问结点时调用调用visit()比较先序遍历和计算叶子结点算法相同点和不同点比较先序遍历和计算叶子结点算法相同点和不同点 分析：本算法要借用队列来完成，其基本思想是，若二分析：本算法要借用队列来完成，其基本思想是，若二叉树非空，先将根结点进队列。然后进入循环：只要队列叉树非空，先将根结点进队列。然后进入循环：只要队列不空，就出队列，遍历该结点，然后判断出队列的结点是不空，就出队列，遍历该结点，然后判断出队列的结点是否有左孩子和右孩子，如有就让左、右孩子进队列。否有左孩子和右孩子，如有就让左、右孩子进队列。例例2 按层次遍历二叉树的算法按层次遍历二叉树的算法void layorder(BiTree T)InitQueue(Q)/队列初始化队列初始化 if(T!=NULL)EnQueue(Q,T);/入队列入队列 while(not QueueEmpty(Q)/若队列非空若队列非空 DeQueue(Q,p);/出队出队 visite(p-data);if(p-lchild!=NULL)EnQueue(Q,p-lchild);/入队列入队列 if(p-rchild!=NULL)EnQueue(Q,p-rchild);/入队列入队列 例例2 按层次遍历二叉树的算法按层次遍历二叉树的算法输入：二叉树的先序序列输入：二叉树的先序序列结果：二叉树的二叉链表结果：二叉树的二叉链表问题：遍历操作访问二叉树的每个结问题：遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是点，而且每个结点仅被访问一次。是否可利用遍历，建立二叉链表的所有否可利用遍历，建立二叉链表的所有结点并完成相应结点的链接？结点并完成相应结点的链接？基本思想：输入在空子树处添加字符基本思想：输入在空子树处添加字符的二叉树的按先序遍历的顺序，建的二叉树的按先序遍历的顺序，建立二叉链表的所有结点并完成相应结立二叉链表的所有结点并完成相应结点链接。点链接。BADCEF在空子树处添加的二在空子树处添加的二叉树的先序序列：叉树的先序序列：A B D F E C 例例3 建立二叉链表建立二叉链表Status CreateBiTree(BiTree&T)/输入输入(在空子树处添加字符的二叉树的在空子树处添加字符的二叉树的)先序序列先序序列(设元素均设元素均为字符为字符)scanf(&ch);if(ch=)T=NULL;/若若ch=则表则表示空子树示空子树 else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;/建立建立(根根)结点结点 CreateBiTree(T-lchild);/递归构造左子树链表递归构造左子树链表 CreateBiTree(T-rchild);/递归构造右子树链表递归构造右子树链表 return OK;/CreateBiTreeq 建立二叉链表算法建立二叉链表算法q 建立二叉链表算法建立二叉链表算法BACDA B C D A BCDATBCD分分析析：由由先先序序序序列列和和中中序序序序列列的的定定义义可可知知，先先序序序序列列中中第第一一个个结结点点必必为为根根结结点点，而而在在中中序序序序列列中中，根根结结点点刚刚好好是是左左、右右子子树树的的分分界点，因此，界点，因此，可按如下方法建立二叉树：可按如下方法建立二叉树：1.用先序序列的第一个结点作为根结点用先序序列的第一个结点作为根结点;2.在中序序列中查找根结点的位置，并以此为界将中序序列划在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列分为左、右两个序列(左、右子树左、右子树);3.根根据据左左、右右子子树树的的中中序序序序列列中中的的结结点点个个数数，将将先先序序序序列列去去掉掉根根结结点点后后的的序序列列划划分分为为左左、右右两两个个序序列列，它它们们分分别别是是左左、右右子子树树的先序序列的先序序列;4.对左、右子树的先序序列和中序序列递归地实施同样方法，对左、右子树的先序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。直到所得左、右子树为空。例例4 由二叉树先序和中序序列建立一个唯一二叉树由二叉树先序和中序序列建立一个唯一二叉树 如一棵二叉树的先序序列为如一棵二叉树的先序序列为ABDGHCEFI，中序序列为，中序序列为GDHBAECIF，试建立该二叉树。，试建立该二叉树。构造过程：由先序可知构造过程：由先序可知A为根结点，再根据中序序列知：为根结点，再根据中序序列知：由由GDHB是左子树，是左子树，ECIF是右子树。是右子树。v A为根结点为根结点A BDGH CEFIGDHB A ECIFv B为左子树的根结点为左子树的根结点B DGHGDH Bv 一直进行下去一直进行下去AG,D,H,B组成左子树组成左子树E,C,I,F组成右子树组成右子树 示例分析示例分析a b c d e f gc b d a e g faab bccddeeffggabcdefg先序序列先序序列先序序列先序序列中序序列中序序列中序序列中序序列遍历是二叉树最基本最常用的操作。遍历是二叉树最基本最常用的操作。1.对二叉树所有结点做某种处理可在遍历过程中实现；对二叉树所有结点做某种处理可在遍历过程中实现；2.查找二叉树某个结点，可通过遍历实现；查找二叉树某个结点，可通过遍历实现；与线性表相比，对二叉树的遍历存在如下问题：与线性表相比，对二叉树的遍历存在如下问题：1.遍历算法要复杂的多，费时的多；遍历算法要复杂的多，费时的多；2.为查找二叉树中某结点在某种遍历下的后继，必须从根为查找二叉树中某结点在某种遍历下的后继，必须从根开始遍历，直到找到该结点及后继；开始遍历，直到找到该结点及后继；如果能将二叉树线性化，就可以减化遍历算法，提高如果能将二叉树线性化，就可以减化遍历算法，提高遍历速度。遍历速度。6.3.2 线索二叉树线索二叉树定义：当以二叉链表作为存储结构时，只能找到结点的左右孩子定义：当以二叉链表作为存储结构时，只能找到结点的左右孩子的信息，而不能直接得到结点的任一序列的前驱与后继信息，这的信息，而不能直接得到结点的任一序列的前驱与后继信息，这种信息只有在遍历的动态过程中才能得到，为了能保存所需的信种信息只有在遍历的动态过程中才能得到，为了能保存所需的信息，可增加标志域。息，可增加标志域。0 lchild 域指示结点的左孩子域指示结点的左孩子 1 lchild 域指示结点的前驱域指示结点的前驱 0 rchild 域指示结点的右孩子域指示结点的右孩子 1 rchild 域指示结点的后继域指示结点的后继 以这种结构构成的二叉链表作为二叉树的存储结构，叫做线以这种结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱与后继的指针叫做线索。加上线索的索链表，其中指向结点前驱与后继的指针叫做线索。加上线索的二叉树称之为线索二叉树。二叉树称之为线索二叉树。LTag=RTag=一、线索二叉树定义一、线索二叉树定义 利用现有的空指针域利用现有的空指针域，每个，每个n个结点的二叉链表，有个结点的二叉链表，有n+1个空指针域，故可利用这些的空指针域存放结点的前趋个空指针域，故可利用这些的空指针域存放结点的前趋和后继指针。和后继指针。(n个结点共有个结点共有2n个链域，而每个结点个链域，而每个结点(除根结点外除根结点外)都有一个分支指向，则共有都有一个分支指向，则共有n-1个分支，其中每个分支占有一个个分支，其中每个分支占有一个链域，所以空链域为链域，所以空链域为2n-(n-1)=n+1。)v 若结点有左子树，则左指针若结点有左子树，则左指针lchild指示其左孩子指示其左孩子(LTag=0)；否则，令左指针指示其前驱否则，令左指针指示其前驱(LTag=1)；v 若结点有右子树，则右指针若结点有右子树，则右指针rchild指示其右孩子指示其右孩子(RTag=0)；否则，令右指针指示其后继否则，令右指针指示其后继(RTag=1)。二、如何保存遍历过程中得到的信息？二、如何保存遍历过程中得到的信息？typedef enum PointerTeg Link,Thread;/Link=0:指针，指针，Thread=1:线索线索typedef struct BiThrNod TElemType data;struct BiThrNode *lchild,*rchild;/左右指针左右指针 PointerTeg LTag,RTag;/左右标志左右标志 BiThrNode,*BiThrTree;三、线索链表的类型描述三、线索链表的类型描述lchildLTagdataRTagrchild(以中序遍历为例以中序遍历为例)v 查找任意结点的前驱结点查找任意结点的前驱结点 如如果果该该结结点点的的左左标标志志为为1，那那么么其其左左指指针针域域所所指指向向的的结结点点便便是是它它的的前前驱驱结结点点；如如果果该该结结点点的的左左标标志志为为0，表表明明该该结结点点有有左左孩孩子子，根根据据中中序序遍遍历历的的定定义义，它它的的前前驱驱结结点点是是以以该该结结点点的的左左孩孩子子为为根根结结点点的的子子树树的的最最右右结结点点，即即沿沿着着其其左左子子树树的的右右指指针针链链向向下下查查找找，当当某某结结点点的的右右标标志志为为1时时，它它就就是是所所要要找找的前驱结点。的前驱结点。中序线索二叉树中序线索二叉树中序：中序：DBGJEACHLKFI 四、四、如何找结点的前驱和后继如何找结点的前驱和后继BACEFDGJHIKL中序线索二叉树中序线索二叉树中序：中序：DBGJEACHLKFI 四、如何找结点的前驱和后继四、如何找结点的前驱和后继(续续)(以中序遍历为例以中序遍历为例)v 查找任意结点的后继结点查找任意结点的后继结点 对对任任意意结结点点p，若若右右标标志志为为1，则则rchild指指向向该该结结点点的的后后继继；若若右右标标志志为为0，则则rchild指指向向该该结结点点的的右右孩孩子子，此此时时，应应从从右右孩孩子子开开始始，沿沿左左指指针针前前进进，直直到到找找到到没没有有左左孩孩子子的的结结点点s(Ltag=1)，则则s就就是是p的的后后继继，即即后后继继是是中中序序遍遍历右子树时，访问的第一个结点。历右子树时，访问的第一个结点。BACEFDGJHIKL 按不同的方式遍历二叉树所得到的线索二叉树是不相按不同的方式遍历二叉树所得到的线索二叉树是不相同的。同的。BADCE 五、遍历线索二叉树五、遍历线索二叉树 A B D C ET先序序列：先序序列：ABCDE先序线索二叉树先序线索二叉树00001111 11 A B D C ET中序序列：中序序列：BCAED中序线索二叉树中序线索二叉树0000111111 A B D C ET后序序列：后序序列：CBEDA后序线索二叉树后序线索二叉树0000111111BADCE A B D C ET0000111111 01中序序列：中序序列：BCAED中序线索二叉树中序线索二叉树 五、遍历线索二叉树五、遍历线索二叉树(续续)v 带头结点的线索二叉树带头结点的线索二叉树 在在存存储储线线索索二二叉叉树树时时往往往往增增设设一一头头结结点点，其其数数据据域域不不存存放放信信息息，其其左左指指针针域域指指向向二二叉叉树树的的根根结结点点，右右指指针针域域指指向向某某种种遍遍历历时时访访问问的的最最后后一一个个结结点点。而而原原二二叉叉树树在在某某序序遍遍历历下下的的第第一一个个结结点点的的前前驱驱线线索索和和最最后后一一个个结结点点的的后后继继线线索索都都指向该头结点。指向该头结点。注注：可可从从第第一一个个结结点点起起顺顺后后继继进进行行遍遍历历，也也可可以以从从最最后后一一个个结结点点起顺前驱进行遍历。起顺前驱进行遍历。v 找遍历的第