数据结构 第五章 树.ppt

《数据结构 第五章 树.ppt》由会员分享，可在线阅读，更多相关《数据结构 第五章 树.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第5章章 树1非线性结构非线性结构：就是指在该结构中至少一个数据元素就是指在该结构中至少一个数据元素有多个前驱（或多个后继）有多个前驱（或多个后继）。树型结构树型结构：是一类用来描述具有层次结构的非线性是一类用来描述具有层次结构的非线性数据结构。其中以树和二叉树最为常用数据结构。其中以树和二叉树最为常用,在计算机中领在计算机中领域中有着广泛的应用。域中有着广泛的应用。线性结构线性结构线性表线性表串（元素为字符）串（元素为字符）数组与广义表数组与广义表一般表一般表堆栈堆栈队列队列顺序顺序/链式链式 存储存储顺序顺序/链式链式/堆堆 存储存储回顾：回顾：2本章要点本章要点n树形结构的概念和术语；

2、树形结构的概念和术语；n二叉树的定义、性质，满二叉树和完全二叉树的概念；二叉树的定义、性质，满二叉树和完全二叉树的概念；n二叉树的遍历及先序、中序、后序及层次遍历方法；二叉树的遍历及先序、中序、后序及层次遍历方法；n线索二叉树与二叉树的恢复；线索二叉树与二叉树的恢复；n树和森林的存储结构树和森林的存储结构,与二叉树之间的相互转换方法；与二叉树之间的相互转换方法；n哈夫曼树的概念及构造。哈夫曼树的概念及构造。35.1 树的概念树的概念n树是以分支关系定义的层次结构，如：树是以分支关系定义的层次结构，如：41.树的定义树树(Tree)(Tree)是由是由n n 0 0个结点的有限集合个结点的有限集

3、合D D，以及该集合上，以及该集合上关系集合关系集合R R构成的。当构成的。当n=0n=0时，称为空树。对于非空树时，称为空树。对于非空树(即即n n 1)1)，满足以下两个条件：，满足以下两个条件：(1)(1)存在一个称为根的特定结点；存在一个称为根的特定结点；(2)(2)其余的结点被分成其余的结点被分成m m 1 1个互不相交的集合个互不相交的集合T T1 1，T T2 2，T Tm m，其中的每个集合都是一棵树，其中的每个集合都是一棵树，T T1 1，T T2 2，T Tm m称为根结称为根结点的点的子树子树。如图所示。如图所示:5树的定义也可以用树的定义也可以用形式化语言形式化语言来描

4、述。树可以用二元组形式来描述。树可以用二元组形式来表示：来表示：Tree=(D,R)Tree=(D,R)其中，其中，D D表示具有相同特性的数据元素的集合，表示具有相同特性的数据元素的集合，R R表示表示D D上数据上数据元素之间的关系，并且满足以下条件：元素之间的关系，并且满足以下条件：若若D D为空集，为空集，TreeTree为空树；若为空树；若D D只含一个数据元素，则只含一个数据元素，则R R为空集，为空集，否则否则R=H,HR=H,H是如下二元关系是如下二元关系:1)1)在在D D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素rootroot，它在关系，它在关系H H下无下

5、无前驱前驱;2)2)若若D-root D-root ，则存在，则存在D-rootD-root的一个划分的一个划分D Dl l、D D2 2、D Dm m,(m0),(m0)，对任意，对任意 j j k(1k(1 j,kj,k m)m)有有 D Dj j D Dk k=,且对任意的且对任意的i(1i(1 i i m)m)，唯一存在数据元素，唯一存在数据元素 x xi i D D，有，有root,x H H；3)3)对应于对应于D-rootD-root的划分的划分,H-root,x,H-,有唯有唯一的一个划分一的一个划分H Hl l、H H2 2、HHm m(m0)(m0)，对任意，对任意j j

6、k(1k(1 j,kj,k m)m)有有 H Hj j H Hk k=，且对任意的，且对任意的i(1i(1 i i m),Hm),Hi i是是D Di i上的二元关系，上的二元关系，T Ti i=(D=(Di i,HHi i)是根是根rootroot的子树。的子树。6树形图树形图是树结构的最主要表示方式。此外还有：是树结构的最主要表示方式。此外还有：文文氏氏图图表表示示法法，也也叫叫嵌嵌套套集集合合表表示示法法；广广义义表表的的表表示形式示形式,也叫嵌套括号表示法；也叫嵌套括号表示法；凹入表示形式凹入表示形式。例如：。例如：2.树的表示 (A(B(E,F(K,L),G),C(H),D(I(M,

7、N,O),J)(A(B(E,F(K,L),G),C(H),D(I(M,N,O),J)7树的结点(Node):(Node):结点的度(Degree):(Degree):叶子(Leaf)(Leaf)或终端结点或终端结点:非终端结点或分支结点或分支结点:树的度(Degree):(Degree):内部结点:孩子(Child)(Child)与与双亲(Parent):(Parent):兄弟(Sibling):(Sibling):结点的结点的祖先(Ancestors)Ancestors):结点的结点的子孙(Descendants):(Descendants):结点的结点的层次(Level):(Level):

8、堂兄弟:树的树的深度(Depth)(Depth)或或高度:3.树的有关术语8有序树(Ordered Tree)(Ordered Tree)：无序树(UnOrdered Tree):(UnOrdered Tree):森林(Forest):(Forest):从逻辑结构上讲从逻辑结构上讲,任何一棵树是一个二元组任何一棵树是一个二元组TreeTree(root,F),(root,F),其中其中rootroot是数据元素称做树的根结点是数据元素称做树的根结点;F;F是是m(m=0)m(m=0)棵树的森林棵树的森林,F,F(T(Tl l,T,T2 2,T,Tm m),),其中其中T Ti i=(r=(ri

9、 i,F,Fi i)称做根称做根rootroot的第的第i i棵子树棵子树;当当m0m0时时,在树根在树根和其子树森林之间存在下列关系和其子树森林之间存在下列关系:RF RFroot,r|i|il,2,m,m0l,2,m,m0这这个个定定义义将将有有助助于于得得到到森森林林和和树树与与二二叉叉树树之之间间转转换换的递归定义。的递归定义。9一、二又树的定义与性质二二叉叉树树(Binary(Binary Tree)Tree)是是另另一一种种树树型型结结构构，是是n n 0 0个个结结点点的的有有穷穷集集合合D D与与D D上上的的关关系系集集合合R R构构成成的的二二元元组组结结构构。当当n=0n

10、=0时时，称称该该二二叉叉树树为为空空二二叉叉树树；否否则则，称称它它为为包包含含了了一一个个根根结结点点以以及及两两棵棵互互不不相相交交、分分别别称称为为左左子子树树和和右右子树的二叉树。即：子树的二叉树。即：(1)(1)每每个个结结点点至至多多只只有有二二棵棵子子树树(二二叉叉树树中中不不存存在在度大于度大于2 2的结点的结点););(2)(2)二二叉叉树树的的子子树树有有左左右右之之分分,其其次次序序不不能能任任意意颠颠倒。倒。思考思考：二叉树就是与度为：二叉树就是与度为2 2的有序树吗？的有序树吗？5.2 二叉树二叉树ABCDEABCDEABCDE10上述数据的结构是上述数据的结构是递

11、归定义：递归定义：二叉树可以有五种基本形态二叉树可以有五种基本形态:(a)(b)(c)(d)(e)性质1：一棵非空一棵非空二叉树的第二叉树的第i i层上至多有层上至多有2 2i-1i-1(i1)个结点个结点。证明：数学归纳法证明：数学归纳法11性质2：一棵一棵深度为深度为h h的二叉树至多有的二叉树至多有2 2h h-1-1个结点个结点,(,(h h1)1)。证证明：由性质明：由性质1,1,深度为深度为h h的二叉树的最大结点数为：的二叉树的最大结点数为：(第第i i层上的最大结点数层上的最大结点数)性质3：对对于于一一棵棵二二叉叉树树T,T,如如果果其其叶叶子子结结点点数数为为n n0 0,

12、度度为为2 2的结点数为的结点数为n n2 2,则则n n0 0=n=n2 2+1+1。证明：证明：12满二叉树:一棵深度为一棵深度为h h且有且有2 2h h-1-1个结点的二叉树。个结点的二叉树。特点：特点：每个分支都有两个孩子结点，并且所有叶子都每个分支都有两个孩子结点，并且所有叶子都在同一层上。在同一层上。13完全二叉树：对于一棵高上对于一棵高上h h，有，有n n个结点的二叉树，个结点的二叉树，除了除了h h层结点，对于层结点，对于h-1h-1层以及上面的结点组成的树是层以及上面的结点组成的树是满二叉树，对于满二叉树，对于h h层的结点尽可能靠左。层的结点尽可能靠左。14性质4:具有

13、具有 n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为:性质5:对对于于一棵有一棵有n n个结点的完全二叉树个结点的完全二叉树(其深度为其深度为 loglog2 2n n)的结点按的结点按照从上至下，和从左到右的顺序对二照从上至下，和从左到右的顺序对二叉树中的所有结点从叉树中的所有结点从1 1开始编号开始编号,则对任则对任意的序号为意的序号为i i的的结点，有如下性质结点，有如下性质:(1)(1)如果如果i1,i1,则其双亲则其双亲Parent(i)Parent(i)的的结点结点序序号为号为 i/2i/2。(2)(2)如果如果2i2in n，则序号为，则序号为i i的的左孩子结点左孩

14、子结点的序号为的序号为2i2i。如。如果果2in,2in,则则序号为序号为i i的结点的结点无左孩子无左孩子(结点结点i i为叶子结点为叶子结点););(3)(3)如果如果2i+12i+1n n，则序号为，则序号为i i的右的右孩子结点孩子结点的序号为的序号为2i2i+1+1；如果如果2i+1n,2i+1n,则结点则结点i i无右孩子。无右孩子。证明证明:根据根据15二叉树的抽象数据类型定义:ADT BinaryTree ADT BinaryTree 数据对象数据对象D D:D:D是具有相同特性的数据元素的集合是具有相同特性的数据元素的集合 数据关系数据关系R R:若若D=D=,则则R=R=,

15、称称BinaryTreeBinaryTree为空二叉树为空二叉树;若若D D,则则R=H,HR=H,H是如下二元关系是如下二元关系:在在D D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root,root,它在关系它在关系H H下无下无前驱前驱;若若D-rootD-root,则存在则存在D-rootD-rootDD1 1,D,Dr r,且且D Dl l D Dr r=若若D D1 1,则则D D1 1中存在唯一的元素中存在唯一的元素x x1 1,root,x,H,H,且存在且存在D Dl l上的关系上的关系H H1 1 H;H;若若D Dr r,则则D Dr r中存在唯一的元素中存

16、在唯一的元素x xr r,root,x,H,H,且且存在存在D Dr r上的关系上的关系H Hr r H;H=root,xH;H=,H,Hl l,H,Hr r;(D(Dl l,H,Hl l)是一棵符合本定义的二叉树是一棵符合本定义的二叉树,称为根的左子树称为根的左子树,(D(Dr r,H,Hr r)是一棵符合本定义的二叉树是一棵符合本定义的二叉树,称为根的右子树。称为根的右子树。16基本操作基本操作:CreateBinaryTree();/CreateBinaryTree();/创建二叉树创建二叉树初始条件：无初始条件：无操作结果：创建一个二叉树操作结果：创建一个二叉树 IsEmpty(T);

17、/IsEmpty(T);/判断二叉树是否为空判断二叉树是否为空初始条件：输入一个树初始条件：输入一个树操作结果：如果该树为空返回操作结果：如果该树为空返回1 1，否则为，否则为0 0 BinaryTreeDepth(T);/BinaryTreeDepth(T);/求二叉树的深度求二叉树的深度(高度高度)初始条件：输入一个树初始条件：输入一个树操作结果：返回该树的深度操作结果：返回该树的深度 NodeValue(T,node);/NodeValue(T,node);/取指定结点的值取指定结点的值初始条件：输入一个树以及指定结点初始条件：输入一个树以及指定结点操作结果：返回结点中的数据操作结果：返

18、回结点中的数据 ParentofNode(T,node);/ParentofNode(T,node);/求指定结点的双亲求指定结点的双亲初始条件：输入树与指定结点初始条件：输入树与指定结点操作结果：返回指定结点操作结果：返回指定结点nodenode的双亲结点的双亲结点 17 LeftChild(T,node);/LeftChild(T,node);/求指定结点的左孩子求指定结点的左孩子初始条件：输入树与指定结点初始条件：输入树与指定结点操作结果：返回指定结点操作结果：返回指定结点nodenode的左孩子的左孩子 RightChild(T,node);/RightChild(T,node);/求

19、指定结点的右孩子求指定结点的右孩子初始条件：输入树与指定结点初始条件：输入树与指定结点操作结果：返回该结点操作结果：返回该结点nodenode的右孩子的右孩子 InsertChild(T,P,LeftOrRight,node);/InsertChild(T,P,LeftOrRight,node);/插入子树插入子树初始条件：输入树、父结点、左或右孩子标识以及指定结点初始条件：输入树、父结点、左或右孩子标识以及指定结点操作结果：将结点操作结果：将结点nodenode插入为插入为T T中中P P所指结点的左或右孩子所指结点的左或右孩子 DeleteChild(T,P,LeftOrRight);/D

20、eleteChild(T,P,LeftOrRight);/删除子树删除子树初始条件：输入树、父结点、左或右孩子标识初始条件：输入树、父结点、左或右孩子标识操作结果：将操作结果：将T T中中P P所指结点的左或右孩子删除，并将删除的所指结点的左或右孩子删除，并将删除的 结点返回结点返回 PreOrderTraverse(T,VISIT);/PreOrderTraverse(T,VISIT);/先序遍历二叉树先序遍历二叉树初始条件：输入树以及访问函数初始条件：输入树以及访问函数操作结果：按照先序方式遍历指定树中的所有结点操作结果：按照先序方式遍历指定树中的所有结点18 InOrderTravers

21、e(T,VISIT);/InOrderTraverse(T,VISIT);/中序遍历二叉树中序遍历二叉树初始条件：输入树以及访问函数初始条件：输入树以及访问函数操作结果：按照中序方式遍历指定树中的所有结点操作结果：按照中序方式遍历指定树中的所有结点 PostOrderTraverse(T,VISIT);/PostOrderTraverse(T,VISIT);/后序遍历二叉树后序遍历二叉树初始条件：输入树以及访问函数初始条件：输入树以及访问函数操作结果：按照后序方式遍历指定树中的所有结点操作结果：按照后序方式遍历指定树中的所有结点 LevelOrderTraverse(T,VISIT);/Lev

22、elOrderTraverse(T,VISIT);/层次遍历二叉树层次遍历二叉树初始条件：输入树以及访问函数初始条件：输入树以及访问函数操作结果：按照层方式遍历指定树中的所有结点操作结果：按照层方式遍历指定树中的所有结点 ADT BinaryTree ADT BinaryTree191.1.顺序存储结构顺序存储结构对于完全二叉树：对于完全二叉树：二、二叉树的存储与实现ABCDEFGHI12345678920n对于非完全二叉树对于非完全二叉树,如果用顺序结构存储如果用顺序结构存储,则应将其每个结则应将其每个结点与完全二叉树上的结点相对照点与完全二叉树上的结点相对照,存储在一维数组的相应分量存储在

23、一维数组的相应分量中中,以以0 或或#表示不存在的结点。表示不存在的结点。例如：例如：在最坏的情况下：单分支二叉树！一个深度为在最坏的情况下：单分支二叉树！一个深度为K K的树却只有的树却只有K K个个结点，即树中不存在度为结点，即树中不存在度为2 2的结点，需要长度为的结点，需要长度为2 2k k-1-1的一维数组的一维数组。ABCDEFG123456789101112131415212.链式存储结构链式存储结构一般有两种形式的链式存储结构：一般有两种形式的链式存储结构：(1)含有两个指针域的结点结构；含有两个指针域的结点结构；(2)含有三个指针域的结点结构。含有三个指针域的结点结构。结点形

24、式结点形式 DataParentleftChildrightChild两个指针域的结点结构两个指针域的结点结构(二叉链表二叉链表)leftChildrightChildData三个指针域的结点结构三个指针域的结点结构(三叉链表三叉链表)leftChildrightChildDataParent22在含有在含有n n个结点的二叉链个结点的二叉链表中有表中有n+1n+1个空链域个空链域 ！23/二叉链表结点类型二叉链表结点类型typedef char ElemType;/typedef char ElemType;/设定数据类型设定数据类型 typedef struct BiTreeNode ty

25、pedef struct BiTreeNode ElemType data;ElemType data;struct BiTreeNode*leftChild,*rightChild;struct BiTreeNode*leftChild,*rightChild;BiTNode,*BiTree,*BTNPtr;BiTNode,*BiTree,*BTNPtr;/三叉链表结点类型三叉链表结点类型typedef char ElemType;/typedef char ElemType;/设定数据类型设定数据类型 typedef struct BiTreeNode typedef struct BiT

26、reeNode ElemType data;ElemType data;struct BiTreeNode*leftChild,*rightChild,struct BiTreeNode*leftChild,*rightChild,*parent*parent;BiTNode,*BiTree,*BTNPtr;BiTNode,*BiTree,*BTNPtr;二叉链表的存储结构定义24BiTree CreateBinaryTree();/BiTree CreateBinaryTree();/创建一个空的二叉树创建一个空的二叉树BiTree CreateBTreeNode(ElemType data

27、);BiTree CreateBTreeNode(ElemType data);/以以datadata为数据创建一个结点为数据创建一个结点Status IsEmpty BiTree bt);/Status IsEmpty BiTree bt);/判断该树是否为空判断该树是否为空 int BinaryTreeDepth(BiTree bt);/int BinaryTreeDepth(BiTree bt);/返回树的深度高度返回树的深度高度ElemType NodeValue(BiTree node);/ElemType NodeValue(BiTree node);/返回指定结点的值返回指定结点

28、的值BiTree LeftChild(BiTree node);/BiTree LeftChild(BiTree node);/取指定结点的左孩子取指定结点的左孩子BiTree RightChild(BiTree node);/BiTree RightChild(BiTree node);/取指定结点的右孩子取指定结点的右孩子Status InsertChild(BiTree parent,int LeftOrRight,BiTree node);Status InsertChild(BiTree parent,int LeftOrRight,BiTree node);/将新结点插入到指定结点

29、的孩子中将新结点插入到指定结点的孩子中BiTree DeleteChild(BTNPtr node,int LeftOrright);BiTree DeleteChild(BTNPtr node,int LeftOrright);/删除指定结点的左孩子或右孩子删除指定结点的左孩子或右孩子void PreOrderTraverse(BiTree bt);/void PreOrderTraverse(BiTree bt);/前序遍历二叉树前序遍历二叉树void InOrderTraverse(BiTree bt);/void InOrderTraverse(BiTree bt);/中序遍历二叉树中

30、序遍历二叉树void PostOrderTraverse(BiTree bt);/void PostOrderTraverse(BiTree bt);/后序遍历二叉树后序遍历二叉树void Levelvoid LevelO OrderTraverse(BiTree bt);/rderTraverse(BiTree bt);/按层遍历二叉树按层遍历二叉树基本操作的函数原型说明基本操作的函数原型说明(部分部分)25二二叉叉树树遍遍历历(Traversing Binary Tree)：是是指指按按一一定定顺顺序序访访问问树树中中的的每每个个结结点点，使使得得每每个个结结点点都都被被访访问问一一次次，

31、而且仅被访问一次。而且仅被访问一次。二二叉叉树树遍遍历历是是各各类类操操作作的的基基础础。一一次次完完整整的的遍遍历历，按按访访问问的的先先后后顺顺序序列列出出来来，就就得得到到了了树树结结点点信信息息的的一一个个线线性排列。性排列。根据二叉树的递归定义可知，二叉树是由三个基本单根据二叉树的递归定义可知，二叉树是由三个基本单元组成元组成:根结点、左子树和右子树。因此根结点、左子树和右子树。因此，若能依次遍历若能依次遍历这三部分这三部分，便是遍历了整个二叉树。便是遍历了整个二叉树。假如以假如以L L、D D、R R分别表示遍历左子树、访问根结点和分别表示遍历左子树、访问根结点和遍历右子树遍历右子

32、树,则可有：则可有：DLRDLR、LDRLDR、LRDLRDDRLDRL、RDLRDL、RLDRLD三、二叉树的遍历261.先序遍历二叉树先序遍历二叉树的操作定义为的操作定义为:若二叉树为非空若二叉树为非空,则：则：(1)先先访问根结点访问根结点;(2)然后然后先序先序访问访问左子树左子树;(3)最后最后先序先序访问访问右子树。右子树。2.中序遍历二叉树中序遍历二叉树的操作定义为的操作定义为:若二叉树为非空若二叉树为非空,则则 (1)先先中序中序访问访问左子树左子树;(2)然后然后访问根结点访问根结点;(3)最后最后中序中序访问访问右子树。右子树。3.后序遍历二叉树的后序遍历二叉树的操作定义为

33、操作定义为:若二叉树为非空若二叉树为非空,则则 (1)先先后序后序访问访问左子树左子树;(2)然后然后后序后序访问访问右子树右子树;(3)最后最后访问根结点。访问根结点。27先序遍历二叉树的递归算法：先序遍历二叉树的递归算法：采用二叉链表作为存储结构，二叉树先序遍历算法如下：采用二叉链表作为存储结构，二叉树先序遍历算法如下：void PreOrderTraverse(Bvoid PreOrderTraverse(Bi iTree bt)Tree bt)if(bt!=NULL)if(bt!=NULL)visit(bt);visit(bt);PreOrderTraverse(bt-leftChil

34、d);PreOrderTraverse(bt-leftChild);PreOrderTraverse(bt-rightChild);PreOrderTraverse(bt-rightChild);/PreOrderTraverse /PreOrderTraverse注：关于注：关于visit()visit()的约定的约定28中序遍历二叉树的递归算法：中序遍历二叉树的递归算法：采用二叉链表作为存储结构，二叉树中序遍历算法如下：采用二叉链表作为存储结构，二叉树中序遍历算法如下：void InOrderTraverse(Bvoid InOrderTraverse(Bi iTree bt)Tree b

35、t)if(bt!=NULL)if(bt!=NULL)InOrderTraverse(bt-leftChild);InOrderTraverse(bt-leftChild);visit(bt);visit(bt);InOrderTraverse(bt-rightChild);InOrderTraverse(bt-rightChild);/InOrderTraverse /InOrderTraverse29后序遍历二叉树的递归算法：后序遍历二叉树的递归算法：采用二叉链表作为存储结构，二叉树后序遍历算法如下：采用二叉链表作为存储结构，二叉树后序遍历算法如下：void PostOrderTravers

36、e(Bvoid PostOrderTraverse(Bi iTree bt)Tree bt)if(bt!=NULL)if(bt!=NULL)PostOrderTraverse(bt-leftChild);PostOrderTraverse(bt-leftChild);PostOrderTraverse(bt-rightChild);PostOrderTraverse(bt-rightChild);visit(bt);visit(bt);/PostOrderTraverse /PostOrderTraverse30如图所示的二叉树三种遍历得到的序列分别为如图所示的二叉树三种遍历得到的序列分别为:

37、先序序列:中序序列:后序序列:举例举例314.递归遍历的非递归化处理递归遍历的非递归化处理上面给出的三种遍历方式都递归算法，结构清晰、简洁，上面给出的三种遍历方式都递归算法，结构清晰、简洁，这三种算法的区别仅仅是访问函这三种算法的区别仅仅是访问函数数visitvisit的的位置不同而已。位置不同而已。递归算法尽管简洁，容易理解，但执行效率低下，另外也递归算法尽管简洁，容易理解，但执行效率低下，另外也不是所有程序设计语言都提供递归。不是所有程序设计语言都提供递归。遍历算法的执行过程：遍历算法的执行过程：32假定我们已经定义了栈的数据类型与二叉链表数据类型相同，假定我们已经定义了栈的数据类型与二叉

38、链表数据类型相同，并假定栈的空间足够大，不用考虑栈的溢出问题。下面先以中序并假定栈的空间足够大，不用考虑栈的溢出问题。下面先以中序为例讨论其非递归的实现。为例讨论其非递归的实现。设设S S为一个栈，为一个栈，ptrptr为指向二叉树结点的活动指针，初始时指向为指向二叉树结点的活动指针，初始时指向根结点。算法的核心思想是：根结点。算法的核心思想是：(1)(1)当当ptrptr非空时，将非空时，将ptrptr所指结点的地址进栈，然后将所指结点的地址进栈，然后将ptrptr指指向该结点的左孩子；向该结点的左孩子；(2)(2)当当ptrptr为空时，则从栈中弹出一个元素，赋给为空时，则从栈中弹出一个元

39、素，赋给ptrptr，并访问，并访问它，然后将它，然后将ptrptr指该结点的右孩子。指该结点的右孩子。重复上述过程，直到重复上述过程，直到ptrptr为空，并且栈也为空为止。为空，并且栈也为空为止。33按此过程得到用堆栈方式实现的中序遍历的算法如下：按此过程得到用堆栈方式实现的中序遍历的算法如下：void InOrderTraverse2(BiTree T)void InOrderTraverse2(BiTree T)/采用二叉链表存储结构中序遍历二叉树采用二叉链表存储结构中序遍历二叉树T T的非递归算法。的非递归算法。InitStack(S);ptr=T;/InitStack(S);ptr

40、=T;/初始化栈，初始化栈，ptrptr指向根结点指向根结点 while(ptr|!StackEmpty(S)while(ptr|!StackEmpty(S)while(ptr)/while(ptr)/当前指针非空当前指针非空 Push(S,ptr);/Push(S,ptr);/根指针进栈根指针进栈 ptr=ptr-leftChild;/ptr=ptr-leftChild;/遍历左子树遍历左子树 if(!StackEmpty(S)if(!StackEmpty(S)/当前指针为空，且栈非空时当前指针为空，且栈非空时 Pop(S,ptr);/Pop(S,ptr);/根指针退栈根指针退栈 visit

41、(ptr);visit(ptr);ptr=ptr-rightChild;/ptr=ptr-rightChild;/遍历右子树遍历右子树 /InOrderTraverse2 /InOrderTraverse2 345.按层次遍历按层次遍历按层遍历：就是先访问第一层结点，然后再访问第：就是先访问第一层结点，然后再访问第二层结点，紧接着再访问第三层结点，一直到访问完二层结点，紧接着再访问第三层结点，一直到访问完树中的所有结点。树中的所有结点。根据这个遍历方法根据这个遍历方法，对于图，对于图5-9(a)5-9(a)的二叉树，按层的二叉树，按层遍历结果为遍历结果为A B C D E F GA B C D

42、 E F G。实现此遍历要用到队列数据结构：先将树根存储到实现此遍历要用到队列数据结构：先将树根存储到队列中，从队列中取出结点，访问该结点的数据，如队列中，从队列中取出结点，访问该结点的数据，如果该结点的左孩子不空，就将做孩子进入队列，如果果该结点的左孩子不空，就将做孩子进入队列，如果该结点的右孩子不空，就将右孩子进入队列，然后再该结点的右孩子不空，就将右孩子进入队列，然后再从队列中取第一个元素，重复操作，一直到队列为空从队列中取第一个元素，重复操作，一直到队列为空为止为止。35假定我们已经创建了与二叉链表相同元素类型的队列结构。假定我们已经创建了与二叉链表相同元素类型的队列结构。则用队列结构

43、来实现树的按层遍历算法如下：则用队列结构来实现树的按层遍历算法如下：void LevelOrderTraverse(BiTree bt)void LevelOrderTraverse(BiTree bt)BiTree ptr=NULL;BiTree ptr=NULL;QueueInit(Q);QueueInit(Q);if(bt!=NULL)if(bt!=NULL)EnQueue(Q,bt);EnQueue(Q,bt);while(!QueueEmpty(Q)while(!QueueEmpty(Q)ptr=DelQueue(Q);ptr=DelQueue(Q);visit(ptr);visit

44、(ptr);if(ptr-leftChild!=NULL)if(ptr-leftChild!=NULL)EnQueue(Q,ptr-leftChild);EnQueue(Q,ptr-leftChild);if(ptr-rightChild!=NULL)if(ptr-rightChild!=NULL)EnQueue(Q,ptr-rightChild);EnQueue(Q,ptr-rightChild);/LevelOrderTraverse /LevelOrderTraverse366.二叉链表的创建与恢复二叉链表的创建与恢复遍历是二叉树各种操作的基础。遍历是二叉树各种操作的基础。如如:结结点点

45、的的查查找找；求求结结点点的的双双亲亲；求求结结点点的的孩孩子子；判判定定结结点点所所在在层层次次；求求结结点点的的个个数数；判判定定二二叉叉树树的的等等价价性；求树的高度等等。性；求树的高度等等。区别：在于遍历过程中的不同访问操作。区别：在于遍历过程中的不同访问操作。如何创建二叉树？如何创建二叉树？(1)(1)按先序遍历过程创建二叉树按先序遍历过程创建二叉树;(2)(2)由遍历序列恢复二叉树。由遍历序列恢复二叉树。37(1)(1)按先序遍历过程创建二叉树按先序遍历过程创建二叉树 给定一棵二叉树，要建立与之对应的二叉链表存储结构，先给定一棵二叉树，要建立与之对应的二叉链表存储结构，先按先序遍历

46、规则写出前序序列。要注意的是，必须严格按先序遍按先序遍历规则写出前序序列。要注意的是，必须严格按先序遍历过程写出来，即使某个结点的子树为空，也要用一个特定符号历过程写出来，即使某个结点的子树为空，也要用一个特定符号写出写出(比如用比如用#)。与普通先序遍历过程相同，不同的只是访问。与普通先序遍历过程相同，不同的只是访问处理，即处理，即visit()visit()：依次输入该先序序列，如果输入的是：依次输入该先序序列，如果输入的是#，则表，则表示空子树，否则生成一个结点。示空子树，否则生成一个结点。若建立一棵如图若建立一棵如图5-9a5-9a所示的二叉树，则创建过程中输入的字所示的二叉树，则创建

47、过程中输入的字符序列为：符序列为：ABD#EF#G#C#ABD#EF#G#C#38算法如下：算法如下：BiTree CreateBiTree()BiTree CreateBiTree()/按先序序列输入二叉树中结点的值，空树用按先序序列输入二叉树中结点的值，空树用#表示表示 BiTree T;char ch;BiTree T;char ch;scanf(&ch);scanf(&ch);if(ch=if(ch=#)T=NULL;/)T=NULL;/空树空树 else else T=(BiTNode*)malloc(sizeof(BiTNode)/T=(BiTNode*)malloc(sizeof

48、(BiTNode)/生成根结点生成根结点 T-data=ch;/T-data=ch;/把值赋给根结点把值赋给根结点 T-leftChild=CreateBiTree();/T-leftChild=CreateBiTree();/构造左子树构造左子树 T-rightChild=CreateBiTree();/T-rightChild=CreateBiTree();/构造右子树构造右子树 return T;return T;/CreateBiTree/CreateBiTree39（2 2）根据遍历序列恢复二叉树）根据遍历序列恢复二叉树 可可以以证证明明，若若二二叉叉树树的的各各结结点点值值均均不不

49、相相同同，则则由由二二叉叉树树的的前前序序序序列列和和中中序序序序列列、中中序序序序列列和和后后序序序序列列、层层次次序序列列和和中中序序序序列均能唯一确定一棵二叉树。列均能唯一确定一棵二叉树。注意：先序序列和后序序列不能唯一确定一棵二叉树。注意：先序序列和后序序列不能唯一确定一棵二叉树。这里以先序序列和中序序列为例来说明确定过程。这里以先序序列和中序序列为例来说明确定过程。设先序序列为：设先序序列为：u u1 1,u,u2 2,u,u3 3,u,un n，中中序序序序列列为为：u up1p1,u,up2p2,u,up3p3,u,upnpn，其其中中p p1 1,p,p2 2,p,p3 3,p

50、,pn n是是1,2,n1,2,n的一个排列。的一个排列。已知一棵二叉树的先序遍历与中序遍历结果分别为：已知一棵二叉树的先序遍历与中序遍历结果分别为：A B C D E F G H IA B C D E F G H I D C E B A G F H I D C E B A G F H I 40首先可以首先可以确定确定结点结点A A是二叉树的根结点是二叉树的根结点。根据中序遍历的特点，根据中序遍历的特点，可以知道在可以知道在A A之前的之前的D D、C C、E E、B B是二叉树的左子树结点，在是二叉树的左子树结点，在A A之后之后的的G G、F F、H H、I I是该二叉树的右子树结点，然后