数据结构树和二叉树.pptx

数据结构可分为线性结构和非线性结构两大类。前面几章主要研究数据结构可分为线性结构和非线性结构两大类。前面几章主要研究的是线性结构。一般的，线性结构只能用来描述数据元素之间的线的是线性结构。一般的，线性结构只能用来描述数据元素之间的线性顺序关系，而很难反映元素之间的层次性顺序关系，而很难反映元素之间的层次(分支分支)关系。本章将要讨关系。本章将要讨论一种非线性数据结构，所谓非线性结构是指在结构中至少存在一论一种非线性数据结构，所谓非线性结构是指在结构中至少存在一个数据元素，它具有两个或两个以上的直接后继或直接前驱。个数据元素，它具有两个或两个以上的直接后继或直接前驱。树形结构，是一类非常重要的非线性数据结构，它用于描述数据元树形结构，是一类非常重要的非线性数据结构，它用于描述数据元素之间的层次关系。树形结构在客观世界中广泛存在，如人类社会素之间的层次关系。树形结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。经常用到的两种的族谱和各种社会组织机构都可用树来形象表示。经常用到的两种结构是树和二叉树。结构是树和二叉树。本章先介绍树、二叉树的定义、性质及存储结构，重点讨论二叉树本章先介绍树、二叉树的定义、性质及存储结构，重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树之间的转换关的存储结构及其各种操作，并研究树和森林与二叉树之间的转换关系，最后介绍树的应用。系，最后介绍树的应用。引 言第1页/共188页内容提要内容提要6.1树的定义和基本术语树的定义和基本术语6.2二叉树二叉树6.3遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4树和森林树和森林6.6赫夫曼树及其应用赫夫曼树及其应用小结小结第2页/共188页6.1树的定义树的定义和基本术语和基本术语第3页/共188页树树(Tree)(Tree)是包含是包含n(n0)n(n0)个结点的有限集。在任意个结点的有限集。在任意一棵非空树中：非空树中：（1 1）有且仅有一个特定的称为有且仅有一个特定的称为根根(Root)(Root)的结点；的结点；(2)(2)当当n1n1时，其余的结点可分为时，其余的结点可分为m(m0)m(m0)个个互不相交互不相交的子集的子集T T1 1,T,T2 2,T,T3 3T Tm m，其中每个子集又是一棵树，并，其中每个子集又是一棵树，并称其为称其为子树子树(Subtree)(Subtree)。树也可以这样定义：树也可以这样定义：树是由根结点和若干棵子树构成树是由根结点和若干棵子树构成的。可以看出，在树的定义中用了递归的概念，即在树的。可以看出，在树的定义中用了递归的概念，即在树的定义中又用到树的定义，它道出了树的固有特性，因的定义中又用到树的定义，它道出了树的固有特性，因此递归算法是树结构算法的显著特点。此递归算法是树结构算法的显著特点。树的定义第4页/共188页上图(a)(a)是只有一个根结点的树；图(b)(b)是有1313个结点的树，其中A A是根，其余结点分成三个互不相交的子集：T1=BT1=B，E E，F F，K K，LL，T2=CT2=C，GG，T3=DT3=D，H H，I I，J J，MM；T1T1、T2T2和T3T3都是根A A的子树，且本身也是一棵树。例如T1T1，其根为B B，其余结点分为两个互不相交的子集；T11=ET11=E，K K，LL，T12=FT12=F。T11T11和T12T12都是B B的子树。而T11T11中E E是根结点，KK和LL是E E的两棵互不相交的子树，其本身又是只有一个根结点的树。第5页/共188页数据对象数据对象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。若若D为空集，则称为空树为空集，则称为空树。否则否则:(1)在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root；(2)当当n1时，其余结点可分为时，其余结点可分为m(m0)个互个互不相交的有限集不相交的有限集T1,T2,Tm，其中每一，其中每一棵子集本身又是一棵符合本定义的树，棵子集本身又是一棵符合本定义的树，称为根称为根root的子树。的子树。数据关系数据关系R：ADTTree第6页/共188页 基本操作：基本操作：查查找找类类插插入入类类删删除除类类第7页/共188页 Root(T)/求树的根结点求树的根结点查找类：查找类：Value(T,cur_e)/求当前结点的元素值求当前结点的元素值Parent(T,cur_e)/求当前结点的双亲结点求当前结点的双亲结点LeftChild(T,cur_e)/求当前结点的最左孩子求当前结点的最左孩子RightSibling(T,cur_e)/求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树判定树是否为空树TreeDepth(T)/求树的深度求树的深度TraverseTree(T,Visit()/遍历遍历第8页/共188页InitTree(&T)/初始化置空树初始化置空树插入类：插入类：CreateTree(&T,definition)/按定义构造树按定义构造树Assign(T,cur_e,value)/给当前结点赋值给当前结点赋值InsertChild(&T,&p,i,c)/将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树第9页/共188页 ClearTree(&T)/将树清空将树清空删除类：删除类：DestroyTree(&T)/销毁树的结构销毁树的结构DeleteChild(&T,&p,i)/删除结点删除结点p的第的第i棵子树棵子树第10页/共188页树的表示方法有四种，各用于不同的目的。树的表示方法有四种，各用于不同的目的。(1)(1)直观表示法：就是一棵树的直观表示。直观表示法：就是一棵树的直观表示。(2)(2)广义表示法：下图广义表示法：下图 (a)(a)是以广义表的形式表示的，根作为由子树森林组成是以广义表的形式表示的，根作为由子树森林组成的表的名字写在表的左边。树的形式化表示法主要用于树的理论描述。的表的名字写在表的左边。树的形式化表示法主要用于树的理论描述。(3)(3)凹入表示法：下图凹入表示法：下图(b)(b)用的是凹入表示法用的是凹入表示法(类似书的编目类似书的编目)。树的凹入表示法。树的凹入表示法主要用于树的屏幕和打印显示。主要用于树的屏幕和打印显示。(4(4）嵌套集合表示法：参见）嵌套集合表示法：参见P120P120图图6.26.2。表示方法的多样性，正说明了树结构在日常生活中及计算机程序设计中的重要表示方法的多样性，正说明了树结构在日常生活中及计算机程序设计中的重要性。一般来说，分等级的分类方案都可用层次结构来表示，也就是说，都可产生性。一般来说，分等级的分类方案都可用层次结构来表示，也就是说，都可产生一个树结构。一个树结构。树的表示形式树的表示形式第11页/共188页ABCDEFGHIJMKLA(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根例如例如:第12页/共188页第13页/共188页基基 本本 术术 语语第14页/共188页结点结点:结点的度结点的度:树的度树的度:叶子结点叶子结点:分支结点分支结点:数据元素及若干指向子树的分支拥有的子树数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM第15页/共188页(从根到结点的)路径：路径：结点的层次结点的层次:树的深度：树的深度：由从根根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次孩子结点：结点子树的根双亲结点：孩子结点的直接前驱兄弟结点：同一双亲的孩子间堂兄弟：双亲在同一层的结点祖先结点：从根到该结点所经分支的所有结点子孙结点：以某结点为根的子树中的任一结点第16页/共188页()有确定的根；()树根和子树根之间为有向关系。有向树：有向树：有序树：有序树：子树之间存在确定的次序关系。无序树：无序树：子树之间不存在确定的次序关系。第17页/共188页任何一棵非空树是一个二元组Tree=（root，F）其中：root 被称为根结点 F 被称为子树森林森林：森林：是m（m0）棵互不相交的树的集合ArootBCDEFGHIJMKLF第18页/共188页对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点第19页/共188页线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素(无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)第20页/共188页6.2 二二 叉叉 树树第21页/共188页6.2.1二叉树的定义二叉树的定义二叉树（二叉树（BinaryTree）或为空树，或是由一个根）或为空树，或是由一个根结点加上两棵分别称为结点加上两棵分别称为左子树左子树和和右子树右子树的、的、互互不相交的不相交的二叉树组成。二叉树组成。ABCDEFGHK根结点左子树右子树第22页/共188页二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树第23页/共188页抽象数据类型二叉数定义ADTBinaryTree数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=，则R=，称BinaryTree为空二叉树;若D ，则R=H，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若 D root，则 存 在 D root=DL，Dr,DLDr=，(3)若 DL,则 DL存 在 唯 一 的 数 据 元 素 xL，有 H;H;且存在DL上的关系HL H；若Dr，则D Dr r存在唯一的数据元素xr，有 H;H;且存在Dr上的关系Hr H,H=，,HL,Hr;(4)（DL,HL）是一棵符合本定义的二叉树，称为根root的左子树，（Dr,Hr）是一棵符合本定义的二叉树，称为根root的右子树，第24页/共188页二叉树的主要基本操作二叉树的主要基本操作：查查找找类类插插入入类类删删除除类类第25页/共188页 Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit();InOrderTraverse(T,Visit();PostOrderTraverse(T,Visit();LevelOrderTraverse(T,Visit();第26页/共188页 InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);第27页/共188页ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);第28页/共188页6.2.2二叉树二叉树的性质的性质第29页/共188页性质性质1：在二叉树的第i层上至多有2i-1 个结点。(i1)用归纳法证明用归纳法证明：归纳基归纳基：归纳假设：归纳假设：归纳证明：归纳证明：i=1 层时，只有一个根结点：2i-1=20=1；假设对所有的 j，1 j i，命题成立；二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2i-2 2=2i-1。第30页/共188页性质性质2：深度为k 的二叉树上至多含2k-1 个结点（k1）。证明：证明：基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+2k-1=2k-1。第31页/共188页性质性质3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2的结点，则必存在关系式：n0=n2+1。证明：证明：设设 二叉树上结点总数 n=n0+n1+n2又又 二叉树上分支总数 b=n1+2n2 而 b=n-1=n0+n1+n2-1由此，由此，n0=n2+1。第32页/共188页两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号编号为为1 至至n 的结点的结点一一对应。123456789 10 11 12 13 14 15abcdefghij第33页/共188页性质性质4：具有 n 个结点的完全二叉树的深深度度为 log2n +1。证明：证明：设设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子右孩子结点。第35页/共188页第36页/共188页6.2.3二叉树的存储结构二叉树的存储结构二、二叉树的链式二、二叉树的链式 存储结构存储结构一、一、二叉树的顺序二叉树的顺序存储结构存储结构第37页/共188页#define MAX_TREE_SIZE 100 /二叉树的最大结点数typedefTElemType SqBiTreeMAX_ TREE_SIZE;/0号单元存储根结点SqBiTree bt;一、一、二叉树的顺序存储结构二叉树的顺序存储结构第38页/共188页按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元依次自上而下、按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元依次自上而下、自左至右存储二叉树上的结点元素。因此，必须把结点安排成一个适当的线性序列，自左至右存储二叉树上的结点元素。因此，必须把结点安排成一个适当的线性序列，使得结点在这个序列中的相互位置能反映出结点之间的逻辑关系。使得结点在这个序列中的相互位置能反映出结点之间的逻辑关系。在一棵有在一棵有n n个结点的完全二叉树中，从树根起，自上层到下层，每层从左到右地给结个结点的完全二叉树中，从树根起，自上层到下层，每层从左到右地给结点编号，就能得到一个足以反映整个二叉树结构的线性序列，如下图所示。点编号，就能得到一个足以反映整个二叉树结构的线性序列，如下图所示。二叉树的顺序存储结构二叉树的顺序存储结构第39页/共188页第40页/共188页第41页/共188页第42页/共188页练习练习:ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 131401326第43页/共188页二、二叉树的链式存储表示二、二叉树的链式存储表示1.1.二叉链表二叉链表2三叉链表三叉链表3 3双亲链表双亲链表4线索链表线索链表第44页/共188页ADEBCF rootlchild data rchild结点结构结点结构:1.1.二叉链表二叉链表二叉链表二叉链表第45页/共188页ABCDEF二叉树二叉树第46页/共188页typedefstruct BiTNode /结点结构结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下:第47页/共188页ADEBCF root 2三叉链表三叉链表parentlchilddatarchild结点结构结点结构:第48页/共188页 typedefstruct TriTNode/结点结构结点结构 TElemType data;struct TriTNode *lchild,*rchild;/左右孩子指针 structTriTNode*parent;/双亲指针 TriTNode,*TriTree;parentlchilddatarchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下:第49页/共188页0123456 data parent结点结构结点结构:3 3双亲链表双亲链表LRTagLRRRL第50页/共188页 typedefstruct BPTNode/结点结构结点结构 TElemType data;int *parent;/指向双亲的指针 charLRTag;/左、右孩子标志域 BPTNode typedefstructBPTree/树结构树结构BPTNode nodesMAX_TREE_SIZE;int num_node;/结点数目 int root;/根结点的位置 BPTree第51页/共188页6.3.1二叉树的遍历二叉树的遍历6.3遍历二叉树和遍历二叉树和线索二叉树线索二叉树第52页/共188页一、问题的提出一、问题的提出二、先左后右的遍历算法二、先左后右的遍历算法三、算法的递归描述三、算法的递归描述四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述五五、遍历算法的应用举例遍历算法的应用举例第53页/共188页如何按着某条搜索路径如何按着某条搜索路径巡访巡访二叉二叉树中的每个结点，使得每个结点树中的每个结点，使得每个结点均被均被访问一次访问一次，而且，而且仅被访问一次仅被访问一次。一、问题的提出一、问题的提出“访问访问”的含义可以很广，如：输出结的含义可以很广，如：输出结点的信息等。点的信息等。第54页/共188页 “遍历遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继每个结点有两个后继，则存在如何遍历存在如何遍历即按什么样的搜索搜索路径路径遍历的问题。第55页/共188页二叉树的遍历方法二叉树的遍历方法 二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：令：L L：遍历左子树 D D：访问根结点 R R：遍历右子树 有六种遍历方法：D DL LR R，L LD DR R，L LR RD D，D DR RL L，R RD DL L，R RL LD D 约定先左后右,有三种遍历方法：D DL LR R、L LD DR R、L LR RD D，分别称为 先序遍历、中序遍历、后序遍历 A A F F G G E E D D C C B B第56页/共188页57 先序遍历（先序遍历（D DL LR R）若二叉树非空若二叉树非空 （1 1）访问根结点；）访问根结点；（2 2）先序遍历左子树；）先序遍历左子树；（3 3）先序遍历右子树）先序遍历右子树；先序遍历序列：先序遍历序列：A A F F G G E E D D C C B B例：先序遍历右图所示的二叉树例：先序遍历右图所示的二叉树 （1 1）访问根结点）访问根结点A A （2 2）先序遍历左子树：即按先序遍历左子树：即按D DL LR R的顺序遍历的顺序遍历左子树左子树 （3 3）先序遍历右子树：即按）先序遍历右子树：即按D DL LR R的顺序遍历的顺序遍历右子树右子树A BCDFGE二、先左后右的遍历算法二、先左后右的遍历算法第57页/共188页58中序遍历（中序遍历（L LD DR R ）若二叉树非空若二叉树非空（1 1）中序遍历左子树）中序遍历左子树（2 2）访问根结点）访问根结点（3 3）中序遍历右子树）中序遍历右子树 中序遍历序列：A A F F G G E E D D C C B B例：中序遍历右图所示的二叉树例：中序遍历右图所示的二叉树 （1 1）中序遍历左子树：即按）中序遍历左子树：即按L LD DR R的顺序遍历的顺序遍历左子树左子树 （2 2）访问根结点）访问根结点 A A （3 3）中序遍历右子树：即按中序遍历右子树：即按L LD DR R的顺序遍历的顺序遍历右子树右子树D BCGFAE第58页/共188页59后序遍历（后序遍历（L LR RD D）若二叉树非空若二叉树非空（1 1）后序遍历左子树）后序遍历左子树（2 2）后序遍历右子树）后序遍历右子树（3 3）访问根结点）访问根结点 后序遍历序列：例：后序遍历右图所示的二叉树例：后序遍历右图所示的二叉树 （1 1）后序遍历左子树：即按）后序遍历左子树：即按L LR RD D的顺序遍历的顺序遍历左子树左子树 （2 2）后序遍历右子树：即按）后序遍历右子树：即按L LR RD D的顺序遍历的顺序遍历右子树右子树 （3 3）访问根结点）访问根结点 A A A A F F G G E E D D C C B BD GCEAFB第59页/共188页60 e e d d c c b b f f a a +*/-后序遍历序列：中序遍历序列：先序遍历序列：例：先例：先中序遍历序遍历、中序遍历、中序遍历序遍历、中序遍历、后后序遍历下图所示的二叉树序遍历下图所示的二叉树前缀表达式中缀表达式后缀表达式-+a*b-c d/e fa+b*c-d-e/fa b c d-*+e f/-第60页/共188页R A DE C HF GBK练习：求下列二叉链表和二叉树的三种遍历次序练习：求下列二叉链表和二叉树的三种遍历次序ABCDEFGHK第61页/共188页这实际上是先序遍历的递归定义，我们知道递归定义包括两个部分：1 1）基本项（也叫终止项）；2 2）递归项 若二叉树非空若二叉树非空 （1 1）访问根结点；）访问根结点；（2 2）先序遍历左子树）先序遍历左子树 （3 3）先序遍历右子树；）先序遍历右子树；先序遍历递归定义递归项上上面面介介绍绍了了三三种种遍遍历历方方法法，显显然然是是用用递递归归的的方方式式给给出出的的三三种种遍遍历历方方法，以先序为例：法，以先序为例：先序遍历（先序遍历（D DL LR R）的定义：）的定义：该定义隐含着若二叉树为空，结束 三、算法的递归描述三、算法的递归描述第62页/共188页上面先序遍历的定义等价于：上面先序遍历的定义等价于：若二叉树为空，结束若二叉树为空，结束 基本项基本项（也叫终止项）（也叫终止项）若二叉树非空若二叉树非空 递归项递归项 （1 1）访问根结点；）访问根结点；（2 2）先序遍历左子树）先序遍历左子树 （3 3）先序遍历右子树；）先序遍历右子树；下面给出下面给出先序、中序、后序遍历递归算法，为了增加算法的可先序、中序、后序遍历递归算法，为了增加算法的可读性，这里对书上算法作了简化，没有考虑访问结点出错的情况读性，这里对书上算法作了简化，没有考虑访问结点出错的情况（即我们假设调用函数（即我们假设调用函数visit()visit()访问结点总是成功的。访问结点总是成功的。第63页/共188页1先序遍历递归算法voidPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)/采用二叉链表存贮二叉树，visit()是访问结点的函数。本算法/先序遍历以为根结点指针的二叉树，对每个数据元素调用函数/Visit()if(T)/若二叉树为空，结束返回/若二叉树不为空，访问根结点；遍历左子树，遍历右子树Visit(T-data)；PreOrderTraverse(T-lchild,Visit);PreOrderTraverse(T-rchild,Visit);/PreOrderTraverse最简单的Visit函数是：StatusPrintElement(TElemTypee)/输出元素e的值printf(e);returnOK;D D A A B B C C E E FFT T第64页/共188页2中序遍历递归算法中序遍历递归算法voidInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)/采用二叉链表存贮二叉树，采用二叉链表存贮二叉树，visit()是访问结点的函数。本算法中是访问结点的函数。本算法中序遍历以为根结点指针的二叉树，对每个数据元素调用函数序遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit()if(T)/若二叉树为空，结束返回若二叉树为空，结束返回/若二叉树不为空，遍历左子树，访问根结点，遍历右子树若二叉树不为空，遍历左子树，访问根结点，遍历右子树InOrderTraverse(T-lchild,Visit);Visit(T-data)；InOrderTraverse(T-rchild,Visit);/InOrderTraverse你能写出你能写出后序遍历递归算法了吧后序遍历递归算法了吧?第65页/共188页3后序遍历递归算法后序遍历递归算法voidPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)/采用二叉链表存贮二叉树，采用二叉链表存贮二叉树，visit()是访问结点的函数。本算法中是访问结点的函数。本算法中序遍历以为根结点指针的二叉树，对每个数据元素调用函数序遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit()if(T)/若二叉树为空，结束返回若二叉树为空，结束返回/若二叉树不为空，遍历左子树，遍历右子树，访问根结点若二叉树不为空，遍历左子树，遍历右子树，访问根结点PostOrderTraverse(T-lchild,Visit);PostOrderTraverse(T-rchild,Visit);Visit(T-data)；/PostOrderTraverse第66页/共188页任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。G HD E FB CA第67页/共188页四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述Status InOrderTraverse(BiTree T,Status(*Visit)(ElemType)/采用二叉链表存储结构，采用二叉链表存储结构，Visit是对数据元素操作的应用是对数据元素操作的应用/函数函数.中序遍历二叉树中序遍历二叉树T的非递归算法，对每个数据元素调的非递归算法，对每个数据元素调/用函数用函数Visit。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);if(!Visit(p-data)return ERROR;Push(S,p-rchild);return OK;/InOrderTraverse第68页/共188页Status InOrderTraverse(BiTree T,Status(*Visit)(ElemType)/采用二叉链表存储结构，采用二叉链表存储结构，Visit是对数据元素操作的应用是对数据元素操作的应用/函数。中序遍历二叉树函数。中序遍历二叉树T的非递归算法，对每个数据元素调的非递归算法，对每个数据元素调/用函数用函数Visit。InitStack(S);p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;/非空指针进栈，继续左进非空指针进栈，继续左进 else /上层指针退栈，访问其所指结点，再向右进上层指针退栈，访问其所指结点，再向右进 Pop(S,p);if(!Visit(p-data)return ERROR;p=p-rchild;return OK;/InOrderTraverse第69页/共188页中序遍历二叉树的非递归算法示意图CBDFAGEABCDGEFABCNULLSGetToplchild)&(!T-rchild)count+;/对叶子结点计数 CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);/if/CountLeaf第73页/共188页2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)算法基本思想算法基本思想:从二叉树深度的定义可知，二叉树的二叉树的深度应为其左、右子树深度的最大值加深度应为其左、右子树深度的最大值加1 1。由此，需先分别求得左、右子树的深度，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、求得左、右子树深度的最大值，然后加右子树深度的最大值，然后加 1 1。首先分析二叉树的深度二叉树的深度和它的左左、右子右子树深度树深度之间的关系。第74页/共188页int Depth(BiTree T)/返回二叉树的深度 if(!T)depthval=0;else depthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeft depthRight?depthLeft:depthRight);return depthval;第75页/共188页3、复制二叉树、复制二叉树其基本操作为：生成一个结点。其基本操作为：生成一个结点。根元素根元素T左子树左子树右子树右子树根元素根元素NEWT左子树左子树右子树右子树左子树左子树右子树右子树(后序遍历后序遍历)第76页/共188页BiTNode*GetTreeNode(TElemType item,BiTNode*lptr,BiTNode*rptr)if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=item;T-lchild=lptr;T-rchild=rptr;return T;生成一个二叉树的结点生成一个二叉树的结点(其数据域为其数据域为item,左指针域为左指针域为lptr,右指针域为右指针域为rptr)第77页/共188页BiTNode*CopyTree(BiTNode*T)if(!T)returnNULL;if(T-lchild)newlptr=CopyTree(T-lchild);/复制左子树 else newlptr=NULL;if(T-rchild)newrptr=CopyTree(T-rchild);/复制右子树 else newrptr=NULL;newT=GetTreeNode(T-data,newlptr,newrptr);return newT;/CopyTree第78页/共188页ABCDEFGHKDCBHKGFEA例如：下列二叉树例如：下列二叉树的复制过程如下：的复制过程如下：newT第79页/共188页4 4、建立二叉树的存储结、建立二叉树的存储结构构 为二叉树建立二叉链表为二叉树建立二叉链表输入：输入：二叉树的先序序列二叉树的先序序列结果：结果：二叉树的二叉链表二叉树的二叉链表 遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可在利用是否可在利用遍历，建立遍历，建立二叉链表的所有结点并完成相应结点的二叉链表的所有结点并完成相应结点的链接？链接？基本思想基本思想：输入（输入（在空子树处添加在空子树处添加*的二叉树的）先序序列（设每的二叉树的）先序序列（设每个元素是个元素是一个字符）按先序遍历的顺序，建立二叉链表的所有结点一个字符）按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点的链接并完成相应结点的链接第80页/共188页 D D A A B B C C E E F F T T 先序序列：A B D F C E（在空子树处添加（在空子树处添加*的二叉树的）先序序列：的二叉树的）先序序列：A B D*F*C E*A B D*F*C E*A A F F E E D D C C B B*A A F F E E D D C C B B第81页/共188页Status CreateBiTree(BiTree&T)/输入（在空子树处添加*的二叉树的）先序序列（设每个元/素是一个字 符）按先序遍历的顺序，建立二叉链表，并将/该二叉链表根结点指针赋给T scanf(&ch);if(ch=*)T=NULL;/若ch=*则T=NULL返回 else /若ch!=*if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-date=ch;/建立（根）结点 CreateBiTree(T-lchild);/构造左子树 CreateBiTree(T-rchild);/构造右子树 return OK;/CreateBiTree第82页/共188页83分析：若二叉树的任意两个结点的值都不相同，则二叉树的前序序列和中序序列能唯一确定一棵二叉树。另外，由前序序列和中序序列的定义可知，前序序列中第一个结点必为根结点，而在中序序列中，根结点刚好是左、右子树的分界点，因此，可按如下方法建立二叉树：由二叉树的先序和中序序列建立二叉树由二叉树的先序和中序序列建立二叉树二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根第83页/共188页841.1.用前序序列的第一个结点作为根结点用前序序列的第一个结点作为根结点;2.2.在在中中序序序序列列中中查查找找根根结结点点的的位位置置，并并以以此此为为界界将将中中序序序序列划分为左、右两个序列列划分为左、右两个序列(左、右子树左、右子树););3.3.根根据据左左、右右子子树树的的中中序序序序列列中中的的结结点点个个数数，将将前前序序序序列列去去掉掉根根结结点点后后的的序序列列划划分分为为左左、右右两两个个序序列列，它它们们分分别别是是左左、右子树的前序序列右子树的前序序列;4.4.对对左左、右右子子树树的的前前序序序序列列和和中中序序序序列列递递归归地地实实施施同同样样方方法，直到所得左、右子树为空。法，直到所得左、右子树为空。假设前序序列为假设前序序列为ABDGHCEFIABDGHCEFI，中序序列为中序序列为GDHBAECIFGDHBAECIF，则得到的二叉树如下页所示则得到的二叉树如下页所示第84页/共188页851.1.A A为根结点为根结点A BDGH CEFI GDHB A ECIF BDGHCEFIA2.2.B B为左子树的根结点为左子树的根结点B DGHGDH BCEFIDHGBA3.3.D D为左子树的左子树为左子树的左子树的根结点的根结点第85页/共188页864.4.C C为右子树的根结点为右子树的根结点5.5.F F为右子树的右为右子树的右子树的根结点子树的根结点C E FIE C IF第86页/共188页abcdefgcbdaegf例如例如:aabbccddeeffggabcdefg先序序列中序序列第87页/共188页练习：已知结点的先序序列和中序序列，求整棵二叉树。先序序列：A B C D E F G中序序列：C B E D A F GACBEDFGABCDEFGABCFDEG第88页/共188页6.3.2线索二叉树线索二叉树线索二叉树的定义线索二叉树的定义 线索的描述线索的描述 建立线索二叉树建立线索二叉树 线索二叉树上的运算线索二叉树上的运算第89页/共188页遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如:先序先序序列:A B C D E F G H K中序中序序列:B D C A H G K F E后序后序序列:D C B H K G F E A一、一、线索二叉树的定义线索二叉树的定义第90页/共188页在在这这样样的的线线性性序序列列中中，很很容容易易求求得得某某个个结结点点在在某某种种遍遍历历下下的的直直接接前前驱驱和和后后继继。然然而而，有有时时我我们们希希望望不不进进行行遍遍历历就