数据结构PPT第六章树和二叉树

《数据结构PPT第六章树和二叉树》由会员分享，可在线阅读，更多相关《数据结构PPT第六章树和二叉树（188页珍藏版）》请在装配图网上搜索。

1、第六章第六章树和二叉树树和二叉树数据结构可分为线性结构和非线性结构两大类。前面几数据结构可分为线性结构和非线性结构两大类。前面几章主要研究的是线性结构。一般的，线性结构只能用来描章主要研究的是线性结构。一般的，线性结构只能用来描述数据元素之间的线性顺序关系，而很难反映元素之间的述数据元素之间的线性顺序关系，而很难反映元素之间的层次层次( (分支分支) )关系。本章将要讨论一种非线性数据结构，所关系。本章将要讨论一种非线性数据结构，所谓非线性结构是指在结构中至少存在一个数据元素，它具谓非线性结构是指在结构中至少存在一个数据元素，它具有两个或两个以上的直接后继或直接前驱。有两个或两个以上的直接后继

2、或直接前驱。树形结构，是一类非常重要的非线性数据结构，它用于树形结构，是一类非常重要的非线性数据结构，它用于描述数据元素之间的层次关系。树形结构在客观世界中广描述数据元素之间的层次关系。树形结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。经常用到的两种结构是树和二叉树。来形象表示。经常用到的两种结构是树和二叉树。本章先介绍树、二叉树的定义、性质及存储结构，重点本章先介绍树、二叉树的定义、性质及存储结构，重点讨论二叉树的存储结构及其各种操作，并研究树和森林与讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树之

3、间的转换关系，最后介绍树的应用。二叉树之间的转换关系，最后介绍树的应用。 引 言内容提要 6.1 树的定义和基本术语树的定义和基本术语 6.2 二叉树二叉树 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树 6.4 树和森林树和森林 6.6 赫夫曼树及其应用赫夫曼树及其应用 小结小结6.1 树的定义树的定义 和基本术语和基本术语 树树(Tree)(Tree)是包含是包含n(n0)n(n0)个结点的有限集。在任意个结点的有限集。在任意一棵一棵非空非空树中：树中： （1 1） 有且仅有一个特定的称为有且仅有一个特定的称为根根(Root)(Root)的结点；的结点； (2) (2) 当当n1n1

4、时，其余的结点可分为时，其余的结点可分为m(mm(m0)0)个个互不相交的子互不相交的子集集T T1 1,T,T2 2,T,T3 3T Tm m，其中每个子集又是一棵树，并称其为，其中每个子集又是一棵树，并称其为子子树树( (SubtreeSubtree) )。 树也可以这样定义：树也可以这样定义： 树是由根结点和若干棵子树构成的。树是由根结点和若干棵子树构成的。可以看出，在树的定义中用了递归的概念，即在树的定义可以看出，在树的定义中用了递归的概念，即在树的定义中又用到树的定义，它道出了树的固有特性，因此递归算中又用到树的定义，它道出了树的固有特性，因此递归算法是树结构算法的显著特点。法是树结

5、构算法的显著特点。 树的定义上图上图(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

6、，T12=FT12=F。T11T11和和T12T12都是都是B B的子树。而的子树。而T11T11中中E E是根结点，是根结点，KK和和LL是是E E的的两棵互不相交的子树，其本身又是只有一个根结点的树。两棵互不相交的子树，其本身又是只有一个根结点的树。数据对象数据对象 D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 若若D为空集，则称为空树为空集，则称为空树 。 否则否则: (1) 在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root； (2) 当当n1时，其余结点可分为时，其余结点可分为m (m0)个互个互 不相交的有限集不相交的有限集T1, T2

7、, , Tm，其中每一，其中每一 棵子集本身又是一棵符合本定义的树，棵子集本身又是一棵符合本定义的树， 称为根称为根root的子树。的子树。 数据关系数据关系 R：ADT Tree 基本操作：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类 Root(T) / 求树的根结点求树的根结点 查找类：查找类：Value(T, cur_e) / 求当前结点的元素值求当前结点的元素值 Parent(T, cur_e) / 求当前结点的双亲结点求当前结点的双亲结点LeftChild(T, cur_e) / 求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T, cur_e)

8、/ 求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T) / 判定树是否为空树判定树是否为空树 TreeDepth(T) / 求树的深度求树的深度TraverseTree( T, Visit() ) / 遍历遍历InitTree(&T) / 初始化置空树初始化置空树 插入类：插入类：CreateTree(&T, definition) / 按定义构造树按定义构造树Assign(T, cur_e, value) / 给当前结点赋值给当前结点赋值InsertChild(&T, &p, i, c) / 将以将以c为根的树插入为结点为根的树插入为结点p的第的第i

9、棵子树棵子树 ClearTree(&T) / 将树清空将树清空 删除类：删除类：DestroyTree(&T) / 销毁树的结构销毁树的结构DeleteChild(&T, &p, i) / 删除结点删除结点p的第的第i棵子树棵子树树的表示方法有四种，各用于不同的目的。树的表示方法有四种，各用于不同的目的。(1) (1) 直观表示法：就是一棵树的直观表示。直观表示法：就是一棵树的直观表示。(2) (2) 广义表示法：下图广义表示法：下图 (a)(a)是以广义表的形式表示的，根作为是以广义表的形式表示的，根作为由子树森林组成的表的名字写在表的左边。树的形式化表示法由

10、子树森林组成的表的名字写在表的左边。树的形式化表示法主要用于树的理论描述。主要用于树的理论描述。(3) (3) 凹入表示法：下图凹入表示法：下图(b)(b)用的是凹入表示法用的是凹入表示法( (类似书的编目类似书的编目) )。树的凹入表示法主要用于树的屏幕和打印显示。树的凹入表示法主要用于树的屏幕和打印显示。(4(4）嵌套集合表示法：参见）嵌套集合表示法：参见P120P120图图6.26.2。表示方法的多样性，正说明了树结构在日常生活中及计算机表示方法的多样性，正说明了树结构在日常生活中及计算机程序设计中的重要性。一般来说，分等级的分类方案都可用层程序设计中的重要性。一般来说，分等级的分类方案

11、都可用层次结构来表示，也就是说，都可产生一个树结构。次结构来表示，也就是说，都可产生一个树结构。 树的表示形式树的表示形式ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2树根例如例如: :基基 本本 术术 语语结点结点: :结点的度结点的度: :树的度树的度: :叶子结点叶子结点: :分支结点分支结点: :数据元素及若干指向子树的分支拥有的子树数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM(从根到结点的)路径：路径：结点的层次结点的层次: :树的深度：树的深度： 由从根根到该结点所经分支和结点构成ABCDEFGHI

12、JMKL假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次孩子结点：结点子树的根双亲结点：孩子结点的直接前驱兄弟结点：同一双亲的孩子间堂兄弟：双亲在同一层的结点祖先结点：从根到该结点所经分支的所有结点子孙结点：以某结点为根的子树中的任一结点() 有确定的根；() 树根和子树根之间为有向关系。有向树：有向树：有序树：有序树：子树之间存在确定的次序关系。无序树：无序树：子树之间不存在确定的次序关系。任何一棵非空树是一个二元组 Tree = （root，F）其中：root 被称为根结点 F 被称为子树森林森林：森林：是m（m0）棵互不相交的树的集合ArootBC

13、DEFGHIJMKLF对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )6.2 二二 叉叉 树树6.2.1 二叉树的定义二叉树的定义 二叉树（二叉树（Binary Tree）或为空树，或是由一个）或为空树，或是由

14、一个根结点加上两棵分别称为根结点加上两棵分别称为左子树左子树和和右子树右子树的、的、互不相交的互不相交的二叉树组成。二叉树组成。ABCDEFGHK根结点左子树右子树二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树抽象数据类型二叉数定义ADT BinaryTree 数据对象数据对象 D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 数据关系数据关系R： 若若D = ，则，则R= ，称称BinaryTree为空二叉树为空二叉树; 若若D ，则，则R=H，

15、H是如下二元关系：是如下二元关系： （1）在）在D中存在唯一的称为中存在唯一的称为根根的数据元素的数据元素root，它在关系，它在关系H下下无前驱无前驱； (2)若若Droot，则存在，则存在Droot=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）是一棵符合本定义的二叉树，称为根）是一棵符合本定义的二叉树，称为根

16、root的的左左子树子树，（，（Dr ,Hr）是一棵符合本定义的二叉树，称为根）是一棵符合本定义的二叉树，称为根root的的右子树右子树，二叉树的主要基本操作二叉树的主要基本操作：查查 找找 类类插插 入入 类类删删 除除 类类 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(); InOrderTravers

17、e(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit(); InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);ClearBiTree(&T); DestroyBiTree(&T);DeleteChild(T, p, LR);6.2.2 二叉树二叉树 的性质的性质 性质性质1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1

18、)用归纳法证明用归纳法证明： 归纳基归纳基： 归纳假设：归纳假设： 归纳证明：归纳证明：i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；假设对所有的 j，1 j i，命题成立；二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 。性质性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。证明：证明： 基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 。 性质性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。证明：证明

19、：设设 二叉树上结点总数 n = n0 + n1 + n2又又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1 。两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号编号为为 1 至至 n 的结点的结点一一对应。123456789 10 11 12 13 14 15abcdefghij性质性质 4 ： 具有 n 个结点的完全二叉树的深度深度为 log2n +1 。证明：证明：设设完全二叉树的深度为 k 则

20、根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子右孩子结点。6.2.3 二叉树的存储结构二叉树的存储结构二、二叉树的链式二、二叉树的链式 存储结构存储结构一、一、 二叉树的顺序二叉树的顺序 存储结构存储结构#define MAX_TREE_SIZE 100 / 二叉树的最大结点数typedef TElemType SqBiTreeMAX_ TREE_SIZE; / 0号单元存储根结点SqBiTree bt;一、一、 二叉树

21、的顺序存储结构二叉树的顺序存储结构按照顺序存储结构的定义，在此约定，用一按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元依次自上而下、自左至组地址连续的存储单元依次自上而下、自左至右存储二叉树上的结点元素。因此，必须把结右存储二叉树上的结点元素。因此，必须把结点安排成一个适当的线性序列，使得结点在这点安排成一个适当的线性序列，使得结点在这个序列中的相互位置能反映出结点之间的逻辑个序列中的相互位置能反映出结点之间的逻辑关系。关系。在一棵有在一棵有n n个结点的完全二叉树中，从树根起，个结点的完全二叉树中，从树根起，自上层到下层，每层从左到右地给结点编号，自上层到下层，每层从左到右地给结

22、点编号，就能得到一个足以反映整个二叉树结构的线性就能得到一个足以反映整个二叉树结构的线性序列，如下图所示。序列，如下图所示。二叉树的顺序存储结构二叉树的顺序存储结构练习练习:ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 131401326二、二叉树的链式存储表示二、二叉树的链式存储表示1. 1. 二叉链表二叉链表2三叉链表三叉链表3 3双亲链表双亲链表4线索链表线索链表ADEBCF rootlchild data rchild结点结构结点结构:1. 1. 二叉链表二叉链表二叉链表二叉链表ABCDEF二叉树二叉树typedef struct Bi

23、TNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下: :ADEBCF root 2三叉链表三叉链表parent lchild data rchild结点结构结点结构: typedef struct TriTNode / 结点结构结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct T

24、riTNode *parent; /双亲指针 TriTNode, *TriTree;parent lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下: :0123456B2C0A -1D2E3F4 data parent结点结构结点结构:3 3双亲链表双亲链表LRTagLRRRL typedef struct BPTNode / 结点结构结点结构 TElemType data; int *parent; / 指向双亲的指针 char LRTag; / 左、右孩子标志域 BPTNode typedef struct BPTree / 树结构树结构 BP

25、TNode nodesMAX_TREE_SIZE; int num_node; / 结点数目 int root; / 根结点的位置 BPTree6.3.1二叉树的遍历二叉树的遍历6.3 遍历二叉树和遍历二叉树和线索二叉树线索二叉树一、问题的提出一、问题的提出二、先左后右的遍历算法二、先左后右的遍历算法三、算法的递归描述三、算法的递归描述四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述五五、遍历算法的应用举例遍历算法的应用举例 如何按着某条搜索路径如何按着某条搜索路径巡访巡访二叉二叉树中的每个结点，使得每个结点树中的每个结点，使得每个结点均被均被访问一次访问一次，而且，而且仅被访问一次仅

26、被访问一次。一、问题的提出一、问题的提出“访问访问”的含义可以很广，如：输出结的含义可以很广，如：输出结点的信息等。点的信息等。 “遍历遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构， 每个结点有两个后继每个结点有两个后继，则存在如何遍历存在如何遍历即按什么样的搜索搜索路径路径遍历的问题。二叉树的遍历方法二叉树的遍历方法 二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：令：L L：遍历左子树 D D：访问根结点 R R：遍历右子树 有六种遍历方法： D DL LR

27、 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 B58 先序遍历（先序遍历（ D DL LR R ） 若二叉树非空若二叉树非空 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树；）先序遍历左子树； （3 3）先序遍历右子树）先序遍历右子树； 先序遍历序列：先序遍历序列： A A F F G G E E D D C C B B例：先序遍历右

28、图所示的二叉树例：先序遍历右图所示的二叉树 （1 1）访问根结点）访问根结点A A （2 2）先序遍历左子树：即按先序遍历左子树：即按D DL LR R的顺序遍历的顺序遍历左子树左子树 （3 3）先序遍历右子树：即按）先序遍历右子树：即按D DL LR R的顺序遍历的顺序遍历右子树右子树A BCDFGE二、先左后右的遍历算法二、先左后右的遍历算法59中序遍历（中序遍历（ L LD DR R ）若二叉树非空若二叉树非空（1 1）中序遍历左子树）中序遍历左子树（2 2）访问根结点）访问根结点（3 3）中序遍历右子树）中序遍历右子树 中序遍历序列： A A F F G G E E D D C C B

29、 B例：中序遍历右图所示的二叉树例：中序遍历右图所示的二叉树 （1 1）中序遍历左子树：即按）中序遍历左子树：即按L LD DR R的顺序遍历的顺序遍历左子树左子树 （2 2）访问根结点）访问根结点 A A （3 3）中序遍历右子树：即按中序遍历右子树：即按L LD DR R的顺序遍历的顺序遍历右子树右子树D BCGFAE60后序遍历（后序遍历（L LR RD D）若二叉树非空若二叉树非空（1 1）后序遍历左子树）后序遍历左子树（2 2）后序遍历右子树）后序遍历右子树（3 3）访问根结点）访问根结点 后序遍历序列：例：后序遍历右图所示的二叉树例：后序遍历右图所示的二叉树 （1 1）后序遍历左子

30、树：即按）后序遍历左子树：即按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 GCEAFB61 e e d d c c b b f f a a + + * * / / - - - - 后序遍历序列： 中序遍历序列： 先序遍历序列：例：先例：先中序遍历序遍历、中序遍历、中序遍历序遍历、中序遍历、后后序遍历下图所示的二叉树序遍历下图所示的二叉树前缀表达式前缀表达式中缀表达式中缀表达式后缀表达式

31、后缀表达式- + a * b - c d /e fa + b * c - d - e /fa b c d - * + e f /-R A DE C HF GBK练习：求下列二叉链表和二叉树的三种遍历次序练习：求下列二叉链表和二叉树的三种遍历次序ABCDEFGHK这实际上是这实际上是先序遍历的递归定义，先序遍历的递归定义，我们知道递归定义包括两个部分我们知道递归定义包括两个部分：1 1）基本项基本项（也叫终止项）；（也叫终止项）； 2 2）递归项递归项 若二叉树非空若二叉树非空 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树）先序遍历左子树 （3 3）先序遍历右子树；）先序遍历右

32、子树；先序遍历递归定义先序遍历递归定义递归项递归项上面介绍了三种遍历方法，显然是用递归的方式给出的三种遍历方上面介绍了三种遍历方法，显然是用递归的方式给出的三种遍历方法，以先序为例：法，以先序为例：先序遍历（先序遍历（D DL LR R）的定义：）的定义：该定义隐含着该定义隐含着若二叉若二叉树为空，结束树为空，结束 三、算法的递归描述三、算法的递归描述上面先序遍历的定义等价于：上面先序遍历的定义等价于：若二叉树为空，结束若二叉树为空，结束 基本项基本项（也叫终止项）（也叫终止项）若二叉树非空若二叉树非空 递归项递归项 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树）先序遍历左子

33、树 （3 3）先序遍历右子树；）先序遍历右子树； 下面给出下面给出先序、中序、后序遍历递归算法，为了增加算法的可先序、中序、后序遍历递归算法，为了增加算法的可读性，这里对书上算法作了简化，没有考虑访问结点出错的情况读性，这里对书上算法作了简化，没有考虑访问结点出错的情况（即我们假设调用函数（即我们假设调用函数visit( )visit( )访问结点总是成功的。访问结点总是成功的。1先序遍历递归算法先序遍历递归算法 void PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉链表存贮二叉树，采用二叉链表存贮二叉树， visit

34、( )是访问结点的函数。本算是访问结点的函数。本算法法/先序遍历以为根结点指针的二叉树，对每个数据元素调用函先序遍历以为根结点指针的二叉树，对每个数据元素调用函数数/Visit( ) if (T) /若二叉树为空，结束返回若二叉树为空，结束返回 / 若二叉树不为空，访问根结点；遍历左子树，遍历右子树若二叉树不为空，访问根结点；遍历左子树，遍历右子树 Visit(T-data)； PreOrderTraverse(T-lchild, Visit); PreOrderTraverse(T-rchild, Visit); /PreOrderTraverse最简单的最简单的Visit函数是：函数是：

35、Status PrintElement(TElemType e) /输出元素输出元素e的值的值 printf(e); return OK; D D A A B B C C E E FFT T2 中序遍历递归算法中序遍历递归算法 void InOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉链表存贮二叉树，采用二叉链表存贮二叉树， visit( )是访问结点的函数。本算法中是访问结点的函数。本算法中序遍历以为根结点指针的二叉树，对每个数据元素调用函数序遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit( ) if (T)

36、 /若二叉树为空，结束返回若二叉树为空，结束返回 / 若二叉树不为空，遍历左子树，访问根结点，遍历右子树若二叉树不为空，遍历左子树，访问根结点，遍历右子树 InOrderTraverse(T-lchild, Visit); Visit(T-data)； InOrderTraverse(T-rchild, Visit); / InOrderTraverse 你能写出你能写出后序遍历递归算法了吧后序遍历递归算法了吧?3 后序遍历递归算法后序遍历递归算法 void PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e) /采用二叉链表存贮二叉

37、树，采用二叉链表存贮二叉树， visit( )是访问结点的函数。本算法中是访问结点的函数。本算法中序遍历以为根结点指针的二叉树，对每个数据元素调用函数序遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit( ) if (T) /若二叉树为空，结束返回若二叉树为空，结束返回 / 若二叉树不为空，遍历左子树，遍历右子树，访问根结点若二叉树不为空，遍历左子树，遍历右子树，访问根结点 PostOrderTraverse(T-lchild, Visit); PostOrderTraverse(T-rchild, Visit); Visit(T-data)； /PostOrderTraverse

38、任何一棵二叉树都可以将它的外部轮廓用一条任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。条包线对于理解二叉树的遍历过程很有用。G HD E FB CA四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 采用二叉链表存储结构，采用二叉链表存储结构，Visit是对数据元素操作的应用是对数据元素操作的应用/函数函数.中序遍历二叉树中序遍历二叉树T的非递归算法，对每个数

39、据元素调的非递归算法，对每个数据元素调/用函数用函数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; / InO

40、rderTraverseStatus 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 /上

41、层指针退栈，访问其所指结点，再向右进上层指针退栈，访问其所指结点，再向右进 Pop(S, p); if (!Visit(p-data) return ERROR; p = p-rchild; return OK; / InOrderTraverse中序遍历遍历二叉树的非递归算法示意图C B D F A G EABCDGEFABCNULLSGetToplchild)& (!T-rchild) count+; / 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeaf2、求二叉树的

42、深度、求二叉树的深度(后序遍历后序遍历)算法基本思想算法基本思想: : 从二叉树深度的定义可知，二叉树的二叉树的深度应为其左、右子树深度的最大值加深度应为其左、右子树深度的最大值加1 1。由此，需先分别求得左、右子树的深度，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、求得左、右子树深度的最大值，然后加右子树深度的最大值，然后加 1 1 。 首先分析二叉树的深度二叉树的深度和它的左左、右子右子树深度树深度之间的关系。int Depth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth(

43、 T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;3、复制二叉树、复制二叉树其基本操作为：生成一个结点。其基本操作为：生成一个结点。根元素根元素T左子树左子树右子树右子树根元素根元素NEWT左子树左子树右子树右子树左子树左子树右子树右子树(后序遍历后序遍历)BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if

44、(!(T = (BiTNode*)malloc(sizeof(BiTNode) exit(OVERFLOW); T- data = item; T- lchild = lptr; T- rchild = rptr; return T; 生成一个二叉树的结点生成一个二叉树的结点(其数据域为其数据域为item,左指针域为左指针域为lptr,右指针域为右指针域为rptr)BiTNode *CopyTree(BiTNode *T) if (!T ) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild);/复制左子树 else newlptr

45、= NULL; if (T-rchild ) newrptr = CopyTree(T-rchild);/复制右子树 else newrptr = NULL; newT = GetTreeNode(T-data, newlptr, newrptr); return newT; / CopyTreeABCDEFGHK D C B H K G F E A例如：下列二叉树例如：下列二叉树的复制过程如下：的复制过程如下：newT4 4、建立二叉树的存储、建立二叉树的存储结构结构 为二叉树建立二叉链表为二叉树建立二叉链表 输入：输入：二叉树的先序序列二叉树的先序序列 结果：结果：二叉树的二叉链表二叉树的

46、二叉链表 遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可在利用。是否可在利用遍历，建立遍历，建立二叉链表的所有结点并完成相应结点二叉链表的所有结点并完成相应结点的链接？的链接？基本思想基本思想：输入（输入（在空子树处添加在空子树处添加* *的二叉树的）先序序列（设每的二叉树的）先序序列（设每个元素是个元素是一个字符）按先序遍历的顺序，建立二叉链表的所有结点一个字符）按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点的链接并完成相应结点的链接 D D A A B B C C E E F F T T 先序序列：A B D F

47、 C E（在空子树处添加（在空子树处添加* *的二叉树的）先序序列：的二叉树的）先序序列： A B D A B D * * F F * * * * * *C E 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 BStatus CreateBiTree(BiTree &T) /输入（在空子树处添加*的二叉树的）先序序列（设每个元/素是一个字 符）按先序遍历的顺序，建立二叉链表，并将/该二叉链表根结点指针赋给T scanf (&ch); if (ch= = * )T=NULL; / 若ch= = * 则T

48、=NULL返回 else / 若ch! = * if (! (T=(BiTNode * )malloc(sizeof(BiTNode) exit(OVERFLOW); T-date = ch; / 建立（根）结点 CreateBiTree(T-lchild); /构造左子树 CreateBiTree(T-rchild); /构造右子树 return OK;/CreateBiTree84分析：若二叉树的任意两个结点的值都不相同，则二叉树的前序序列和中序序列能唯一确定一棵二叉树。另外，由前序序列和中序序列的定义可知，前序序列中第一个结点必为根结点，而在中序序列中，根结点刚好是左、右子树的分界点，因

49、此，可按如下方法建立二叉树：由二叉树的先序和中序序列建立二叉树由二叉树的先序和中序序列建立二叉树二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根851.1.用前序序列的第一个结点作为根结点用前序序列的第一个结点作为根结点; ;2.2.在中序序列中查找根结点的位置，并以此为界将中序序在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列列划分为左、右两个序列( (左、右子树左、右子树););3.3.根据左、右子树的中序序列中的结点个数，将前序序列根据左、右子树的中序序列中的结点个数，将前序序列去掉根结点后的序列划分为左、右两个序列，它们分

50、别是左、去掉根结点后的序列划分为左、右两个序列，它们分别是左、右子树的前序序列右子树的前序序列; ;4.4.对左、右子树的前序序列和中序序列递归地实施同样方对左、右子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。法，直到所得左、右子树为空。假设前序序列为假设前序序列为ABDGHCEFIABDGHCEFI，中序序列为中序序列为GDHBAECIFGDHBAECIF， 则得到的二叉树如下页所示则得到的二叉树如下页所示861. 1. A A为根结点为根结点A BDGH CEFI GDHB A ECIF BDGHCEFIA2. 2. B B为左子树的根结点为左子树的根结点B DGHG

51、DH BCEFIDHGBA3. 3. D D为左子树的左子树为左子树的左子树的根结点的根结点 A B G H D C E F I 87 A B G H D C FI E 4. 4. C C为右子树的根结点为右子树的根结点 A B G H D C F I E 5. 5. F F为右子树的右为右子树的右子树的根结点子树的根结点C E FIE C IFa b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列中序序列练习： 已知结点的先序序列和中序序列，求整棵二叉树。先序序列：A B C D E F G中序序列：C B E D A F GA

52、CBEDFGABCDEFGABCFDEG6.3.2线索二叉树线索二叉树 线索二叉树的定义线索二叉树的定义 线索的描述线索的描述 建立线索二叉树建立线索二叉树 线索二叉树上的运算线索二叉树上的运算遍历二叉树的结果是， 求得结点的一个线性序列。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一、一、线索二叉树的定义线索二叉树的定义在这样的线性序列中，很容易求得某个结点在某种遍在这样的线性序列中，很容易求得某个结点在某种遍历下的直接前驱和后继。然而，有时我们希望不进行遍历历下

53、的直接前驱和后继。然而，有时我们希望不进行遍历就能快速找到某个结点在某种遍历下的直接前驱和后继，就能快速找到某个结点在某种遍历下的直接前驱和后继，这样，就应该把每个结点的直接前驱和直接后继记录下来。这样，就应该把每个结点的直接前驱和直接后继记录下来。为了做到这一点，可以在原来的二叉链表结点中，再增加为了做到这一点，可以在原来的二叉链表结点中，再增加两个指针域，一个指向前驱，一个指向后继，但这样做将两个指针域，一个指向前驱，一个指向后继，但这样做将会浪费大量存贮单元，存贮空间的利用率相当低会浪费大量存贮单元，存贮空间的利用率相当低( (一个结一个结点中有点中有4 4个指针，个指针，1 1个指左孩

54、子，个指左孩子，1 1个指右孩子，个指右孩子，1 1个指前驱，个指前驱，1 1个指后继个指后继) )，而原来的左、右孩子域有许多空指针又没有，而原来的左、右孩子域有许多空指针又没有利用起来。为了不浪费存贮空间，我们利用原有的孩子指利用起来。为了不浪费存贮空间，我们利用原有的孩子指针为空时来存放直接前驱和后继，这样的指针称为针为空时来存放直接前驱和后继，这样的指针称为“线线索索”，加线索的过程称为，加线索的过程称为线索化线索化，加了线索的二叉树，称，加了线索的二叉树，称为为线索二叉树线索二叉树，对应的二叉链表称为，对应的二叉链表称为线索二叉链表线索二叉链表。一、一、线索二叉树的定义线索二叉树的定

55、义指向该线性序列中的“前驱”和 “后继” 的指针指针，称作“线索线索”加了线索的二叉树，称作 “线索二叉树线索二叉树”包含 “线索” 的二叉链表，称作 “线索链线索链表表”A B C D E F G H K D C B E 在线索二叉树中，由于有了线索，无需遍历二叉在线索二叉树中，由于有了线索，无需遍历二叉树就可以得到任一结点在某种遍历下的直接前驱和后树就可以得到任一结点在某种遍历下的直接前驱和后继。但是，我们怎样来区分孩子指针域中存放的是左、继。但是，我们怎样来区分孩子指针域中存放的是左、右孩子信息还是直接前驱或直接后继信息呢右孩子信息还是直接前驱或直接后继信息呢? ?为此，在为此，在二叉链

56、表结点中，还必须增加两个标志域二叉链表结点中，还必须增加两个标志域ltagltag、rtagrtag。 ltag和rtag定义如下： 0 lchild域指向结点的左孩子域指向结点的左孩子 ltag= 1 lchild域指向结点在某种遍历下的直接前驱域指向结点在某种遍历下的直接前驱 0 rchild域指向结点的右孩子域指向结点的右孩子 rtag= 1 rchild域指向结点在某种遍历下的直接后继域指向结点在某种遍历下的直接后继 这样，二叉链表中每个结点还是有这样，二叉链表中每个结点还是有5个个域，但其中只有域，但其中只有2个指针，较原来的个指针，较原来的4个指个指针要方便。增加线索后的二叉链表结

57、点结针要方便。增加线索后的二叉链表结点结构可描述如下：构可描述如下： lchild ltag data rtag rchild typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerThr LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;二、线索的描述：1、类型定义：、类型定义： typedef enum Link, Thread PointerThr; / Link=0:指针，Thread=1:线索2线索的画法线索的画法在二叉树或二叉链

58、表中，若左孩子为空，则在二叉树或二叉链表中，若左孩子为空，则画出它的直接前驱，右孩子为空时，则画出它的画出它的直接前驱，右孩子为空时，则画出它的直接后继，左右孩子不为空时，不需画前驱和后直接后继，左右孩子不为空时，不需画前驱和后继。这样就得到了线索二叉树或线索二叉链表。继。这样就得到了线索二叉树或线索二叉链表。 A D C B 0 A 0 1 B 1 0 C 1 root 1 D 1 A D C B NULL (a) 二叉树 (b)先序线索二叉树 (c)先序线索二叉链表 图 先序线索示意图 先序序列为：ABCD A D C B NULL NULL （a）中序二叉树 （b） 中序线索二叉链表 图

59、 中序线索示意图 0 A 0 root 1 D 1 0 C 1 1 B 1 中序序列为：BADC C 0 A 0 1 B 1 0 C 1 1 D 1 root D B A NULL (a)后序线索二叉树 (b)后序线索二叉链表 图 后序线索示意图 后序序列为：BDCAABCDEABCDE A B D C ET先序序列：ABCDE先序线索二叉链表00001111 11ABCDE A B D C ET中序序列：BCAED中序线索二叉链表0000111111ABCDE A B D C ET后序序列：CBEDA后序线索二叉链表0000111111ABCDE 0 A 0 1 B 0 0 D 1 1 C

60、1 1 E 1 T中序序列：BCAED带头结点的中序线索二叉链表 0 1头结点：ltag=0, lchild指向根结点rtag=1, rchild指向遍历序列中最后一个结点遍历序列中第一个结点的lchild域和最后一个结点的rchild域都指向头结点 A B D C ET中序序列：BCAED中序线索二叉链表0000111111 建立线索二叉树，或者说对二叉树线索化，实质上就建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前结点的左、右指针域是否为空，如果为空，将检查当前结点的左、右指针域是否为空

61、，如果为空，将它们改为指向前驱结点或后继结点的线索。为实现这一它们改为指向前驱结点或后继结点的线索。为实现这一过程，设指针过程，设指针pre始终指向刚刚访问过的结点，即若指针始终指向刚刚访问过的结点，即若指针p指向当前结点，则指向当前结点，则pre指向它的前驱，以便增设线索。指向它的前驱，以便增设线索。 此外，在对一棵二叉树加线索时，必须首先申请一个此外，在对一棵二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间二叉树线索化后，还需建立最后一个结点与头结点之间的线索。的

62、线索。 三、建立线索二叉树三、建立线索二叉树void InThreading(BiThrTree p) if (p) / 对以p为根的非空二叉树进行线索化 InThreading(p-lchild); / 左子树线索化 if (!p-lchild) / 建前驱线索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后继线索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驱 InThreading(p-rchild); / 右子树线索化 / if / InThread

63、ingStatus InOrderThreading(BiThrTree &Thrt, BiThrTree T) / 构建中序线索链表 if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode) exit (OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread; Thrt-rchild = Thrt; / 添加头结点 return OK; / InOrderThreading if (!T) Thrt-lchild = Thrt; else Thrt-lchild = T; pre = Thrt; InT

64、hreading(T); pre-rchild = Thrt; / 处理最后一个结点 pre-RTag = Thread; Thrt-rchild = pre; 四、四、 线索二叉树上的运算线索二叉树上的运算1线索二叉树上的查找线索二叉树上的查找 （1）查找指定结点在中序线索二叉树中的的直接后继）查找指定结点在中序线索二叉树中的的直接后继若所找结点右标志若所找结点右标志rtag=1，则右孩子域指向中序后继，则右孩子域指向中序后继，否则，中序后继应为否则，中序后继应为遍历右子树时的第一个访问结点遍历右子树时的第一个访问结点,即右子即右子树中最左下的结点树中最左下的结点（参见下图）。从下图中可知，

65、（参见下图）。从下图中可知，x的后继的后继为为xk 。 X X1 X2 XK P X 0 P 0 x1 0 x2 1 xk 图 求中序后继示意图 （2）查找指定结点在中序线索二叉树中的的直接）查找指定结点在中序线索二叉树中的的直接前驱前驱若所找结点左标志若所找结点左标志ltag=1，则左孩子域指向中序前驱，则左孩子域指向中序前驱，否则，中序前驱应为否则，中序前驱应为遍历左子树时的最后一个访问结点，即遍历左子树时的最后一个访问结点，即左子树中最右下的结点左子树中最右下的结点（参见下图）。从下图中可知，（参见下图）。从下图中可知，x的前的前驱为驱为xk 。 X X1 X2 xk P 0 X P x

66、1 0 x2 0 xk 1 图 求中序前驱示意图 (3) 查找指定点在先序线索二叉树中的直接后继查找指定点在先序线索二叉树中的直接后继先序后继的查找比较方便，若无左孩子，右先序后继的查找比较方便，若无左孩子，右孩子为后继，否则左孩子为后继。孩子为后继，否则左孩子为后继。 (4) 查找指定结点在后序线索二叉树中的直接前查找指定结点在后序线索二叉树中的直接前驱驱后序前驱的查找也比较方便，若左孩子为空，后序前驱的查找也比较方便，若左孩子为空，左链指前驱，否则，若右子树为空，左孩子为前驱，左链指前驱，否则，若右子树为空，左孩子为前驱，否则右孩子为前驱。否则右孩子为前驱。 求后序后继和先序前驱都比较麻烦，在此不再求后序后继和先序前驱都比较麻烦，在此不再作进一步介绍。作进一步介绍。2线索二叉树上的遍历线索二叉树上的遍历 遍历某种次序的线索二叉树，只要从该次序下遍历某种次序的线索二叉树，只要从该次序下的开始结点出发，反复找到结点在该次序下的后继，的开始结点出发，反复找到结点在该次序下的后继，直到后继为空。这对于中序线索和前序线索二叉树直到后继为空。这对于中序线索和前序线索二叉树很方便，但对于后序线索二叉树较麻烦很方便，但对于后序线索二叉树较麻烦(因求后序因求后序后继较麻烦后继较麻烦)。故后序线索对于遍历没有什么意义。故后序线索对于遍历没有什