数据结构第二部分ppt课件

1、第二部分第二部分 树树 树形结构式处理具有层次关系的数据元树形结构式处理具有层次关系的数据元素素 这部分将介绍这部分将介绍 树树 二叉树二叉树 堆堆第五章第五章 树树 树的概念树的概念 二叉树二叉树 表达式树表达式树 哈夫曼树与哈夫曼编哈夫曼树与哈夫曼编码码 树和森林树和森林树的概念树的概念 树的定义树的定义 树的术语树的术语 树的运算树的运算树的定义树的定义树是树是n (n1) n (n1) 个结点的有限集合个结点的有限集合T T，并且满足：，并且满足： (1)(1)有一个被称之为根有一个被称之为根(root)(root)的结点的结点 (2)(2)其余的结点可分为其余的结点可分为m(m0)m

2、(m0)个互不相交的个互不相交的集合集合TlTl，T2T2，TmTm，这些集合本身也是一棵这些集合本身也是一棵树，并称它们为根结点树，并称它们为根结点的子树的子树(Subree)(Subree)。每棵。每棵子树同样有自己的根结子树同样有自己的根结点。点。ADCBFEGJIHLKM树的概念树的概念 树的定义树的定义 树的术语树的术语 树的运算树的运算根结点、叶结点、内部节点根结点、叶结点、内部节点结点的度和树的度结点的度和树的度儿子结点儿子结点父亲结点父亲结点兄弟结点兄弟结点祖先结点祖先结点子孙结点子孙结点结点所处层次结点所处层次树的高度树的高度有序树有序树无序树无序树森林森林 树的术语树的术语

3、ADCBFEGJIHLKM树的概念树的概念 树的定义树的定义 树的术语树的术语 树的运算树的运算树的常用操作树的常用操作 建树建树create()create()：创建一棵空树；：创建一棵空树； 清空清空clear()clear()：删除树中的所有结点；：删除树中的所有结点； 判空判空IsEmpty()IsEmpty()：判别是否为空树；：判别是否为空树； 找根结点找根结点root()root()：找出树的根结点。如果树是空：找出树的根结点。如果树是空树，则返回一个特殊的标记；树，则返回一个特殊的标记； 找父结点找父结点parent(x)parent(x)：找出结点：找出结点x x的父结点；的

4、父结点； 找子结点找子结点child(x,i)child(x,i)：找结点：找结点x x的第的第i i个子结点；个子结点； 剪枝剪枝delete(x,i)delete(x,i)：删除结点：删除结点x x的第的第i i棵子树；棵子树； 构建一棵树构建一棵树MakeTreeMakeTreex,T1, T2, ,Tnx,T1, T2, ,Tn）：）：构建一棵以构建一棵以x x为根结点，以为根结点，以T1, T2, ,TnT1, T2, ,Tn为第为第i i棵子树的树；棵子树的树； 遍历遍历traverse()traverse()：访问树上的每一个结点。：访问树上的每一个结点。 第五章第五章 树树 树

5、的概念树的概念 二叉树二叉树 表达式树表达式树 哈夫曼树与哈夫曼编哈夫曼树与哈夫曼编码码 树和森林树和森林二叉树二叉树 二叉树的概念二叉树的概念 二叉树的性质二叉树的性质 二叉树的基本运算二叉树的基本运算 二叉树的遍历二叉树的遍历 二叉树的实现二叉树的实现 二叉树类二叉树类 二叉树遍历的非递归实现二叉树遍历的非递归实现二叉树的定义二叉树的定义 二叉树二叉树Binary TreeBinary Tree是结点的有限集合，是结点的有限集合，它或者为空，或者由一个根结点及两棵互不它或者为空，或者由一个根结点及两棵互不相交的左、右子树构成，而其左、右子树又相交的左、右子树构成，而其左、右子树又都是二叉树

6、。都是二叉树。 注意：二叉树必须严格区分左右子树。即使只有一棵子注意：二叉树必须严格区分左右子树。即使只有一棵子树，也要说明它是左子树还是右子树。交换一棵二叉树树，也要说明它是左子树还是右子树。交换一棵二叉树的左右子树后得到的是另一棵二叉树。的左右子树后得到的是另一棵二叉树。二叉树的基本形态二叉树的基本形态 (a)空二叉树空二叉树 (b)根和空的根和空的左右子树左右子树 (c)根和左右子树根和左右子树 (d)根和左子树根和左子树 (e)根和右子树根和右子树左左子子树树右右子子树树左左子子树树右右子子树树结点总数为结点总数为3 的所有二叉的所有二叉树的不同形状树的不同形状l 一棵高度为一棵高度为

7、k k并具有并具有2k2k1 1个结点的二叉个结点的二叉树称为满二叉树。树称为满二叉树。l 一棵二叉树中任意一层的结点个数都达一棵二叉树中任意一层的结点个数都达到了最大值到了最大值满二叉树满二叉树DCGEFBAHKIJOLNM满二叉树实例满二叉树实例不是满二叉树不是满二叉树DCGEFBAHIJ完全二叉树完全二叉树在满二叉树的最底层自右至左依次在满二叉树的最底层自右至左依次( (注意：不能跳过注意：不能跳过任何一个结点任何一个结点) )去掉若干个结点得到的二叉树也被称去掉若干个结点得到的二叉树也被称之为完全二叉树。满二叉树一定是完全二叉树，但之为完全二叉树。满二叉树一定是完全二叉树，但完全二叉树

8、不一定是满二叉树。完全二叉树不一定是满二叉树。完全二叉树的特点是：完全二叉树的特点是： （1 1所有的叶结点都出现在最低的两层上。所有的叶结点都出现在最低的两层上。 （2 2对任一结点，如果其右子树的高度为对任一结点，如果其右子树的高度为k k，则其，则其左子树的高度为左子树的高度为k k或或k k1 1。 01234完全二叉树完全二叉树非完全二叉树非完全二叉树DCGEFBAHIJ二叉树二叉树 二叉树的概念二叉树的概念 二叉树的性质二叉树的性质 二叉树的基本运算二叉树的基本运算 二叉树的遍历二叉树的遍历 二叉树的实现二叉树的实现 二叉树类二叉树类 二叉树遍历的非递归实现二叉树遍历的非递归实现二

9、叉树的性质二叉树的性质1 1 一棵非空二叉树的第一棵非空二叉树的第 i i 层上最多有层上最多有2i-12i-1个结点个结点i1i1）。）。BCDEFLA1层：结点个数层：结点个数 21-1=1个个2层：结点个数层：结点个数 22-1=2 个个3层：结点个数层：结点个数 23-1=4 个个证明：当证明：当i=1i=1时，只有一个根结点，时，只有一个根结点，2i-1=20 =1,2i-1=20 =1,命题成立。命题成立。 假定对于所有的假定对于所有的j j，1jk,1jk,命题成立。命题成立。 即第即第j j层上至多有层上至多有2j-12j-1个结点。个结点。 由归纳假设可知，第由归纳假设可知，

10、第j = kj = k层上至多有层上至多有2k-12k-1个结点。个结点。 若要使得第若要使得第k+1k+1层上结点数为最多，那么，第层上结点数为最多，那么，第k k层上层上 的每个结点都必须有二个儿子结点。的每个结点都必须有二个儿子结点。 因而，第因而，第k+1k+1层上结点数最多为为第层上结点数最多为为第k k层上最多结点数层上最多结点数 的二倍，即：的二倍，即：2 22k-12k-12k+1-12k+1-12k2k。 所以，命题成立。所以，命题成立。 二叉树的性质二叉树的性质2 2 一棵高度为一棵高度为k k的二叉树，最多具有的二叉树，最多具有2k2k1 1个结点。个结点。 kiki11

11、122证明：这棵二叉树中的每一层的结点个数必须最多。证明：这棵二叉树中的每一层的结点个数必须最多。 根据性质根据性质1，第，第i层的结点数最多为等于层的结点数最多为等于2i-1， 因此结点个数因此结点个数 N 最多为：最多为： 对于一棵非空二叉树，如果叶子结点数为对于一棵非空二叉树，如果叶子结点数为n0n0，度数为度数为2 2的结点数为的结点数为n2n2，则有，则有: : n0 n0n2n21 1 成立。成立。 二叉树的性质二叉树的性质3 3证明：设证明：设n n为二叉树的结点总数，为二叉树的结点总数，n1n1为二叉树中度数为为二叉树中度数为 1 1的结点数。的结点数。 二叉树中所有结点均小于

12、或等于二叉树中所有结点均小于或等于2 2，所以有：，所以有： n n n0 n0 n1 n1 n2 n2 再看二叉树中的树枝再看二叉树中的树枝( (父结点和儿子结点之间的父结点和儿子结点之间的 线段线段) )总数。总数。 在二叉树中，除根结点外，其余结点都有唯一在二叉树中，除根结点外，其余结点都有唯一 的一个树枝进入本结点。的一个树枝进入本结点。性质性质3证明证明设设B B为二叉树中的树枝数，那么有下式成立：为二叉树中的树枝数，那么有下式成立： B B n n1 1 这些树枝都是由度为这些树枝都是由度为1 1和度为和度为2 2的结点发出的，的结点发出的，一个度为一个度为1 1的结点发出一个树枝

13、，一个度为的结点发出一个树枝，一个度为2 2的结点的结点发出两个树枝，所以有：发出两个树枝，所以有： B B n1n12n2 2n2 因而，因而， n0n0n2n21 1二叉树的性质二叉树的性质4 4具有具有n n个结点的完全二叉树的高度个结点的完全二叉树的高度 k = k = log2nlog2n + + 1 1 证明证明 根据完全二叉树的定义和性质根据完全二叉树的定义和性质2可知，高度为可知，高度为k的的 完全二叉树的第一层到第完全二叉树的第一层到第k-1层具有最多的结点个层具有最多的结点个 数，总数为数，总数为 2k-1- 1个，第个，第k层至少具有一个结点，层至少具有一个结点， 至多有

14、至多有2k-1个结点。因而，个结点。因而， 2k-1 1 n 2k - 1 即即 2k-1 n 2k 对不等式取对数，有对不等式取对数，有 k -1 log2n 1i1，则其父亲结点的编号为，则其父亲结点的编号为i/2i/2 。（2 2如果如果2i n2i n，则编号为，则编号为i i的结点为叶子结点，的结点为叶子结点，没有儿子；否则，其左儿子的编号为没有儿子；否则，其左儿子的编号为2i2i。（3 3如果如果2i + 1 n2i + 1 n，则编号为，则编号为i i的结点无右儿子；的结点无右儿子；否则，其右儿子的编号为否则，其右儿子的编号为2i+12i+1。 BDEFLAPSQRU121110

15、987654321C二叉树二叉树 二叉树的概念二叉树的概念 二叉树的性质二叉树的性质 二叉树的基本运算二叉树的基本运算 二叉树的遍历二叉树的遍历 二叉树的实现二叉树的实现 二叉树类二叉树类 二叉树遍历的非递归实现二叉树遍历的非递归实现二叉树常用操作二叉树常用操作 建树建树create()create()：创建一棵空的二叉树；：创建一棵空的二叉树； 清空清空clear()clear()：删除二叉树中的所有结点；：删除二叉树中的所有结点； 判空判空IsEmpty()IsEmpty()：判别二叉树是否为空树；：判别二叉树是否为空树； 找根结点找根结点root()root()：找出二叉树的根结点。：找

16、出二叉树的根结点。 找父结点找父结点parent(x)parent(x)：找出结点：找出结点x x的父结点；的父结点； 找左孩子找左孩子lchild(x)lchild(x)：找结点：找结点x x的左孩子结点；的左孩子结点； 找右孩子找右孩子rchild(x)rchild(x)：找结点：找结点x x的右孩子结点；的右孩子结点； 删除左子树删除左子树delLeft(x)delLeft(x)：删除结点：删除结点x x的左子树；的左子树； 删除右子树删除右子树delRight(x)delRight(x)：删除结点：删除结点x x的右子树；的右子树； 构建一棵树构建一棵树MakeTreeMakeTree

17、x,TL, TRx,TL, TR）：构建一棵以）：构建一棵以x x为根结点，以为根结点，以TLTL， TRTR为左右子树的二叉树；为左右子树的二叉树； 遍历遍历traverse()traverse()：访问二叉树上的每一个结点。：访问二叉树上的每一个结点。二叉树二叉树 二叉树的概念二叉树的概念 二叉树的性质二叉树的性质 二叉树的基本运算二叉树的基本运算 二叉树的遍历二叉树的遍历 二叉树的实现二叉树的实现 二叉树类二叉树类 二叉树遍历的非递归实现二叉树遍历的非递归实现二叉树的遍历二叉树的遍历 二叉树的遍历讨论的是如何访问到树上的二叉树的遍历讨论的是如何访问到树上的每一个结点每一个结点 在线性表中

18、，我们可以沿着后继链访问到在线性表中，我们可以沿着后继链访问到所有结点。而二叉树是有分叉的，因此在所有结点。而二叉树是有分叉的，因此在分叉处必须确定下一个要访问的节点：是分叉处必须确定下一个要访问的节点：是根结点、左结点还是右结点根结点、左结点还是右结点 根据不同的选择，有三种遍历的方法：前根据不同的选择，有三种遍历的方法：前序、中序和后序序、中序和后序前序遍历前序遍历 如果二叉树为空，则操作为空如果二叉树为空，则操作为空 否则否则 访问根结点访问根结点 前序遍历左子树前序遍历左子树 前序遍历右子树前序遍历右子树中序遍历中序遍历 如果二叉树为空，则操作为空如果二叉树为空，则操作为空 否则否则

19、中序遍历左子树中序遍历左子树 访问根结点访问根结点 中序遍历右子树中序遍历右子树后序遍历后序遍历 如果二叉树为空，则操作为空如果二叉树为空，则操作为空 否则否则 后序遍历左子树后序遍历左子树 后序遍历右子树后序遍历右子树 访问根结点访问根结点前序：前序：A、L、B、E、 C、D、W、X中序：中序：B、L、E、A、 C、W、X、D后序：后序：B、E、L、X、 W、D、C、ABCDELAXW前序前序 中序中序 唯一确定一唯一确定一棵二叉树棵二叉树 前序前序: A、B、D、E、F、C 中序中序: D、B、E、F、A、C 前序前序: B、D、E、F 中序中序: D、B、E、F 前序前序: E、F 中序

20、中序: E、FD、B、E、FA CACBABCD E、FEFABCD 同理，由二叉树的后序序列和中序序列同样可同理，由二叉树的后序序列和中序序列同样可以唯一地确定一棵二叉树以唯一地确定一棵二叉树 但是，已知二叉树的前序遍历序列和后序遍历但是，已知二叉树的前序遍历序列和后序遍历序列却无法确定一棵二叉树。比如：已知一棵序列却无法确定一棵二叉树。比如：已知一棵二叉树的前序遍历序列为二叉树的前序遍历序列为A A、B B，后序遍历序列，后序遍历序列为为B B、A A，我们虽然可以很容易地得知结点，我们虽然可以很容易地得知结点A A为为根结点，但是无法确定结点根结点，但是无法确定结点B B是结点是结点A

21、A的左儿子的左儿子还是右儿子，因为还是右儿子，因为B B无论是结点无论是结点A A的右儿子还是的右儿子还是左儿子都是符合已知条件的。左儿子都是符合已知条件的。 二叉树二叉树 二叉树的概念二叉树的概念 二叉树的性质二叉树的性质 二叉树的基本运算二叉树的基本运算 二叉树的遍历二叉树的遍历 二叉树的实现二叉树的实现 二叉树类二叉树类 二叉树遍历的非递归实现二叉树遍历的非递归实现二叉树的实现二叉树的实现 顺序实现顺序实现 链接实现链接实现完全二叉树的顺序存储完全二叉树的顺序存储 BCDEFLAPSQRU212111098765431根据编号性质，根据编号性质，可以省略左右可以省略左右孩子字段孩子字段0

22、1A2L3B4B5E6F7D8P9Q10R11S12U普通二叉树的顺序存储普通二叉树的顺序存储 DBAHI将普通的树修将普通的树修补成完全二叉补成完全二叉树树01A2B3 4D5 6 7 8H9I右单支树的实例右单支树的实例 CGA01A23C C45 6 7G G 顺序实现的特点顺序实现的特点 存储空间的浪费。存储空间的浪费。 一般只用于一些特殊的场合，如静态的一般只用于一些特殊的场合，如静态的并且结点个数已知的完全二叉树或接近并且结点个数已知的完全二叉树或接近完全二叉树的二叉树。完全二叉树的二叉树。 二叉树的实现二叉树的实现 顺序实现顺序实现 链接实现链接实现链接存储结构链接存储结构ABC

23、DEFGHIL标准形式：（二叉链表）标准形式：（二叉链表）广义标准形式：（三叉链表）广义标准形式：（三叉链表）LEFTDATARIGHTLEFTDATARIGHT PARENT标准形式的实例标准形式的实例 AL/C/ B/E/D/W/XrootALCXEBWD广义标准形式的实例广义标准形式的实例 ALCXEBWDArootLCE B DW X 二叉树基本运算的实现二叉树基本运算的实现 由于二叉树是一个递归的结构，因此二叉树中的许由于二叉树是一个递归的结构，因此二叉树中的许多运算的实现都是基于递归函数。多运算的实现都是基于递归函数。 create()create()：将指向根结点的指针设为空指针

24、就可以：将指向根结点的指针设为空指针就可以了，即了，即root = NULLroot = NULL。 isEmpty()isEmpty()：只需要判别：只需要判别rootroot即可。如果即可。如果rootroot等于等于空指针，返回空指针，返回truetrue，否则，返回，否则，返回falsefalse。 root()root()：返回：返回rootroot指向的结点的数据部分。如果二指向的结点的数据部分。如果二叉树是空树，则返回一个特殊的标记。叉树是空树，则返回一个特殊的标记。clear() 从递归的观点看，一棵二叉树由三部分组从递归的观点看，一棵二叉树由三部分组成：根结点、左子树、右子树

25、。删除一棵成：根结点、左子树、右子树。删除一棵二叉树就是删除这三个部分。二叉树就是删除这三个部分。 根结点的删除很简单，只要回收根结点的根结点的删除很简单，只要回收根结点的空间，把指向根结点的指针设为空指针。空间，把指向根结点的指针设为空指针。 如何删除左子树和右子树呢？记住左子树如何删除左子树和右子树呢？记住左子树也是一棵二叉树，右子树也是一棵二叉树，也是一棵二叉树，右子树也是一棵二叉树，左右子树的删除和整棵树的删除过程是一左右子树的删除和整棵树的删除过程是一样的。样的。 If （左子树非空）（左子树非空） 递归删除左子树；递归删除左子树；If （右子树非空）（右子树非空） 递归删除右子树；

26、递归删除右子树；delete root指向的结点；指向的结点；root = NULL； parent(x)parent(x)：在二叉链表的实现中一般不实：在二叉链表的实现中一般不实现这个操作现这个操作 lchild(x)lchild(x)：返回结点：返回结点x x的的leftleft值值 rchild(x)rchild(x)：返回结点：返回结点x x的的rightright值值 delLeft(x)delLeft(x)：对左子树调用：对左子树调用clearclear函数删除函数删除左子树，然后将结点左子树，然后将结点x x的的leftleft置为置为NULLNULL。 delRight(x)d

27、elRight(x)：对右子树调用：对右子树调用clearclear函数删除函数删除右子树，然后将结点右子树，然后将结点x x的的rightright置为置为NULLNULL。 makeTreemakeTreex,TL, TRx,TL, TR）：为）：为x x申请一个结点，申请一个结点，让它的让它的leftleft指向指向TLTL的根结点，的根结点，rightright指向指向TRTR的根结点。的根结点。 二叉树的遍历二叉树的遍历 前序：前序：访问根结点；访问根结点；If If （左子树非空）（左子树非空） 前序遍历左子树；前序遍历左子树；If If （右子树非空前序遍历右子树；（右子树非空前

28、序遍历右子树；其他两种遍历只要调整一下次序即可。其他两种遍历只要调整一下次序即可。二叉树二叉树 二叉树的概念二叉树的概念 二叉树的性质二叉树的性质 二叉树的基本运算二叉树的基本运算 二叉树的遍历二叉树的遍历 二叉树的实现二叉树的实现 二叉树类二叉树类 二叉树遍历的非递归实现二叉树遍历的非递归实现二叉树类二叉树类 由于二叉树的顺序实现仅用于一些特殊由于二叉树的顺序实现仅用于一些特殊的场合。大多数情况下，二叉树都是用的场合。大多数情况下，二叉树都是用二叉链表实现，所以仅介绍用二叉链表二叉链表实现，所以仅介绍用二叉链表实现的二叉树类。实现的二叉树类。二叉树类的设计二叉树类的设计 标准的链接存储由两个

29、类组成：结点类标准的链接存储由两个类组成：结点类和树类。和树类。 和线性表的实现类似，这个结点类是树和线性表的实现类似，这个结点类是树类专用的，因此可作为树类的私有内嵌类专用的，因此可作为树类的私有内嵌类。类。结点类结点类Node的设计的设计 存储和处理树上每一个结点的类。存储和处理树上每一个结点的类。 数据成员包括：结点的数据及左右孩子的数据成员包括：结点的数据及左右孩子的指针。指针。 结点的操作包括：结点的操作包括： 构造和析构构造和析构二叉树类的设计二叉树类的设计 树的存储：存储指向根结点的指针树的存储：存储指向根结点的指针 树的操作：树的操作： 树的标准操作树的标准操作 增加了一个建树

30、的函数增加了一个建树的函数递归函数的设计递归函数的设计 对于二叉树类的用户来说，他并不需要知道这对于二叉树类的用户来说，他并不需要知道这些操作时用递归函数实现的。些操作时用递归函数实现的。 对用户来说，调用这些函数并不需要参数对用户来说，调用这些函数并不需要参数 但递归函数必须有一个控制递归终止的参数但递归函数必须有一个控制递归终止的参数 设计时，我们将用户需要的函数原型作为公有设计时，我们将用户需要的函数原型作为公有的成员函数。每个公有成员函数对应一个私有的成员函数。每个公有成员函数对应一个私有的、带递归参数的成员函数。公有函数调用私的、带递归参数的成员函数。公有函数调用私有函数完成相应的功

31、能。有函数完成相应的功能。二叉树类的定义二叉树类的定义 template class BinaryTree private: struct Node Node *left , *right ; / 结点的左、右儿子的地址结点的左、右儿子的地址 Type data; / 结点的数据信息结点的数据信息 Node() : left(NULL), right(NULL) Node(Type item, Node *L = NULL, Node * R =NULL ): data(item), left(L), right(R) Node() ; Node *root; / 二叉树的根结点。二叉树的根结

32、点。 public: BinaryTree() : root( NULL) / 构造空二叉树构造空二叉树BinaryTree(const Type & value ) root = new Node(value); BinaryTree(Node *p) root = p; BinaryTree() clear(); Type getRoot() const return root-data;Type getLeft() const return root-left-data;Type getRight() const return root-right-data;void makeT

33、ree(const Type &x, BinaryTree &lt, BinaryTree &rt) root = new Node( x, lt.root, rt.root); lt.root = NULL; rt.root = NULL; void delLeft() BinaryTree tmp = root-left; root-left = NULL； tmp.clear(); void delRight() BinaryTree tmp = root-right; root-right = NULL; tmp.clear(); bool isEmpty ()

34、 const return root = NULL; void clear() if (root != NULL) clear(root); root = NULL; int size() const return size(root); int height() const return height(root); void preOrder() const； void postOrder() const； void midOrder() const； void createTree(Type flag);private: void clear( Node *t ) ； int height

35、( Node *t ) const； int size( Node *t ) const； void preOrder( Node *t ) const； void postOrder( Node *t ) const； void midOrder( Node *t ) const； ; 求规模操作的实现求规模操作的实现 用递归的观点来看，二叉树是由根结点和左用递归的观点来看，二叉树是由根结点和左右子树构成。因而，树的规模应该为：右子树构成。因而，树的规模应该为： 左子树的规模左子树的规模 + + 右子树的规模右子树的规模 + 1+ 1根）根）size () int size() const

36、return size(root); int size(Node *t) const if (t = NULL) return 0; return 1 + size(t-left) + size(t-right); 求高度操作的实现求高度操作的实现 用递归的观点来看，二叉树是由根结点用递归的观点来看，二叉树是由根结点和左右子树构成。因而，树的高度应该和左右子树构成。因而，树的高度应该为：为：1 1maxmax左子树高度，右子树高度）左子树高度，右子树高度）height()int height() const return height(root); int height(Node *t) co

37、nst if (t = NULL) return 0; else int lt = height(t-left), rt = height(t-right); return 1 + ( (lt rt) ? lt : rt); 三种遍历的实现三种遍历的实现 树的遍历本身就是用递归形式描述的，树的遍历本身就是用递归形式描述的，因此用递归函数实现是很自然的因此用递归函数实现是很自然的preOrder()void preOrder() const if (root != NULL) cout n前序遍历：前序遍历：; preOrder(root); void preOrder(Node *t) con

38、st if (t != NULL) cout data left); preOrder(t-right); midOrder()void midOrder() const if (root != NULL) cout left); cout data right); postOrder() void postOrder() const if (root != NULL) cout left); postOrder(t-right); cout data left != NULL) clear(t-left); if (t-right != NULL) clear(t-right); delet

39、e t; 创建一棵树创建一棵树 创建过程：创建过程： 先输入根结点的值，创建根节点先输入根结点的值，创建根节点 对已添加到树上的每个结点，依次输入它的对已添加到树上的每个结点，依次输入它的两个儿子的值。如果没有儿子，则输入一个两个儿子的值。如果没有儿子，则输入一个特定值特定值 实现工具：实现工具： 使用一个队列，将新加入到树中的结点放入使用一个队列，将新加入到树中的结点放入队列队列 依次出队。对每个出队的元素输入它的儿子依次出队。对每个出队的元素输入它的儿子BCDEFLAPSQRU212111098765431队列的变化队列的变化ACLEBCDFEBPDFEQQPDFSRRQPDUSSRQPU

40、USRQ USR US U createTreetemplate void BinaryTree:createTree(Type flag) linkQueue que; Node *tmp; Type x, ldata, rdata; /创建树，输入创建树，输入flag表示空表示空 cout x; root = new Node(x); que.enQueue(root); while (!que.isEmpty() tmp = que.deQueue();cout n输入输入 data 的两个儿子的两个儿子( flag ldata rdata;if (ldata != flag) que.

41、enQueue(tmp-left = new Node(ldata);if (rdata != flag) que.enQueue(tmp-right = new Node(rdata);cout create completed!n; 二叉树类的应用二叉树类的应用 创建一棵由整型值组成的二叉树创建一棵由整型值组成的二叉树 求高度求高度 求规模求规模 按前序、中序和后序遍历按前序、中序和后序遍历 归并两棵树归并两棵树int main() BinaryTree tree, tree1(M), tree2; tree.createTree(); cout 高度为：高度为： tree.height(

42、) endl; cout 规模为：规模为： tree.size() endl; tree.PreOrder(); tree.MidOrder(); tree.PostOrder(); tree2.makeTree(Y, tree, tree1); cout endl; cout 高度为：高度为： tree2.height() endl; cout 规模为：规模为： tree2.size() endl; tree2.PreOrder(); tree2.MidOrder(); tree2.PostOrder(); return 0; BCDELAXW执行实例执行实例输入根结点：输入根结点：A输入输

43、入A的两个儿子的两个儿子(表示空结点表示空结点)：LC输入输入L的两个儿子的两个儿子(表示空结点表示空结点)：BE输入输入C的两个儿子的两个儿子(表示空结点表示空结点)：D输入输入B的两个儿子的两个儿子(表示空结点表示空结点)：输入输入E的两个儿子的两个儿子(表示空结点表示空结点)：输入输入D的两个儿子的两个儿子(表示空结点表示空结点)：W输入输入W的两个儿子的两个儿子(表示空结点表示空结点)：X输入输入X的两个儿子的两个儿子(表示空结点表示空结点)： 高度为：高度为：5规模为：规模为：8前序遍历：前序遍历：A L B E C D W X中序遍历：中序遍历：B L E A C W X D后序遍

44、历：后序遍历：B E L X W D C A高度为：高度为：6规模为：规模为：10前序遍历：前序遍历：Y A L B E C D W X M中序遍历：中序遍历：B L E A C W X D Y M后序遍历：后序遍历：B E L X W D C A M Y BCDELAXWMY二叉树二叉树 二叉树的概念二叉树的概念 二叉树的性质二叉树的性质 二叉树的基本运算二叉树的基本运算 二叉树的遍历二叉树的遍历 二叉树的实现二叉树的实现 二叉树类二叉树类 二叉树遍历的非递归实现二叉树遍历的非递归实现二叉树遍历的非递归实现二叉树遍历的非递归实现 递归是程序设计中强有力的工具。递归是程序设计中强有力的工具。

45、递归程序结构清晰、明了、美观，递归程序结构清晰、明了、美观， 递归程序的弱点：它的时间、空间的效率递归程序的弱点：它的时间、空间的效率比较低。比较低。 所以在实际使用中，我们常常希望使用它所以在实际使用中，我们常常希望使用它的非递归版本的非递归版本 二叉树的遍历也是如此。尽管二叉树遍历二叉树的遍历也是如此。尽管二叉树遍历的递归函数非常简洁，但有时我们还是希的递归函数非常简洁，但有时我们还是希望使用速度更快的非递归函数。望使用速度更快的非递归函数。二叉树遍历的非递归实现二叉树遍历的非递归实现 前序遍历前序遍历 中序遍历中序遍历 后序遍历后序遍历前序遍历的非递归实现前序遍历的非递归实现 前序遍历第

46、一个被访问的结点是根结点，然后前序遍历第一个被访问的结点是根结点，然后访问左子树，最后访问右子树。访问左子树，最后访问右子树。 可以设置一个栈，保存将要访问的树的树根。可以设置一个栈，保存将要访问的树的树根。 开始时，把二叉树的根结点存入栈中。然后重开始时，把二叉树的根结点存入栈中。然后重复以下过程，直到栈为空：复以下过程，直到栈为空： 从栈中取出一个结点，输出根结点的值；从栈中取出一个结点，输出根结点的值； 然后把右子树，左子树放入栈中然后把右子树，左子树放入栈中前序遍历的过程前序遍历的过程BCDELAXWA输出：ALBECDWXLCBECECCDWXtemplate void Binary

47、Tree:preOrder() const linkStack s; Node *current; cout 前序遍历前序遍历: ; s.push( root ); while ( !s.isEmpty() ) current = s.pop(); cout data; if ( current-right != NULL ) s.push( current-right ); if ( current -left != NULL ) s.push( current-left ); 二叉树遍历的非递归实现二叉树遍历的非递归实现 前序遍历前序遍历 中序遍历中序遍历 后序遍历后序遍历中序遍历的非递归

48、实现中序遍历的非递归实现 采用一个栈存放要遍历的树的树根采用一个栈存放要遍历的树的树根 中序遍历中，先要遍历左子树，接下去才能访中序遍历中，先要遍历左子树，接下去才能访问根结点，因而，当根结点出栈时，我们不能问根结点，因而，当根结点出栈时，我们不能访问它，而要访问它的左子树，此时要把树根访问它，而要访问它的左子树，此时要把树根结点暂存一下。结点暂存一下。 存哪里？由于左子树访问完后还要访问根结点，存哪里？由于左子树访问完后还要访问根结点，因此仍可以把它存在栈中，接着左子树也进栈。因此仍可以把它存在栈中，接着左子树也进栈。此时执行出栈操作，出栈的是左子树。左子树此时执行出栈操作，出栈的是左子树。

49、左子树问结束后，再次出栈的是根结点，此时根结点问结束后，再次出栈的是根结点，此时根结点可被访问。根结点访问后，访问右子树，则将可被访问。根结点访问后，访问右子树，则将右子树进栈。右子树进栈。栈元素的设计栈元素的设计 在中序遍历中根结点要进栈两次。在中序遍历中根结点要进栈两次。 当要遍历一棵树时，将根结点进栈。当要遍历一棵树时，将根结点进栈。 根结点第一次出栈时，它不能被访问，必须重根结点第一次出栈时，它不能被访问，必须重新进栈，并将左子树也进栈，表示接下去要访新进栈，并将左子树也进栈，表示接下去要访问的是左子树。问的是左子树。 根结点第二次出栈时，才能被访问，并将右子根结点第二次出栈时，才能被

50、访问，并将右子树进栈，表示右子树可以访问了。树进栈，表示右子树可以访问了。 在中序遍历时不仅要记住需要访问哪一棵树，在中序遍历时不仅要记住需要访问哪一棵树，而且还必须记住根结点是在第几次进栈。而且还必须记住根结点是在第几次进栈。中序遍历的过程中序遍历的过程BCDELAXW0A01LA011BLA111BLA11LA输出：输出：01EABL11EAE1AA0C1CC0D01WD11WDW01XD11XDX1DDStNode类的定义类的定义 struct StNode Node *node; int TimesPop; StNode ( Node *N = NULL ):node(N), Time

51、sPop(0) ; 中序遍历的非递归实现中序遍历的非递归实现 template void BinaryTree:midOrder() const linkStack s; StNode current(root); cout 中序遍历中序遍历: ; s.push(current); while (!s.isEmpty() current = s.pop(); if ( +current.TimesPop = 2 ) cout data; if ( current.node-right != NULL ) s.push(StNode(current.node-right ); else s.pu

52、sh( current ); if ( current.node-left != NULL ) s.push(StNode(current.node-left) ); 二叉树遍历的非递归实现二叉树遍历的非递归实现 前序遍历前序遍历 中序遍历中序遍历 后序遍历后序遍历后序遍历的非递归实现后序遍历的非递归实现 将中序遍历的非递归实现的思想进一步延伸，可将中序遍历的非递归实现的思想进一步延伸，可以得到后序遍历的非递归实现。以得到后序遍历的非递归实现。 当以后序遍历一棵二叉树时，先将树根进栈，表当以后序遍历一棵二叉树时，先将树根进栈，表示要遍历这棵树。示要遍历这棵树。 根结点第一次出栈时，根结点不能访

53、问，应该访根结点第一次出栈时，根结点不能访问，应该访问左子树。于是，根结点重新入栈，并将左子树问左子树。于是，根结点重新入栈，并将左子树也入栈。也入栈。 根结点第二次出栈时，根结点还是不能访问，要根结点第二次出栈时，根结点还是不能访问，要先访问右子树。于是，根结点再次入栈，右子树先访问右子树。于是，根结点再次入栈，右子树也入栈。也入栈。 当根结点第三次出栈时，表示右子树遍历结束，当根结点第三次出栈时，表示右子树遍历结束，此时，根结点才能被访问。此时，根结点才能被访问。 后序遍历的过程后序遍历的过程BCDELAXW0A01LA011BLA111BLA211BLA输出：输出：021ELABE121

54、ELAL221ELA21LA02CA12CABCDELAXW022DCA0122WDCA02122XWDCA12122XWDCA22122XWDCA2122WDCA222DCA22CA2A输出：输出：BLEXWDCA后序遍历的非递归实现后序遍历的非递归实现template void BinaryTree:postOrder() const linkStack s;StNode current(root); cout 后序遍历后序遍历: ;s.push(current); while (!s.isEmpty() current = s.pop(); if ( +current.TimesPop

55、= 3 ) cout data; continue; s.push( current ); if ( current.TimesPop = 1 ) if ( current.node-left != NULL ) s.push(StNode( current.node-left) ); else if ( current.node -right != NULL ) s.push(StNode( current.node-right ) ); 第五章第五章 树树 树的概念树的概念 二叉树二叉树 表达式树表达式树 哈夫曼树与哈夫曼编哈夫曼树与哈夫曼编码码 树和森林树和森林表达式树表达式树 算术表达

56、式可以表示为一棵二叉树，如算术表达式可以表示为一棵二叉树，如: : (4-2) (4-2)* *(10+(4+6)/2)+2(10+(4+6)/2)+2 对这棵树后序遍历可对这棵树后序遍历可 得到结果得到结果 设计一个类，设计一个类， 利用表达式树计算由利用表达式树计算由 四则运算组成的表达式四则运算组成的表达式+*+/210+64-422树的构建过程3*4+5*7*9+8 构建左节点构建左节点33*4+5*7*9+8 构建根节点构建根节点*3*4+5*7*9+8 构建右节点构建右节点43*4+5*7*9+8 构建根节点构建根节点+，原树作为左子树，原树作为左子树+3*45*7*9+8 构建右

57、节点构建右节点5+3*45*7*9+8 下移到右节点，构建根节点下移到右节点，构建根节点*，原来的右节点作为它的左节点，原来的右节点作为它的左节点+3*45+3*45*7*9+8 构建右节点构建右节点7+3*45*7*9+8 创建根创建根*，原树作为左子树，原树作为左子树+3*45*7*+8 上移到根。创建根上移到根。创建根+，原树作为左子树，原树作为左子树8 8作为左节点作为左节点9+8 9作为右子树作为右子树8+3*45*7*9+3*45*7*9+3*45*7*9构建过程总结构建过程总结 顺序扫描中缀表达式顺序扫描中缀表达式 当扫描到的是运算数：先检查当前的表达式当扫描到的是运算数：先检查

58、当前的表达式树是否存在。如果不存在，则表示扫描到的树是否存在。如果不存在，则表示扫描到的是第一个运算数，将它作为树根。如果树存是第一个运算数，将它作为树根。如果树存在，则将此运算数作为前一运算符的右孩子。在，则将此运算数作为前一运算符的右孩子。 如果扫描到的是如果扫描到的是+ +或或- -：将它作为根结点，原：将它作为根结点，原来的树作为它的左子树。来的树作为它的左子树。构建过程总结构建过程总结 续续 如果扫描到的是如果扫描到的是* *或或/ /：则与根结点比较。如：则与根结点比较。如果根结点也是果根结点也是* *或或/ /，则根结点应该先执行，则根结点应该先执行，于是将当前运算符作为根结点，

59、原来的树作于是将当前运算符作为根结点，原来的树作为左子树。如果根结点是为左子树。如果根结点是+ +或或- -，则当前运算，则当前运算符应该先运算，于是将它作为右子树的根，符应该先运算，于是将它作为右子树的根，原来的右子树作为它的左子树。原来的右子树作为它的左子树。 在遇到运算数时，如何知道它前面的运算符在遇到运算数时，如何知道它前面的运算符是谁？这只需要判别根结点有没有右孩子。是谁？这只需要判别根结点有没有右孩子。如果没有右孩子，则运算数是根结点的右运如果没有右孩子，则运算数是根结点的右运算数，否则就是根结点右孩子的右运算数。算数，否则就是根结点右孩子的右运算数。构建过程括号的处理）构建过程括

60、号的处理）(4+5)*(8+9)+10 遇到括号，将括号内的子表达式构建一棵子树遇到括号，将括号内的子表达式构建一棵子树 作为整个表达式的一个运算数作为整个表达式的一个运算数4+5*(8+9)+10 *作为根节点，括号内的子树作为左子树作为根节点，括号内的子树作为左子树4+5*(8+9)+10括号内的子表达式构建一棵子括号内的子表达式构建一棵子树作为整棵树的右子树树作为整棵树的右子树4+5*8+9+10 +作为根节点，原树作为左子作为根节点，原树作为左子树，树，10作为右子树作为右子树4+5*8+9+10表达式树类的设计表达式树类的设计 数据成员：指向树根节点的指针数据成员：指向树根节点的指针 公有成员函数：公有成员函数： 构造函数：调用构造函数：调用createcreate从表