课件第5和二叉树

1、树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现二叉树遍历的非递归算法 树、森林与二叉树的转换哈夫曼树和哈夫曼编码第 5 章 树和二叉树本章的主要内容是树的定义树：n（n0）个结点的有限集合。当n0时，称为空树；任意一棵非空树满足以下条件： 有且仅有一个特定的称为根的结点； 当n1时，除根结点之外的其余结点被分成m（m0）个互不相交的有限集合T1,T2, ,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。5.1 树的逻辑结构树的定义是采用递归方法(a) 一棵树结构 (b)一个非树结构 (c)一个非树结构 5.1 树的逻辑结构树的定义ACBGFEDHIACBGFDACBGFD

2、E树的应用举例文件结构5.1 树的逻辑结构My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic树的基本术语 结点的度：结点所拥有的子树的个数。 树的度：树中各结点度的最大值。5.1 树的逻辑结构CGBDEFKLHMIJA5.1 树的逻辑结构 叶子结点：度为0的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点。CGBDEFKLHMIJA树的基本术语 孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点； 兄弟：具有同一个双亲的孩子结点互称为兄弟。 5.1 树的逻辑结构CGBDEFKLHMI

3、JA树的基本术语 路径：如果树的结点序列n1, n2, , nk有如下关系：结点ni是ni+1的双亲（1=ik），则把n1, n2, , nk称为一条由n1至nk的路径； 路径上经过的边的个数称为路径长度。 CGBDEFKLHMIJA5.1 树的逻辑结构树的基本术语祖先、子孙：在树中，如果有一条路径从结点x到结点y，则x称为y的祖先，而y称为x的子孙。5.1 树的逻辑结构CGBDEFKLHMIJA树的基本术语 结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。 树的深度：树中所有结点的最大层数，也称高度。1层2层4层3层高度4CGBDEFKLHMIJC

4、5.1 树的逻辑结构树的基本术语CBDEFKLHJA71234568910层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。5.1 树的逻辑结构树的基本术语有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。数据结构中讨论的一般都是有序树 5.1 树的逻辑结构树的基本术语ACBGFEDACBGFEDCBDEFKLHJ森林：m (m0)棵互不相交的树的集合。 5.1 树的逻辑结构树的基本术语A树结构和线性结构的比较线性结构树结构第一个数据元素根结点（只有一个）无前驱无双亲最后一个数据元素叶子结点(可以有多个)无

5、后继无孩子其它数据元素其它结点一个前驱,一个后继一个双亲,多个孩子一对一 一对多5.1 树的逻辑结构树的抽象数据类型定义ADT TreeData 树是由一个根结点和若干棵子树构成， 树中结点具有相同数据类型及层次关系Operation5.1 树的逻辑结构树的应用很广泛，在不同的实际应用中，树的基本操作不尽相同。下面给出一个树的抽象数据类型定义的例子，简单起见，基本操作只包含树的遍历，针对具体应用，需要重新定义其基本操作。InitTree 前置条件：树不存在 输入：无 功能：初始化一棵树 输出：无 后置条件：构造一个空树DestroyTree 前置条件：树已存在 输入：无 功能：销毁一棵树 输出

6、：无 后置条件：释放该树占用的存储空间 树的抽象数据类型定义5.1 树的逻辑结构 PreOrder 前置条件：树已存在 输入：无 功能：前序遍历树 输出：树的前序遍历序列 后置条件：树保持不变 PostOrder 前置条件：树已存在 输入：无 功能：后序遍历树 输出：树的后序遍历序列 后置条件：树保持不变endADT树的抽象数据类型定义5.1 树的逻辑结构树的遍历操作 树的遍历：从根结点出发，按照某种次序访问树中所有结点，使得每个结点被访问一次且仅被访问一次。 如何理解访问?抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。如何理解次序?树通常有前序（根）遍历、后序（根）遍历和层

7、序（次）遍历三种方式。5.1 树的逻辑结构树结构（非线性结构）线性结构。遍历的实质?前序遍历 树的前序遍历操作定义为：若树为空，则空操作返回；否则 访问根结点； 按照从左到右的顺序前序遍历根结点的每一棵子树。 5.1 树的逻辑结构前序遍历序列：A B D E H I F C GACBGFEDHI后序遍历 树的后序遍历操作定义为：若树为空，则空操作返回；否则 按照从左到右的顺序后序遍历根结点的每一棵子树； 访问根结点。 5.1 树的逻辑结构后序遍历序列：D H I E F B G C AACBGFEDHI层序遍历 树的层序遍历操作定义为：从树的第一层（即根结点）开始，自上而下逐层遍历，在同一层中

8、，按从左到右的顺序对结点逐个访问。 5.1 树的逻辑结构层序遍历序列：A B C D E F G H IACBGFEDHI5.2 树的存储结构实现树的存储结构，关键是什么?什么是存储结构?树中结点之间的逻辑关系是什么?思考问题的出发点：如何表示结点的双亲和孩子如何表示树中结点之间的逻辑关系。数据元素以及数据元素之间的逻辑关系在存储器中的表示。双亲表示法基本思想：用一维数组来存储树的各个结点（一般按层序存储），数组中的一个元素对应树中的一个结点，包括结点的数据信息以及该结点的双亲在数组中的下标。 5.2 树的存储结构 data parentdata：存储树中结点的数据信息parent：存储该结点

9、的双亲在数组中的下标template struct PNode DataType data; /数据域 int parent; /指针域，双亲在数组中的下标 ; data parent5.2 树的存储结构树的双亲表示法实质上是一个静态链表。双亲表示法下标 data parent012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 5.2 树的存储结构如何查找双亲结点？时间性能？双亲表示法ACBHFEDGI5.2 树的存储结构双亲表示法ACBHFEDGI如何查找孩子结点？时间性能？下标 data parentfirstchild 1 3 6 -1 8 -1

10、-1-1-1012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 下标 data parent rightsib-1 2-1 4 5 -17-1-15.2 树的存储结构双亲表示法012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 ACBHFEDGI如何查找兄弟结点？时间性能？下标 data parent rightsib-1 2-1 4 5 -17-1-15.2 树的存储结构双亲表示法012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 ACBHFEDGI如何查找所有孩子结

11、点？时间性能？firstchild 1 3 6 -1 8 -1-1-1-1链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。 如何表示孩子？5.2 树的存储结构孩子链表表示法方案一：指针域的个数等于树的度data child1 child2 childd其中：data：数据域，存放该结点的数据信息； child1childd：指针域，指向该结点的孩子。 5.2 树的存储结构缺点：浪费空间ACBHFEDGIABCDEFGHI链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。 如何表示孩子？5.2 树的存储结构孩子链表表示法方案二： 指针

12、域的个数等于该结点的度 data degree child1 child2 childd其中：data：数据域，存放该结点的数据信息； degree：度域，存放该结点的度； child1childd：指针域，指向该结点的孩子。 5.2 树的存储结构缺点：结点结构不一致ACBHFEDGIA 2B 3C 2E 1I 0G 0H 0F 0D 0孩子链表表示法孩子链表的基本思想：把每个结点的孩子排列起来，看成是一个线性表，且以单链表存储，则n个结点共有 n 个孩子链表。这 n 个单链表共有 n 个头指针，这 n 个头指针又组成了一个线性表，为了便于进行查找采用顺序存储。最后，将存放 n 个头指针的数组

13、和存放n个结点的数组结合起来，构成孩子链表的表头数组。 5.2 树的存储结构如何表示孩子？将结点的所有孩子放在一起，构成线性表。child next孩子结点struct CTNode int child; CTNode *next;5.2 树的存储结构template struct CBNode DataType data; CTNode *firstchild; ;孩子链表表示法data firstchild表头结点ACBHFEDGI012345678下标 data firstchild A B C D E F G H I 5.2 树的存储结构如何查找孩子结点？时间性能？12 345 7 6

14、8 ACBHFEDGI012345678下标 data firstchild A B C D E F G H I 5.2 树的存储结构12 345 7 68 如何查找双亲结点？时间性能？双亲孩子表示法5.2 树的存储结构012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 data parent firstchild12 345 7 68 ACBHFEDGI孩子兄弟表示法5.2 树的存储结构ACBHFEDGI某结点的第一个孩子是惟一的某结点的右兄弟是惟一的设置两个分别指向该结点的第一个孩子和右兄弟的指针 template struct TNode Dat

15、aType data; TNode *firstchild, *rightsib;5.2 树的存储结构结点结构firstchild data rightsibdata：数据域，存储该结点的数据信息；firstchild：指针域，指向该结点第一个孩子；rightsib：指针域，指向该结点的右兄弟结点。 孩子兄弟表示法5.2 树的存储结构孩子兄弟表示法ACBHFEDGI A B C D E F G H I如何查找兄弟结点？时间性能？5.2 树的存储结构孩子兄弟表示法ACBHFEDGI A B C D E F G H I如何查找孩子结点？时间性能？二叉树的定义 二叉树是n(n0)个结点的有限集合，该

16、集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。5.3 二叉树的逻辑结构问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。研究二叉树的意义？二叉树的特点 每个结点最多有两棵子树； 二叉树是有序的，其次序不能任意颠倒。 5.3 二叉树的逻辑结构注意：二叉树和树是两种树结构。ABCDEFGABAB二叉树的基本形态空二叉树只有一个根结点左子树根结点只有左子树右子树根结点只有右子树左子树右子树根结点同时有左右子树5.3 二叉树的逻辑结构5.3 二叉树的逻辑结构具有3个结点的树和具有3个结点的二叉树的形态二叉树和树是两种树结构。特殊

17、的二叉树斜树1 .所有结点都只有左子树的二叉树称为左斜树；2 .所有结点都只有右子树的二叉树称为右斜树；3.左斜树和右斜树统称为斜树。1. 在斜树中，每一层只有一个结点；2.斜树的结点个数与其深度相同。 5.3 二叉树的逻辑结构斜树的特点：ABCABC满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。满二叉树的特点：叶子只能出现在最下一层；只有度为0和度为2的结点。5.3 二叉树的逻辑结构特殊的二叉树CDEFGHIJKLMNO1112131415满二叉树5.3 二叉树的逻辑结构不是满二叉树，虽然所有分支结点都有左右子树，但叶子不在

18、同一层上。满二叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉树中叶子结点个数最多A1523467BCDEFGLM89特殊的二叉树完全二叉树对一棵具有n个结点的二叉树按层序编号，如果编号为i（1in）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。5.3 二叉树的逻辑结构特殊的二叉树CDEFGHIJKLMNO1112131415CDEFGHIJ在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。5.3 二叉树的逻辑结构A1523467910BCDEFGHIJK11L12M13N14O158

19、CDEFGHIJ不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点特殊的二叉树1. 叶子结点只能出现在最下两层且最下层的叶子结点都集中在二叉树的左面；2. 完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。3. 深度为k的完全二叉树在k-1层上一定是满二叉树。4. 在同样结点个数的二叉树中，完全二叉树的深度最小。 完全二叉树的特点5.3 二叉树的逻辑结构特殊的二叉树CDEFGHIJ二叉树的基本性质 性质5-1 二叉树的第i层上最多有2i-1个结点（i1）。 证明：当i=1时，第1层只有一个根结点，而 2i-1=20

20、=1，结论显然成立。假定i=k（1ki）时结论成立，即第k层上至多有2k-1个结点， 则 i=k+1时，因为第k+1层上的结点是第k层上结点的孩子，而二叉树中每个结点最多有2个孩子，故在第k+1层上最大结点个数为第k层上的最大结点个数的二倍，即22k-12k。结论成立。5.3 二叉树的逻辑结构性质5-2 一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。 证明：由性质1，深度为k的二叉树中结点个数最多 = =2k-1；每一层至少要有一个结点，因此深度为k的二叉树，至少有k个结点。5.3 二叉树的逻辑结构深度为k且具有2k-1个结点的二叉树一定是满二叉树，深度为k且具有k个结点的二叉

21、树不一定是斜树。二叉树的基本性质 性质5-3 在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有: n0n21。 证明: 设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有： nn0n1n2 在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，一个度为1的结点射出一个分枝，一个度为2的结点射出两个分枝，所以有： n 1 n12n2因此可以得到：n0n21 。5.3 二叉树的逻辑结构二叉树的基本性质 5.3 二叉树的逻辑结构n个结点的满二叉树有多少个叶子结点？解：因为在满二叉树中没有度为1的结点，只有度为0的叶子结点和度为2的分支结点，所以，n n0 + n2n0n2

22、 + 1 即叶子结点n0（n + 1）/2 二叉树的基本性质 性质5-3 在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有: n0n21。 性质5-4 具有n个结点的完全二叉树的深度为 log2n +1。 5.3 二叉树的逻辑结构证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立 2k-1 n 2k 2k-1-12k-12k-1第k-1层第k层最少结点数最多结点数完全二叉树的基本性质 5.3 二叉树的逻辑结构证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立 2k-1 n 2k完全二叉树的基本性质 性质5-

23、4 具有n个结点的完全二叉树的深度为 log2n +1。 对不等式取对数，有： k-1log2nk即： log2nklog2n+1由于k是整数，故必有k log2n +1。 性质5-5 对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1in）的结点（简称为结点i），有： （1）如果i1，则结点i的双亲结点的序号为 i/2；如果i1，则结点i是根结点，无双亲结点。 （2）如果2in，则结点i的左孩子的序号为2i；如果2in，则结点i无左孩子。 （3）如果2i+1n，则结点i的右孩子的序号为2i+1；如果2i+1n，则结点 i无右孩子。 5.3 二叉树的逻辑结构完全二叉树

24、的基本性质一棵具有n个结点的完全二叉树中从1开始按层序编号，则 结点i的双亲结点为 i/2； 结点i的左孩子为2i； 结点i的右孩子为2i1。 5.3 二叉树的逻辑结构性质5表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。完全二叉树的基本性质 二叉树的抽象数据类型定义ADT BiTreeData 由一个根结点和两棵互不相交的左右子树构成， 结点具有相同数据类型及层次关系Operation 5.3 二叉树的逻辑结构同树类似，在不同的应用中，二叉树的基本操作不尽相同。下面给出一个二叉树抽象数据类型定义的例子，简单起见，基本操作只包含二叉树的遍历，在实际应用中

25、，应根据具体需要重新定义其基本操作。 InitBiTree 前置条件：无 输入：无 功能：初始化一棵二叉树 输出：无 后置条件：构造一个空的二叉树DestroyBiTree 前置条件：二叉树已存在 输入：无 功能：销毁一棵二叉树 输出：无 后置条件：释放二叉树占用的存储空间 二叉树的抽象数据类型定义5.3 二叉树的逻辑结构 PreOrder 前置条件：二叉树已存在 输入：无 功能：前序遍历二叉树 输出：二叉树中结点的一个线性排列 后置条件：二叉树不变 InOrder 前置条件：二叉树已存在 输入：无 功能：中序遍历二叉树 输出：二叉树中结点的一个线性排列 后置条件：二叉树不变 二叉树的抽象数据

26、类型定义5.3 二叉树的逻辑结构 PostOrder 前置条件：二叉树已存在 输入：无 功能：后序遍历二叉树 输出：二叉树中结点的一个线性排列 后置条件：二叉树不变 LeverOrder 前置条件：二叉树已存在 输入：无 功能：层序遍历二叉树 输出：二叉树中结点的一个线性排列 后置条件：二叉树不变 endADT二叉树的抽象数据类型定义5.3 二叉树的逻辑结构二叉树的遍历操作 二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。二叉树遍历操作的结果？非线性结构线性化5.3 二叉树的逻辑结构抽象操作，可以是对结点进行的各种处理，这里简化为输出结点

27、的数据。前序遍历中序遍历后序遍历层序遍历 二叉树的遍历方式：DLR、LDR、LRD、DRL、RDL、RLD 如果限定先左后右，则二叉树遍历方式有三种：前序：DLR中序：LDR后序：LRD层序遍历：按二叉树的层序编号的次序访问各结点。 5.3 二叉树的逻辑结构考虑二叉树的组成：根结点D左子树L右子树R二叉树前序（根）遍历若二叉树为空，则空操作返回；否则：访问根结点；前序遍历根结点的左子树；前序遍历根结点的右子树。5.3 二叉树的逻辑结构前序遍历序列：A B D G C E FABCDEFG二叉树的遍历操作 中序（根）遍历若二叉树为空，则空操作返回；否则：中序遍历根结点的左子树；访问根结点；中序遍

28、历根结点的右子树。 5.3 二叉树的逻辑结构中序遍历序列：D G B A E C FABCDEFG二叉树的遍历操作 后序（根）遍历若二叉树为空，则空操作返回；否则：后序遍历根结点的左子树；后序遍历根结点的右子树。访问根结点；5.3 二叉树的逻辑结构后序遍历序列：G D B E F C AABCDEFG二叉树的遍历操作 层序遍历二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。 5.3 二叉树的逻辑结构层序遍历序列：A B C D E F GABCDEFG二叉树的遍历操作 5.3 二叉树的逻辑结构-/+*abcdef二叉树遍历操

29、作练习前序遍历结果：- + a * b - c d / e f中序遍历结果：a + b * c - d - e / f后序遍历结果：a b c d - * + e f / -5.3 二叉树的逻辑结构若已知一棵二叉树的前序（或中序，或后序，或层序）序列，能否唯一确定这棵二叉树呢？ABC例：已知前序序列为ABC，则可能的二叉树有5种。ABC二叉树的遍历操作 5.3 二叉树的逻辑结构例：已知前序遍历序列为ABC，后序遍历序列为CBA，则下列二叉树都满足条件。ABCABC若已知一棵二叉树的前序序列和后序序列，能否唯一确定这棵二叉树呢？二叉树的遍历操作 若已知一棵二叉树的前序序列和中序序列，能否唯一确定

30、这棵二叉树呢？怎样确定？ 例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHI 和BCAEDGHFI，如何构造该二叉树呢? 5.3 二叉树的逻辑结构二叉树的遍历操作 前序：A B C D E F G H I中序：B C A E D G H F I前序：B C中序：B C5.3 二叉树的逻辑结构 B C D EF GH IA前序： D E F G H I中序： E D G H F IABCDEFGHI前序：F G H I中序：G H F I5.3 二叉树的逻辑结构前序： D E F G H I中序： E D G H F IABCDEFGHIABCDEFIGH1. 根据前序序列

31、的第一个元素建立根结点；2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；3. 在前序序列中确定左右子树的前序序列；4. 由左子树的前序序列和中序序列建立左子树；5. 由右子树的前序序列和中序序列建立右子树。 5.3 二叉树的逻辑结构已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下： 二叉树的遍历操作 顺序存储结构二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置（下标）应能体现结点之间的逻辑关系父子关系。 如何利用数组下标来反映结点之间的逻辑关系?完全二叉树和满二叉树中结点的序号可以唯一地反映出结点之间的逻辑关系 。5.4 二叉树的存储结构及实现

32、A B C D E F G H I J数组下标 1 2 3 4 5 6 7 8 9 10完全二叉树的顺序存储5.4 二叉树的存储结构及实现CDEFGHIJ以编号为下标二叉树的顺序存储ABCDEFG数组下标 1 2 3 4 5 6 7 8 9 10 11 12 135.4 二叉树的存储结构及实现ABCDEGF以编号为下标ABCDEGF123561013按照完全二叉树编号二叉树的顺序存储ABCDEFG数组下标 0 1 2 3 4 5 6 7 8 9 10 11 125.4 二叉树的存储结构及实现ABCDEGFABCDEGF123561013按照完全二叉树编号注意到C+语言

33、的数组下标从0开始，也可以将编号为i的结点存储到下标为i-1的位置。 一棵斜树的顺序存储会怎样呢？深度为k的右斜树，k个结点需分配2k1个存储单元。 一棵二叉树改造后成完全二叉树形态，需增加很多空结点，造成存储空间的浪费。5.4 二叉树的存储结构及实现二叉树的顺序存储结构一般仅存储完全二叉树ABC137D15二叉链表基本思想：令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信息外，还要设置指示左右孩子的指针。 结点结构： lchild data rchild其中，data：数据域，存放该结点的数据信息； lchild：左指针域，存放指向左孩子的指针； rchild：右

34、指针域，存放指向右孩子的指针。 5.4 二叉树的存储结构及实现template struct BiNode DataType data; BiNode *lchild, *rchild;5.4 二叉树的存储结构及实现lchild datarchild左孩子结点右孩子结点二叉链表GFEDBAABCDEFGC二叉链表5.4 二叉树的存储结构及实现具有n个结点的二叉链表中，有多少个空指针？GFEDBAABCDEFGC二叉链表5.4 二叉树的存储结构及实现具有n个结点的二叉链表中，有n+1个空指针。template class BiTreepublic: BiTree( )root = Creat(r

35、oot); /构造函数，建立一棵二叉树 BiTree( )Release(root); /析构函数 void PreOrder( )PreOrder(root); /前序遍历二叉树 void InOrder( )InOrder(root); /中序遍历二叉树 void PostOrder( )PostOrder(root); /后序遍历二叉树 void LeverOrder( ); /层序遍历二叉树private: BiNode *root; /指向根结点的头指针 BiNode *Creat(BiNode *bt); /构造函数调用 void Release(BiNode *bt); /析构函

36、数调用 void PreOrder(BiNode *bt); /前序遍历函数调用 void InOrder(BiNode *bt); /中序遍历函数调用 void PostOrder(BiNode *bt); /后序遍历函数调用;5.4 二叉树的存储结构及实现前序遍历递归算法template void BiTree : PreOrder(BiNode *bt) if (bt = NULL) return; /递归调用的结束条件 else cout data; /访问根结点bt的数据域 PreOrder(bt-lchild); /前序递归遍历bt的左子树 PreOrder(bt-rchild);

37、 /前序递归遍历bt的右子树 5.4 二叉树的存储结构及实现中序遍历递归算法 template void BiTree : InOrder (BiNode *bt) if (bt = NULL) return; /递归调用的结束条件 else InOrder(bt-lchild); /中序递归遍历bt的左子树 cout data; /访问根结点bt的数据域 InOrder(bt-rchild); /中序递归遍历bt的右子树 5.4 二叉树的存储结构及实现后序遍历递归算法template void BiTree : PostOrder(BiNode *bt) if (bt = NULL) ret

38、urn; /递归调用的结束条件 else PostOrder(bt-lchild); /后序递归遍历bt的左子树 PostOrder(bt-rchild); /后序递归遍历bt的右子树 cout data; /访问根结点bt的数据域 5.4 二叉树的存储结构及实现层序遍历5.4 二叉树的存储结构及实现ABCDEFG遍历序列：AABCBDCEFGDEFG层序遍历队列Q初始化；2. 如果二叉树非空，将根指针入队；3. 循环直到队列Q为空 3.1 q=队列Q的队头元素出队； 3.2 访问结点q的数据域； 3.3 若结点q存在左孩子，则将左孩子指针入队； 3.4 若结点q存在右孩子，则将右孩子指针入队

39、；5.4 二叉树的存储结构及实现层序遍历template void BiTree : LeverOrder( ) front = rear = -1; /采用顺序队列，并假定不会发生上溢 if (root = NULL) return; /二叉树为空，算法结束 Q+rear = root; /根指针入队 while (front != rear) /当队列非空时 q = Q+front; /出队 cout data; if (q-lchild != NULL) Q+rear = q-lchild; if (q-rchild != NULL) Q+rear = q-rchild; 5.4 二叉树

40、的存储结构及实现构造函数建立二叉树为了建立一棵二叉树，将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如“#”，以标识其为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。 为什么如此处理?5.4 二叉树的存储结构及实现如何由一种遍历序列生成该二叉树？遍历是二叉树各种操作的基础，可以在遍历的过程中进行各种操作，例如建立一棵二叉树。扩展二叉树的前序遍历序列:A B # D # # C # #5.4 二叉树的存储结构及实现DBAC#DBAC#构造函数建立二叉树设二叉树中的结点均为一个字符。假设扩展二叉树的前序遍历序列由键盘输入，root为指向根结点的指针，二叉链表的建立过程是：首先输入根结

41、点，若输入的是一个“#”字符，则表明该二叉树为空树，即root=NULL；否则输入的字符应该赋给root-data,，之后依次递归建立它的左子树和右子树 。5.4 二叉树的存储结构及实现构造函数建立二叉树template BiTree : BiTree( ) root = Creat(root); template BiNode *BiTree:Creat(BiNode *bt) cin ch; /输入结点的数据信息，假设为字符 if (ch = # ) bt = NULL; /建立一棵空树 else bt = new BiNode; bt-data = ch; /生成一个结点，数据域为ch

42、bt-lchild = Creat(bt-lchild); /递归建立左子树 bt-rchild = Creat(bt-rchild); /递归建立右子树 return bt;5.4 二叉树的存储结构及实现二叉树算法设计练习 遍历二叉树是二叉树各种操作的基础，遍历算法中对每个结点的访问操作可以是多种形式及多个操作，根据遍历算法的框架，适当修改访问操作的内容，可以派生出很多关于二叉树的应用算法。 void InOrder (BiNode *root) if (root=NULL) return; else InOrder(root-lchild); coutdata; InOrder(root-

43、rchild); 二叉树算法设计练习设计算法求二叉树的结点个数。 void Count(BiNode *root) /count为全局量并已初始化为0 if (root = NULL) return; else Count(root-lchild); count+; Count(root-rchild); 二叉树算法设计练习设计算法按前序次序打印二叉树中的叶子结点。 void PreOrder(BiNode *root) if (root = NULL) return; else if (!root-lchild & !root-rchild) coutdata; PreOrder(root-

44、lchild); PreOrder(root-rchild); 二叉树算法设计练习设计算法求二叉树的深度。 int Depth(BiNode *root) if (root = NULL) return 0; else hl= Depth(root-lchild); hr= Depth(root -rchild); return max(hl, hr)+1; 二叉树算法设计练习设计算法求树中结点 x 的第 i 个孩子。 TNode *Search(TNode *root, DataType x, int i) if (root-data = x) j=1; p=root-firstchild;

45、 while (p!=NULL & jrightsib; if (p != NULL) return p; else return NULL; Search(root-firstchild, x, i); Search(root-rightsib, x, i);三叉链表5.4 二叉树的存储结构及实现GFEDBAABCDEFGC在二叉链表中，如何求某结点的双亲？三叉链表 lchild dataparentrchild在二叉链表的基础上增加了一个指向双亲的指针域。结点结构其中：data、lchild和rchild三个域的含义同二叉链表的结点结构；parent域为指向该结点的双亲结点的指针。 5.4

46、 二叉树的存储结构及实现ABCDEFGABDEFCG三叉链表5.4 二叉树的存储结构及实现ABCDEFG三叉链表的静态链表形式5.4 二叉树的存储结构及实现0123456data parent lchild rchildABCDEFG-1 0 0 1 2 2 3 1 3 4-1-1-1-1 2-1 5 6-1-1-1线索链表5.4 二叉树的存储结构及实现如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：D G B A F C F如果二叉树不改变，如何保存？顺序存储D G B A F C F线索链表5.4 二叉树的存储结构及实现如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：D

47、 G B A F C F如果二叉树改变，如何保存？链接存储 D F 线索链表5.4 二叉树的存储结构及实现如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：D G B A F C F如何将二叉链表与中序链表结合？链接存储 D F 线索链表线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索；线索化：使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；线索链表：加上线索的二叉链表称为线索链表。5.4 二叉树的存储结构及实现如何保存二叉树的某种遍历序列？将二叉链表中的空指针域指向其前驱结点和后继结点 ltag lchild data rchild rtag0: lc

48、hild指向该结点的左孩子1: lchild指向该结点的前驱结点0: rchild指向该结点的右孩子1: rchild指向该结点的后继结点ltag=rtag=5.4 二叉树的存储结构及实现结点结构线索链表enum flag Child, Thread; template struct ThrNode DataType data; ThrNode *lchild, *rchild; flag ltag, rtag;5.4 二叉树的存储结构及实现线索链表 ltag lchild data child rtag结点结构二叉树的遍历方式有4种，故有4种意义下的前驱和后继，相应的有4种线索二叉树： 前序

49、线索二叉树 中序线索二叉树 后序线索二叉树 层序线索二叉树5.4 二叉树的存储结构及实现线索二叉树FABDCEG中序线索二叉树5.4 二叉树的存储结构及实现线索二叉树中序序列：D G B A E C Ftemplate class InThrBiTreepublic: InThrBiTree( ); /构造函数，建立中序线索链表 InThrBiTree( ); /析构函数，释放各结点的存储空间 ThrNode *Next(ThrNode *p); /查找p的后继 void InOrder( ); /中序遍历线索链表private: ThrNode *root; /指向线索链表的头指针 ThrN

50、ode *Creat(ThrNode *bt); void ThrBiTree(ThrNode *bt, ThrNode *pre); /构造函数调用;5.4 二叉树的存储结构及实现中序线索链表类的声明分析：建立线索链表，实质上就是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历该二叉树时才能得到。5.4 二叉树的存储结构及实现建立二叉链表遍历二叉树，将空指针改为线索中序线索链表的建立构造函数A头指针BCDEFG00000000000000中序线索链表的建立过程5.4 二叉树的存储结构及实现已经建立起二叉链表A头指针BCDEFG00000000000000中序线索链表

51、的建立过程5.4 二叉树的存储结构及实现中序遍历二叉链表p为正在访问的结点pre为刚访问的结点p1A头指针BCDEFG00000000000000中序线索链表的建立过程5.4 二叉树的存储结构及实现中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre1p1A头指针BCDEFG00000000000000中序线索链表的建立过程5.4 二叉树的存储结构及实现中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11p1A头指针BCDEFG00000000000000中序线索链表的建立过程5.4 二叉树的存储结构及实现中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11p1

52、1A头指针BCDEFG00000000000000中序线索链表的建立过程5.4 二叉树的存储结构及实现中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11p111A头指针BCDEFG00000000000000中序线索链表的建立过程5.4 二叉树的存储结构及实现中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11p1111A头指针BCDEFG00000000000000中序线索链表的建立过程5.4 二叉树的存储结构及实现中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11p11111A头指针BCDEFG00000000000000中序线索链表的建立过程5.4

53、 二叉树的存储结构及实现中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11111111在遍历过程中，访问当前结点root的操作为：如果root的左、右指针域为空，则将相应标志置1；若root的左指针域为空，则令其指向它的前驱，这需要设指针pre始终指向刚刚访问过的结点，显然pre的初值为NULL；若pre的右指针域为空，则令其指向它的后继，即当前访问的结点root; 令pre指向刚刚访问过的结点root；5.4 二叉树的存储结构及实现中序线索链表的建立1. 建立二叉链表，将每个结点的左右标志置为0；2. 遍历二叉链表，建立线索； 2.1 如果二叉链表root为空，则空操作返回；

54、2.2 对root的左子树建立线索； 2.3 对根结点root建立线索； 2.3.1 若root没有左孩子，则为root加上前驱线索; 2.3.2 若root没有右孩子，则将root右标志置为1； 2.3.3 若结点pre右标志为1，则为pre加上后继线索； 2.3.4 令pre指向刚刚访问的结点root； 2.4 对root的右子树建立线索。5.4 二叉树的存储结构及实现中序线索链表的建立构造函数template void InThrBiTree :ThrBiTree(ThrNode *bt, ThrNode *pre) if (bt = NULL) return; ThrBiTree(bt

55、-lchild, pre); if (bt-lchild = NULL) /对bt的左指针进行处理 bt-ltag = 1; bt-lchild = pre; /设置pre的前驱线索 if (bt-rchild = NULL) bt-rtag = 1; /对bt的右指针进行处理 if (pre-rtag = 1) pre-rchild = bt; /设置pre的后继线索 pre = bt; ThrBiTree(bt-rchild, pre);5.4 二叉树的存储结构及实现中序线索链表的建立构造函数5.4 二叉树的存储结构及实现中序线索链表查找后继FABDCEG 如果结点p的右标志为1，则表明该

56、结点的右指针是线索； 如果结点p的右标志为0，则表明该结点有右孩子。根据中序遍历的操作定义，它的后继结点应该是遍历其右子树时第一个访问的结点，即右子树中的最左下结点。template ThrNode *InThrBiTree : Next( ThrNode *p) if (p-rtag = 1) q = p-rchild; /右标志为1，可直接得到后继结点 else q = p-rchild; /工作指针q指向结点p的右孩子 while (q-ltag = 0) /查找最左下结点 q = q-lchild; return q;5.4 二叉树的存储结构及实现中序线索链表查找后继二叉树前序遍历的非

57、递归算法的关键：在前序遍历过某结点的整个左子树后，如何找到该结点的右子树的根指针。解决办法：在访问完该结点后，将该结点的指针保存在栈中，以便以后能通过它找到该结点的右子树。 在前序遍历中，设要遍历二叉树的根指针为root，则有两种可能： 若root!=NULL，则表明？如何处理？ 若root=NULL，则表明？如何处理？前序遍历非递归算法5.5 二叉树遍历的非递归算法访问结点序列:A栈S内容:BD A B前序遍历的非递归实现 ADBC5.5 二叉树遍历的非递归算法访问结点序列:A栈S内容:BD A前序遍历的非递归实现 ADBC D5.5 二叉树遍历的非递归算法访问结点序列:A栈S内容:BD C

58、前序遍历的非递归实现 ADBCC5.5 二叉树遍历的非递归算法1.栈s初始化；2.循环直到root为空且栈s为空 2.1 当root不空时循环2.1.1 输出root-data; 2.1.2 将指针root的值保存到栈中； 2.1.3 继续遍历root的左子树2.2 如果栈s不空，则2.2.1 将栈顶元素弹出至root；2.2.2 准备遍历root的右子树； 前序遍历非递归算法（伪代码）5.5 二叉树遍历的非递归算法前序遍历非递归算法（伪代码）template void BiTree:PreOrder(BiNode *root) top = -1; /采用顺序栈，并假定不会发生上溢 while

59、 (root != NULL | top != -1) while (root != NULL) coutdata; s+top = root; root = root-lchild; if (top != -1) root = stop-; root = root-rchild; 5.5 二叉树遍历的非递归算法中序遍历非递归算法在二叉树的中序遍历中，访问结点的操作发生在该结点的左子树遍历完毕并准备遍历右子树时，所以，在遍历过程中遇到某结点时并不能立即访问它，而是将它压栈，等到它的左子树遍历完毕后，再从栈中弹出并访问之。中序遍历的非递归算法只需将前序遍历的非递归算法中的输出语句coutdata

60、移到bt = stop-之后即可。 5.5 二叉树遍历的非递归算法中序遍历非递归算法template void BiTree:PreOrder(BiNode *root) top = -1; /采用顺序栈，并假定不会发生上溢 while (root != NULL | top != -1) while (root != NULL) s+top = root; root = root-lchild; if (top != -1) root = stop-; coutdata; root = root-rchild; 5.5 二叉树遍历的非递归算法后序遍历非递归算法在后序遍历过程中，结点要入两次栈