第6章 树与二叉树

2 6.1 树 树 (tree) 结构是一种多分支多层次的数据结构，由一组结点组成。由于它呈现与自然界树类似的结构形式，所以称之为树。在许多算法中，常用树型结构描述问题的求解过程或表示求解的对策等。 树的逻辑结构 树的存储结构

6.1.1 树的逻辑结构 1. 树的定义 树是由 n (n≥0) 个结点组成的有限集。在任意一棵非空树 T 中： 3 6.1.1 树的逻辑结构 1. 树的定义 树是由 n (n≥0) 个结点组成的有限集。在任意一棵非空树 T 中： ① 有且仅有一个特定的称为根 (root) 结点； ② 当 n>1 时，其余结点分成 m (m>0) 个互不相交的有限集T1，T2，…，Tm，其中每一个集合本身又都是一棵树，并且称为根的子树。

 InsertChild (Tree, p, child); 初始条件：树 Tree 存在，p 指向 Tree 中某个结点， 4 2. 树的基本操作  InitTree (tree); 操作结果：构造空树 Tree。  InsertChild (Tree, p, child); 初始条件：树 Tree 存在，p 指向 Tree 中某个结点， 1≤i≤p 所指结点的度+1，非空树 child 与Tree 不相交。 操作结果：插入child为 T 中 p 所指结点的子 树。

3. 树的基本概念 树结构中经常会用到一些基本术语。例如： 结点 双亲及孩子 层次 结点的度 兄弟 树的深度 叶结点 堂兄弟 有序树 5 3. 树的基本概念 树结构中经常会用到一些基本术语。例如： 结点 双亲及孩子 层次 结点的度 兄弟 树的深度 叶结点 堂兄弟 有序树 分支结点 祖先 无序树 树的度 子孙 森林

6.1.2 树的存储结构 1. 双亲表示法 假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在连续空间中的位置。 6.1.2 树的存储结构 6 1. 双亲表示法 假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在连续空间中的位置。 #define Max 100 typedef struct TNode { // 结点结构定义 DataType data; // 数据域 int parent; // 双亲位置域 } TNode; typedef struct { // 双亲表示结构定义 TNode tree[MAX]; // 结点数组 int nodenum; // 结点数 } ParentTree; // 双亲表示结构类型名

树的双亲表示存储结构利用了每个结点（根结点除外）只有惟一双亲的性质。 2 B 3 C 4 D 1 5 E 1 6 F 3 7 G 6 8 H 在树的双亲存储结构中，求双亲 Parent(T, x) 操作非常方便。求树根结点 Root(x) 操作也很简单：反复调用 Parent 操作，直到遇见无双亲的结点时，即 T.parent = -1 时，便找到了惟一的无双亲的根结点。 在树的双亲存储结构中，求某结点的孩子结点时需遍历整个结构。例如求树中结点 F 的孩子，就需要在整个结构中从头到尾扫描一遍 T.parent 域，T.parent = 6 的结点 G、H、K 就是结点 F 的孩子。 树 数组下标 双亲存储结构 R -1 R A B C D E F G H K 1 A 树的双亲表示存储结构利用了每个结点（根结点除外）只有惟一双亲的性质。 2 B 3 C 4 D 1 5 E 1 6 F 3 7 G 6 8 H 6 9 K 6

8 2. 孩子表示法 由于树中每个结点可能有多棵子树，则可以用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，此时，链表中的结点可以有如下 3 种结构格式： 同构结点格式 不同构结点格式 单链表存储结构

(1) 同构结点格式。即多重链表中的结点是同构的。 9 (1) 同构结点格式。即多重链表中的结点是同构的。 data child1 child2 …… childd 其中 d 为树的度。由于树中很多结点的度都小于 d，所以链表中有很多空链域，空间比较浪费。 设树的度为 k，结点数为 n。若采用同构结点格式，每个结点具有 k 个固定链域，那么共有 nk 个链域。由于 n 个结点要有 ( n - 1) 个枝相连，而每枝需要 1 个链域。因此，这棵树的空链域的个树为： n ( k – 1 ) +1。 由此可知，树的度越大，空链域越多。如果采用同构结点格式将造成空间的极大浪费。

(2) 不同构结点格式。即多重链表中的结点是不同构的。 10 (2) 不同构结点格式。即多重链表中的结点是不同构的。 degree child1 child2 …… childd data 其中 为结点的度，degree 域的值和 相同。这 d d 种存储结构避免了孩子表示法存储结构中出现的空链域，节约存储空间。但是由于每个结点的孩子链域数不同，所以在这种结构上进行的各种操作不易实现。

11 (3) 单链表存储结构。即把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作为存储结构，则 n 个结点有 n 个孩子链表（叶子结点的孩子链表为空表）。而 n 个头指针又组成一个线性表，为了便于查找，可以采用顺序存储结构。

树 A 3 5 ∧ B R A B C D E F G H k C 6 ∧ 根位置 D R 1 2 ∧ E F 7 8 9 ∧ G H K 12 在树的孩子单链表结构中，查找某结点的双亲需要按照该结点在头结点顺序表中的位置序号在每个孩子链表中扫描，当在孩子域 child 中找到相同的序号时，则单链表表头的结点就是要找的双亲。 例如，要寻找树中 G 结点的双亲结点。G 结点在头结点顺序表中的位置序号为 7，则在孩子链表中查询 child = 7 的孩子结点，当找到的时候，该单链表的表头结点 F 就是 G 的双亲结点。 树 与树的双亲表示法相反，树的孩子单链表表示法便于查找树中任一结点的孩子：由链表中某结点的指针域 next 即可以得到该结点的孩子结点。 A 3 5 ∧ 1 B ∧ R A B C D E F G H k 2 C 6 ∧ 根位置 3 D ∧ 4 R 1 2 ∧ 5 E ∧ 6 F 7 8 9 ∧ 7 G ∧ 8 H ∧ 9 K ∧

13 3. 孩子兄弟表示法 树的孩子兄弟表示法又称二叉树表示法，或二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点的结构相同，都有 3 个域：数据域 data 存放树中结点的信息；孩子域 firstchild 存放该结点的第一个孩子结点（从左算起）的地址；兄弟域 nextsibling 存放该结点的下一个兄弟结点（从左向右）的地址。

R ∧ A 树 D ∧ B ∧ R A B C D E F G H K E ∧ C ∧ F ∧ G ∧ H ∧ K ∧ 14 例如，要访问 F 结点的第 3 个孩子，只要先从 F 结点的 Firstchild 域找到第一个孩子 G 结点后，再沿着 G 结点的 Nextsibling 域连续走 2 步，找到 K 结点，这就是 F 结点的第 3 个孩子结点。但是，在这个结构上查找某结点的双亲结点不是很方便，若为每个结点再增设一个双亲 parent 域，则查找某结点的双亲的操作也很方便。 R ∧ 在树的二叉链表存储结构中，易于实现找结点等的操作。如果要访问树中结点 x 的第 i 个孩子，那么只需要先从该结点的 firstchild 域找到第 1 个孩子结点，然后再沿孩子结点的 nextsibling 域连续走 i-1 步，便可以找到结点 x 的第 i 个孩子。 A 树 树的二叉链表存储结构的最大优点就是结点的结构统一，和前面讲的二叉树表示法完全一样，因此可以利用二叉树的算法来实现对树的操作。 D ∧ B ∧ R A B C D E F G H K E ∧ C ∧ F ∧ G ∧ H ∧ K ∧

6.2 二叉树 二叉树的逻辑结构 二叉树的基本性质 二叉树的存储结构 15 6.2 二叉树 二叉树 (binary tree) 是另一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于 2 的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。 二叉树的逻辑结构 二叉树的基本性质 二叉树的存储结构

16 6.2.1 二叉树的逻辑结构 1. 二叉树的定义 二叉树是一个有限的结点的集合，该集合或者为空，或者由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 二叉树定义是一个递归定义，即在二叉树的定义中又用到二叉树的概念。

6.2.2 二叉树的基本性质 性质1：在二叉树的第 i 层上至多有 2i-1 个结点（i≥1）。 证明：利用归纳法容易证得此性质。 6.2.2 二叉树的基本性质 17 性质1：在二叉树的第 i 层上至多有 2i-1 个结点（i≥1）。 证明：利用归纳法容易证得此性质。 i = 1 时，只有一个根结点。2i-1 = 20 = 1，命题成立。 假定对所有的 j (1≤j＜i)，命题成立，即第 j 层上至多有 2 j-1 个结点。那么，可以证明 j = i 时命题也成立。 根据归纳假设，第 i-1 层上至多有 2i-2 个结点。由于二叉树的每个结点的度最多为 2，所以在第 i 层上最多的结点数为第 i-1 层上的 2 倍，即 2×2i-2 = 2i-1。

性质2：深度为 k 的二叉树至多有 2k－1 个结点（k≥1）。 18 性质2：深度为 k 的二叉树至多有 2k－1 个结点（k≥1）。 证明： 由性质1 可见，深度为 k 的二叉树的最大结点数为 = 2k－1

性质3：对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0 ＝ n2 + 1。 19 性质3：对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0 ＝ n2 + 1。 证明： (1) 设 n1 为二叉树 T 中度为 1 的结点数。n 为二叉树中总结点数。因为二叉树中所有结点的度均小于或等于 2，则：n = n0 + n1 + n2 。 (2) 设 B 为二叉树 T 中的分支总数。 从入支的角度看，二叉树中除了根结点外，其余结点都有一个且仅有一个入支，则：n = B + 1。 从出支的角度看，度为 1 的结点只有一个出支，度为 2 的结点有两个出支，则：B = n1 + 2n2 故：n = n1 + 2n2 + 1；最后得到： n0 = n2 + 1。

满二叉树：一棵深度为 k 并且有 2k-1 个结点的二叉树，称之为满二叉树。 20 为便于介绍下面两个二叉树性质，先了解满二叉树 (full binary tree) 和完全二叉树 (complete binary tree) 的概念。 满二叉树：一棵深度为 k 并且有 2k-1 个结点的二叉树，称之为满二叉树。 满二叉树的特点是：每一层上的结点数都达到最大值；满二叉树中只有度为 0 和度为 2 的结点，不存在度为 1 的结点；每一个结点均有两棵高度相同的子树，叶子结点都在树的最下面的同一层上。

如果对满二叉树的结点进行编号，约定编号从根结点起，自上而下，自左至右。由此可以引出完全二叉树的定义。 21 如果对满二叉树的结点进行编号，约定编号从根结点起，自上而下，自左至右。由此可以引出完全二叉树的定义。 完全二叉树：一棵深度为 k 并且有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时，称之为完全二叉树。 完全二叉树的特点是：二叉树中的叶子结点只可能出现在二叉树中层次最大的两层上；最下一层的结点一定是从最左边开始向右放的；并且若某个结点没有左孩子，则它一定没有右孩子。

log2n  + 1 （ x 表示不大于 x 的最大整数） 22 性质4：具有 n 个结点的完全二叉树的深度为 log2n  + 1 （ x 表示不大于 x 的最大整数） 证明： 设所求完全二叉树深度为 k，则它的前 k-1 层可视为深度为 k-1 的满二叉树，共有 2k-1-1 个结点，故该完全二叉树的总结点数 n 一定满足式子：n＞2k-1-1。 根据性质 2，可以确定：n ≤ 2k-1 由此得到：2k-1-1＜n≤2k-1 或 2k-1 ≤n＜2k 等价关系：k-1≤log2n＜k 因为 k 是整数，所以 k-1 = log2n，即 k = log2n + 1

(1) 若 i = 1，则结点 i 是二叉树的根，没有双亲结点；若 i ＞1，则其双亲结点是结点 i / 2。 23 性质5：如果对一棵有 n 个结点的完全二叉树（此二叉树的深度为 log2n +1）的结点按照层次编号（从第 1 层到第 log2n +1 层，每层从左到右），那么对任一结点 i（1 ≤i ≤n），有 (1) 若 i = 1，则结点 i 是二叉树的根，没有双亲结点；若 i ＞1，则其双亲结点是结点 i / 2。 (2) 若 2i ＞n，则结点 i 没有左孩子（结点 i 为叶子结点）；否则其左孩子是结点 2i。 (3) 若 2i + 1＞n，则结点 i 没有右孩子；否则其右孩子是结点 2i + 1。

6.2.3 二叉树的存储结构 二叉树和其他数据结构一样也分顺序存储结构和链式存储结构；而链式存储结构又分二叉链表存储结构和三叉链表存储结构。 24 6.2.3 二叉树的存储结构 二叉树和其他数据结构一样也分顺序存储结构和链式存储结构；而链式存储结构又分二叉链表存储结构和三叉链表存储结构。

二叉树的顺序存储结构就是用一组地址连续的存储单元来存放一棵二叉树的所有结点元素。 25 1. 顺序存储结构 二叉树的顺序存储结构就是用一组地址连续的存储单元来存放一棵二叉树的所有结点元素。 # define MAX_TREE_SIZE 100 // 二叉树的最大结点数 typedef DataType SqBiTree[MAX_TREE_SIZE]; // 定义顺序树类型SqBiTree，约定0 号单元存储根结点 SqBiTree bt; //定义了一棵二叉树bt

顺序存储结构仅适用于完全二叉树。如果存储一般二叉树，则会造成存储空间的浪费，这时就需要使用二叉树的链式存储结构。 26 2. 链式存储结构 顺序存储结构仅适用于完全二叉树。如果存储一般二叉树，则会造成存储空间的浪费，这时就需要使用二叉树的链式存储结构。 二叉树的链式存储结构主要是设计结点结构。根据结点结构的不同，又可以分为二叉链表存储结构和三叉链表存储结构。

(1) 二叉链表存储结构 27 二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点包括三个域：数据域、左指针域和右指针域，称为二叉链表存储结构。 左孩子指针 lchild data rchild 右孩子指针 数据域 tyepdef struct Node { DataType data; structNode *lchild, *rchild; // 左右孩子指针 } BiTNode *BiTree; // 二叉链表存储结构类型名

(2) 三叉链表存储结构 28 为方便找到结点双亲，在二叉链表结构中增加一个指向其双亲结点的指针域，则表示二叉树的链表中的结点包括四个域：数据域、左指针域、右指针域和双亲指针域，称为三叉链表存储结构。 左孩子指针 lchild data parent rchild 右孩子指针 数据域 双亲指针 tyepdef struct TriTNode { TElemType data; struct TriTNode *lchild, *rchild, *parent; } TriTNode *TriTree; // 三叉链表存储结构类型名

29 6.4 遍历二叉树 在二叉树的很多应用中，常要求在二叉树中查找某些指定的结点或对二叉树中全部结点逐一进行某种操作，这就需要依次访问二叉树中的结点，即遍历二叉树。 遍历二叉树 (traversing binary tree) 是指按某种规律巡查二叉树，对树中的每个结点访问一次且仅访问一次。在访问每个结点时可对结点进行各种操作，如：输出结点的信息、对结点进行计数、修改结点的信息等。

30 遍历二叉树的操作定义 遍历二叉树的递归算法 遍历二叉树的非递归算法 建立二叉树的算法

6.3.1 遍历二叉树的操作定义 31 二叉树的定义是递归的，一棵非空的二叉树由三个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。 设以 L、D、R 分别表示遍历左子树、访问根结点和遍历右子树，则可能有 DLR、LDR、LRD、DRL、RDL、RLD 六种遍历二叉树的方案。如果限定先左子树后右子树，则只有前三种方案，分别称之为先根（序）遍历 DLR、中根（序）遍历 LDR 和后根（序）遍历 LRD。遍历左子树和右子树的规律和遍历整个二叉树的规律相同，因而这三种遍历都具有递归性。

(1) 先根（序）DLR 遍历二叉树的操作定义 32 (1) 先根（序）DLR 遍历二叉树的操作定义 若二叉树为空，则空操作；否则： ① 访问根结点； ② 先序遍历左子树； ③ 先序遍历右子树。

(2) 中根（序）LDR 遍历二叉树的操作定义 33 (2) 中根（序）LDR 遍历二叉树的操作定义 若二叉树为空，则空操作；否则： ① 中序遍历左子树； ② 访问根结点； ③ 中序遍历右子树。

(3) 后根（序）LRD 遍历二叉树的操作定义 34 (3) 后根（序）LRD 遍历二叉树的操作定义 若二叉树为空，则空操作；否则： ① 后序遍历左子树； ② 后序遍历右子树； ③ 访问根结点。

6.3.2 遍历二叉树的递归算法 遍历二叉树可以根据二叉树的递归定义写出递归算法。分为： 先序遍历二叉树的递归算法 中序遍历二叉树的递归算法 35 6.3.2 遍历二叉树的递归算法 遍历二叉树可以根据二叉树的递归定义写出递归算法。分为： 先序遍历二叉树的递归算法 中序遍历二叉树的递归算法 后序遍历二叉树的递归算法

1. 先序遍历二叉树的递归算法 void PreOrder (BiTree root) { 36 1. 先序遍历二叉树的递归算法 void PreOrder (BiTree root) /* 采用二叉链表存储结构，root为指向二叉树根结点指针，Visit 是对数据元素操作的应用函数，先序遍历二叉树root的递归算法，对每个数据元素调用函数 Visit 。*/ { if (root!=NULL) { // 若root不为空 Visit(root->data) // 访问根结点 PreOrder (root->LChild) // 先序遍历左子树 PreOrder (root->RChild) //先序遍历右子树 } } // PreOrder

2. 中序遍历二叉树的递归算法 void InOrder (BiTree root) { 37 2. 中序遍历二叉树的递归算法 void InOrder (BiTree root) /* 采用二叉链表存储结构，root为指向二叉树(或某一子树)根结点指针，Visit 是对数据元素操作的应用函数， 中序遍历二叉树root的递归算法，对每个数据元素调用函数 Visit 。*/ { if (root!=NULL) { // 若root不为空 InOrder (root->LChild) // 中序遍历左子树 Visit(root->data) // 访问根结点 InOrder (root->RChild) //中序遍历右子树 } } // InOrder

3. 后序遍历二叉树的递归算法 void PostOrder (BiTree root) { 38 3. 后序遍历二叉树的递归算法 void PostOrder (BiTree root) /* 采用二叉链表存储结构，root为指向二叉树根结点指针，Visit 是对数据元素操作的应用函数，后序遍历二叉树root的递归算法，对每个数据元素调用函数 Visit 。*/ { if (root!=NULL) { // 若root不为空 PostOrder (root->LChild) // 后序遍历左子树 PostOrder (root->RChild) //后序遍历右子树 Visit(root->data) // 访问根结点 } } // PostOrder

对每个数据元素进行访问的时候，可以使用调用函数 Visit，最简单的 Visit 函数是： 39 对每个数据元素进行访问的时候，可以使用调用函数 Visit，最简单的 Visit 函数是： int Visit ( DataType e ) { printf (e); // 输出数据元素 e 的值 return OK; } // PrintElement

40 6.3.3 遍历二叉树的非递归算法 在有些算法语言中是不允许递归调用的，所以也有必要讨论遍历二叉树的非递归算法。非递归的程序中要用栈来保存遍历经过的路径，才能访问到二叉树中的每一个结点。分为： 先序遍历二叉树的非递归算法 中序遍历二叉树的非递归算法 后序遍历二叉树的非递归算法

使用一个栈 S，用以存放已经访问过的根结点指针，以备在访问该结点的左子树之后再访问其右子树。显然，开始时栈应该为空。 41 1. 先序遍历二叉树的非递归算法 (1) 算法思想 使用一个栈 S，用以存放已经访问过的根结点指针，以备在访问该结点的左子树之后再访问其右子树。显然，开始时栈应该为空。 算法开始时，先将栈 S 初始化，然后令 p 指向二叉树的根结点，即 p = root。 如果指向根结点的指针非空或者栈非空，则做如下操作：

如果指向根结点的指针非空，则访问根结点；然后将根结点指针进栈；最后将指针指向该结点的左子树根结点，继续遍历； 42 如果指向根结点的指针非空，则访问根结点；然后将根结点指针进栈；最后将指针指向该结点的左子树根结点，继续遍历； 如果指向根结点的指针为空，则应该退至上一层（即将栈顶存放的指针出栈）。有两种情况：  若从左子树返回，则应将指针指向当前层（即栈顶指针所指）根结点的右子树根结点， 继续遍历。  若从右子树返回，则表明当前层遍历结束，应该继续退栈。从另一个角度看，这意味着遍历右子树时不再需要保存当前层的根指针，可以直接修改指针。 当指针为空并且栈为空时，遍历结束。

(2) 算法分析 2n2 + n1 = n2 + n2 + n1 = n0 + n1 + n2 - 1 = n - 1 43 (2) 算法分析 PreOrder 非递归算法的时间复杂度 假定二叉树 T 有 n 个结点，算法中对每个结点都要入栈和出栈一次。因此，入栈和出栈都要执行 n 次。此外，只有当 p 为非空时，才对当前在栈顶的结点信息进行访问。 树中非空链域的个数为 2n2+n1，再由二叉树的性质 3 (n0 = n2+1)，可知： 2n2 + n1 = n2 + n2 + n1 = n0 + n1 + n2 - 1 = n - 1 所以，遍历每个结点的时间复杂度为 O(n)。

44 PreOrder非递归算法所需附加空间 算法所需要的附加空间为栈（用以存放已经访问的根结点）的容量。栈的容量与树的深度有关，如果每个结点需要 1 个存储单位，则遍历深度为 k 的二叉树，栈需要 k 个存储单位，即所需要的空间为 O(k)。

使用一个栈 S，用以存放待访问的根结点指针，以备在访问该结点的左子树之后再访问该结点及其右子树。显然，开始时栈应该为空。 45 2. 中序遍历二叉树的非递归算法 ① 算法思想 使用一个栈 S，用以存放待访问的根结点指针，以备在访问该结点的左子树之后再访问该结点及其右子树。显然，开始时栈应该为空。 算法开始时，先将栈 S 初始化，然后令 p 指向二叉树的根结点，即 p = root。 如果指向根结点的指针非空或者栈 S 非空，则做如下操作：

如果指向根结点指针非空，则将该指针进栈，然后将指针指向该结点左子树根结点，继续遍历。 46 如果指向根结点指针非空，则将该指针进栈，然后将指针指向该结点左子树根结点，继续遍历。 如果指向根结点指针为空，则应退至上一层（即将栈顶存放的指针出栈）：  若从左子树返回，则应访问当前层（即栈顶指针所指的）根结点，然后将指针指向该结点的右子树根结点，继续遍历；  若从右子树返回，则表明当前层遍历结束，应继续退栈。从另一个角度看，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改指针。 当指针为空并且栈为空时，遍历结束。

(2)算法描述 if ( p!=NULL ) { // 如果 p 非空 } // else } // while } // InOrder void InOrder(BiTree root) /*采用二叉链表存储结构，Visit 是对元素操作的应用函数。 中序遍历二叉树T 的非递归算法，对每个元素调用函数 Visit*/ { InitStack (&S); // 使用栈 S 存放待访问的根结点 p = root; //令 p 指向二叉树根结点 while ( p!=NULL || ! IsEmpty (S) ) // 当 p 不为空，或者栈 S 不为空时 if ( p!=NULL ) { // 如果 p 非空 Push ( &S, p ) ; // 将 p 指针入栈 p = p->Lchild; // 指针指向左子树根结点，遍历左子树 }//if else { // 如果 p 为空 Pop ( &S, &p ) // 退栈，将上一层的根结点指针弹出 Visit (p->data); // 访问 p 指针指向的结点 p = p->Rchild; // 指针指向右子树根结点，遍历右子树 } // else } // while } // InOrder

树中空链域的个数为 2n0+n1，再由二叉树的性质3 (n0 = n2+1)，可知： 48 (3) 算法分析 InOrder 非递归算法的时间复杂度 假定二叉树 root 有 n 个结点，算法中对每个结点都要入栈和出栈一次。因此，入栈和出栈都要执行 n 次。此外，只有当 p 为空时，才对当前在栈顶的结点信息进行访问。 树中空链域的个数为 2n0+n1，再由二叉树的性质3 (n0 = n2+1)，可知： 2n0 + n1 = n0 + n0 + n1 = n0 + n1 + n2 + 1 = n + 1 所以，遍历每个结点的时间复杂度为 O(n)。

49 InOrder 非递归算法所需附加空间 算法所需附加空间为栈（用以存放待访问的根结点）的容量。栈的容量与树的深度有关，如果每个结点需要 1 个存储单位，则遍历深度为 k 的二叉树，栈需要 k 个存储单位，即所需要的空间为 O(k)。

50 3. 后序遍历二叉树的非递归算法 (1) 算法思想 在后序遍历中，当搜索指针指向某一结点时，不能马上进行访问，而先要遍历其左子树，所以要将此结点入栈保存。当遍历完它的左子树后，退栈再次得到该结点时，还不能进行访问，还需要遍历其右子树。所以，需要再次将此结点入栈保存。

为了区别同一结点的两次入栈，在此算法中，设计一个栈 S 存放 SElemType 类型的数据，其结构为： 51 为了区别同一结点的两次入栈，在此算法中，设计一个栈 S 存放 SElemType 类型的数据，其结构为： typedef struct SElemType // 顺序栈中数据的结构定义 { BiTNode *p; // 二叉树的结点指针 int tag; // 标志变量 // 当 tag = 0 时，表示该结点第一次入栈，暂不访问； // 当 tag = 1 时，表示该结点第二次入栈，可以访问。 } SElemType; 算法开始时，先将栈 S 初始化，然后令 p 指向二叉树的根结点，即 p = root。

如果指向根结点指针不为空，先将 tag 置零；再将 tag 和根结点一道送入栈中；然后将指针指向该结点的左子树根结点；继续遍历。 52 如果指向根结点指针为空，则应退至上一层，即将栈顶存放的数据项（SElemType类型，包括二叉树结点指针和标志变量）出栈：  若 tag 为 0，则改变 tag 值，将 tag 置 1；再把 tag 和弹出的结点重新装入栈中；然后将指针指向该结点的右子树根结点；继续遍历。  若 tag = 1，则访问弹出的结点，并且将弹出指针置为空。 直到栈为空并且指针为空时，遍历结束。

(2) 算法描述 void PostOrder (BiTree root) { SElemtype Data; 53 (2) 算法描述 void PostOrder (BiTree root) /*采用二叉链表存储结构，Visit 是对元素操作的应用函数。 后序遍历二叉树 T 的非递归算法，对每个元素调用函数Visit*/ { SElemtype Data; InitStack (S); Data.p = root; // 使用栈 S 存放待访问的根结点。令 Data.p 指向二叉树根结点 do { if ( Data.p ) { // 若 Data.p 非空 Data.tag = 0; // 将 Data.tag 置零 Push ( S, Data ); // 将 Data.tag 和 Data.p 一道送入栈 S Data.p = Data.p->lchild; // 将指针指向左子树根结点，遍历左子树 }

{ Pop ( S, Data ); // 将 Data.tag 和 Data.p 一道弹出 else // 如果 Data.p 为空 { Pop ( S, Data ); // 将 Data.tag 和 Data.p 一道弹出 54 if ( Data.tag = 0 ) // 如果标志变量 Data.tag 为零 { Data.tag = 1; // 将 Data.tag 置为 1 Push ( S, Data ) // 将 Data.tag 和 Data.p 一道送入栈 S 中 Data.p = Data.p->rchild; // 将指针指向右子树根结点，遍历右子树 } else { // 如果标志变量 Data.tag 为 1 Visit ( Data.p ); // 访问 Data.p 指向的结点 Data.p = NULL; // 将 Data.p 指针置空 } } while ( ! Data.p && StackEmpty (S) ); return OK; } // PostOrderTraverse

PostOrder 非递归算法的时间复杂度 55 (3) 算法分析 PostOrder 非递归算法的时间复杂度 假定二叉树 root 有 n 个结点，算法中对每个结点都要进行两次入栈和出栈。因此，入栈和出栈都要执行 2n 次，则入栈、出栈的时间复杂度为 O(n)。 此外，每当 Data.p 为空时，就弹出栈顶的数据项 Data，然后根据 Data.tag 的值是否为零，或访问刚弹出的结点，或使数据项重新进栈。重新入栈的时间已经算在入栈、出栈所需时间之内，访问结点的时间显然为 O(n)。所以，算法总的时间复杂度为 O(n)+O(n)，或者为 O(n)。

PostOrder 非递归算法所需附加空间 56 PostOrder 非递归算法所需附加空间 算法所需要的附加空间比前面两个算法多。由于 Data.tag 变量用 1 位二进制就可以表示，因此，所需要的空间仍然为 O(k)，其中 k 为二叉树的深度。

⑴从当前结点开始,进栈并走左子树,直到左子树为空 57 后序遍历方法二算法思想 ⑴从当前结点开始,进栈并走左子树,直到左子树为空 ⑵如果栈顶结点的右子树为空,或栈顶结点的右子树为刚访问过的结点,则退栈并访问，然后将当前结点指针置为空。 ⑶ 否则，走右子树。 直到栈为空并且指针为空时，遍历结束。

58 6.3.4 建立二叉树的算法 遍历二叉树是二叉树各种操作的基础，可以在遍历的过程中对结点进行各种操作，比如：对于一棵已知树可以求结点的双亲，求结点的孩子结点，判定结点所在的层次等；反之，给定一棵二叉树的遍历序列结点，可建立二叉树的存储结构。

例如，如果按照先序序列建立二叉树的二叉链表结构，对下图所示二叉树，可以按照“扩展先序遍历顺序”读入字符，即可以建立相应的二叉链表。 59 例如，如果按照先序序列建立二叉树的二叉链表结构，对下图所示二叉树，可以按照“扩展先序遍历顺序”读入字符，即可以建立相应的二叉链表。 A B C D F E G A B C ．．D E ．G ．．F．．．

void CreateBiTree ( BiTree *bt) 60 void CreateBiTree ( BiTree *bt) /*按先序次序输入二叉树中结点的值（一个字符）， 圆点字符表示空树。构造二叉链表表示的二叉树 T。*/ { scanf (&ch); // 输入字符 if ( ch = =  ． ) *bt = NULL; // 若是．字符则令指针为空 else { if ( ! ( *bt = ( BiTNode * ) malloc ( sizeof ( BiTNode ) ) ) ) return; (*bt)->data = ch; // 生成根结点 CreateBiTree ( &((*bt)->LChild ); // 构造左子树 CreateBiTree ( &((*bt)->RChild ); // 构造右子树 } LC } // CreateBiTree

6.4 二叉线索树 二叉线索树的引出 二叉线索树的定义 二叉线索树的存储结构 二叉线索树的操作 61 6.4 二叉线索树 先序、中序和后序遍历二叉树的结点比处理单链表中的一个结点要复杂。对单链表，我们曾经定义了求前驱和求后继的运算。那么在树中可以吗？ 二叉线索树的引出 二叉线索树的定义 二叉线索树的存储结构 二叉线索树的操作

6.4.1 线索二叉树的引出 (1) 先序排序如何实现求前驱和求后继运算？ 62 6.4.1 线索二叉树的引出 (1) 先序排序如何实现求前驱和求后继运算？ A B D F E G 后继 后继 对于求后继运算，如果所考虑的结点是非叶子结点，那么该结点的左孩子就是它的后继结点。 对于求前驱运算，在先序排序下，不论何种情况都需要遍历二叉树。 如果所考虑的结点是叶子结点，那么要找到该结点的后继结点，就必须遍历二叉树。 如果结点的左孩子不存在，那么该结点的右孩子就是它的后继结点。

(2) 后序排序如何实现求前驱和求后继运算？ 63 (2) 后序排序如何实现求前驱和求后继运算？ A B D F E G 前驱 前驱 对于求后继运算，在后序排序下，不论何种情况都需要遍历二叉树。 如果所考虑的结点是叶子结点，那么要找到该结点的前驱结点，就必须遍历二叉树。 对于求前驱运算，如果所考虑的结点是非叶子结点，那么该结点的右孩子就是它的前驱结点。 如果该结点的右孩子不存在，那么该结点的左孩子就是它的前驱结点。

(3) 中序排序如何实现求前驱和求后继运算？ 64 (3) 中序排序如何实现求前驱和求后继运算？ 对于求前驱运算，若所考虑的结点有左孩子，那么就要从该左孩子开始，顺着该左孩子的右孩子链域找下去，一直找到右孩子的链域是空为止，最后这个结点就是所考虑结点的前驱结点；若所考虑的结点无左孩子，那么就要遍历二叉树。 对于求后继运算，若所考虑的结点有右孩子，那么就要从该右孩子开始，顺着该右孩子的左孩子链域找下去，一直找到左孩子的链域是空为止，最后这个结点就是所考虑结点的后继结点；若所考虑的结点无右孩子，那么就要遍历二叉树。 N R1 R2 Rk N R1 R2 Rk 前驱 后继

(4) 如何保存在遍历二叉树的动态过程中得到的某一结点的前驱和后继信息？ 方法有两个。 65 (4) 如何保存在遍历二叉树的动态过程中得到的某一结点的前驱和后继信息？ 方法有两个。 方法一：为了方便地实现求结点的前驱和求后继运算，可以在原有二叉链表的结点结构中，再增加两个链域：plink 和 nlink，分别指示结点在依任一次序遍历时得到的前驱和后继信息。 方法二： 在有 n 个结点的二叉树中，有 n+1 个空链域。由此，可以利用这些空链域来存放结点的前驱和后继的信息。

为了避免混淆，需改变二叉链表的结点结构，增加两个标志域：ltag 和 rtag。 66 试做如下规定：若结点有左子树，则其 lchild 域指示其左孩子，否则令 lchild 域指示其前驱；若结点有右子树，则其 rchild 域指示其右孩子，否则令 rchild 域指示其后继。 为了避免混淆，需改变二叉链表的结点结构，增加两个标志域：ltag 和 rtag。

6.4.2 二叉线索树的定义 这种存储方式利用了二叉链表中原有的空链域，提高了结构的存储密度，是一种实用的做法。 左孩子或前驱域 数据域 6.4.2 二叉线索树的定义 67 左孩子或前驱域 数据域 右孩子或后继域 lchild ltag data rtag rchild 左标志域 右标志域 lchild 域指示结点的左孩子 ltag = 1 lchild 域指示结点的前驱 其中： rchild 域指示结点的右孩子 rtag = 1 rchild 域指示结点的后继 这种存储方式利用了二叉链表中原有的空链域，提高了结构的存储密度，是一种实用的做法。

① 线索链表：以这种结点结构构成的二叉链表作为二叉树的存储结构称之。 68 相关概念如下： ① 线索链表：以这种结点结构构成的二叉链表作为二叉树的存储结构称之。 ② 线索：在线索链表中指向结点前驱和后继的指针称之。 ③ 线索二叉树：加上线索的二叉树称之。 ④ 线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程称之。

通常，线索二叉树指中序线索二叉树，简称线索树。 69 6.4.3 二叉树线索的存储结构 typedef struct BiThrNode { DataType data; // 数据域 struct BiThrNode *lchild, *rchild; // 左右孩子指针 PointerTag ltag, rtag; // 左右标志 } BiThrNode, *BiThrTree; // 线索二叉树的类型名 通常，线索二叉树指中序线索二叉树，简称线索树。

 令二叉树中序序列第一个结点的 lchild 域指针和最后一个结点的 rchild 域指针均指向头结点。 70 为了方便起见，仿照线性表的存储结构：  在二叉树线索链表上也添加一个头结点，并令其 lchild 域指针指向二叉树的根结点，其 rchild 域指针指向中序遍历二叉树时访问的最后一个结点；  令二叉树中序序列第一个结点的 lchild 域指针和最后一个结点的 rchild 域指针均指向头结点。

6.4.4 二叉线索树的操作 1. 在二叉线索树中求结点的中序前驱 (1) 算法思想 6.4.4 二叉线索树的操作 71 1. 在二叉线索树中求结点的中序前驱 (1) 算法思想 判断给定结点 t 的左指针 lchild 是否指向头结点 Thrt。若是，则返回 ；若否，则继续下面的操作。 判断给定结点 t 的左标志 ltag 是否为 1。若为 1，则t->LChild指向t的前驱。当t->LChild=0时，则说明 p 指向结点 t 的左孩子(p=t->LChild)，这时就需要顺着 p 所指结点的右链域寻找，直到结点右标志 rtag 为 1；若为 1，则说明 p 指向结点 t 的线索，即 p 所指向的结点就是结点 t 的前驱。

(2) 算法实现 int InPre( BiThrTree t, BiThrTree p ) { 72 (2) 算法实现 int InPre( BiThrTree t, BiThrTree p ) // t 指向中序线索树中某一结点，p 返回此结点的前驱； 并返回 OK { p = t->lchild; // 将 t 的 lchild 域的值赋给 p if ( p == Thrt ) return ERROR; // 若 p 指向头结点，则出错 if ( t->ltag == 0) // 若 t 的左标志为 0 while ( p->rtag = =0) { p = p->rchild; } // 顺着 t 的左孩子的右链域寻找，直到结点右标志是 1 为止 return OK; } // InPre

如果 t 所指向结点的左孩子有 k 层右孩子，则需要进行 k+1 次比较，因此 Inpre 算法的时间复杂度为 O(k)。 73 (3) 算法分析 如果 t 所指向结点的左孩子有 k 层右孩子，则需要进行 k+1 次比较，因此 Inpre 算法的时间复杂度为 O(k)。

判断给定结点 t 的右指针 rchild 是否指向头结点 Thrt。若是，则返回 ERROR；若否，则继续。 74 2. 在二叉线索树中求结点的中序后继 (1) 算法思想 判断给定结点 t 的右指针 rchild 是否指向头结点 Thrt。若是，则返回 ERROR；若否，则继续。 判断给定结点 t 的右标志 rtag 是否为 0。若为 0，则用 p 指向结点 t 的右孩子，这时就需要顺着 p 所指结点的左链域寻找，直到结点左标志 ltag 为 1；若为 1，则说明 p 指向结点 t 的线索，即 p 所指向的结点就是结点 t 的后继。

(2) 算法实现 int InNext ( BiThrTree t, BiThrTree p ) { 75 (2) 算法实现 int InNext ( BiThrTree t, BiThrTree p ) // t 指向中序线索树中某一结点，p 返回此结点的后继； 并返回 OK { p = t->rchild; // 将 t 的 rchild 域值赋给 p if ( p = =Thrt ) return ERROR; // 若 p 指向头结点，则出错 if ( t->rtag = 0 ) // 若 t 的右标志为 0 while ( p->ltag = =0) { p = p->lchild; } // 顺着 t 的右孩子的左链域寻找，直到结点左标志是 1 为止 return OK; } // InNext

如果 t 所指向结点的右孩子有 k 层左孩子，则需要进行 k+1 次比较，因此 Next_Thr 算法的时间复杂度为 O(k)。 76 (3) 算法分析 如果 t 所指向结点的右孩子有 k 层左孩子，则需要进行 k+1 次比较，因此 Next_Thr 算法的时间复杂度为 O(k)。

下面给出将值为 e 的新结点 r 插入到中序线索树中，作为结点 p 的右孩子。 77 3. 在二叉线索树中插入结点 下面给出将值为 e 的新结点 r 插入到中序线索树中，作为结点 p 的右孩子。 (1) 算法思想 建立新结点 r，使其数据域的值为 e； 如果结点 p 无右孩子，则做：  将新结点 r 插入线索树中作为结点 p 的右孩子。  结点 p 的后继是新结点 r的后继，r的前驱是 p；且r.ltag = 1，r.rtag = 1。  修改 p.rchild,使其指向新结点 r,且 t.rtag = 0。

 将新结点 r 插入到线索树中作为结点 p 的右孩子； 78 如果 p 有右孩子，则做：  将新结点 r 插入到线索树中作为结点 p 的右孩子；  p 的右子树在新结点 r 插入之后，应该成为新结点 r 的右子树，这样就有 r.rtag = 0；新结点 r 的前驱是 p；且 r.ltag = 1；  修改 p.rchild，使其指向新结点 r，且 p.rtag = 0。  求出新结点 r 的后继，并修改 r 的后继的 lchild 域，使其指向新结点 r，即这个结点的前驱应该为 q。

(2) 算法描述 int InsNode(BiThrTree Thrt, BiThrTree p, BiThrTree r) { 79 int InsNode(BiThrTree Thrt, BiThrTree p, BiThrTree r) // 将新结点r插入到中序线索树中作为结点 p的右孩子，并返回 OK { if ( ! ( r = ( BiThrTree ) malloc ( sizeof ( BiThrNode ) ) ) ) exit ( OVERFLOW ); r->data = e; r->rchild = p->rchild; r->rtag = p->rtag; r->lchild = p; r->ltag = 1; p->rchild = r; p->rtag = 0; if ( r->rtag = 0 ) { InNext ( &r, &s ); s->lchild = r; } // 若 r 的右标志为 0，则寻找 r 的后继 s，并将 r 作为 s 的前驱 return OK } //InsNode

同理，可以编写出将值为 e 的新结点 r 插入到中序线索树中，作为结点 p 的左孩子。 80 (3) 算法分析 InsNode 算法的执行时间主要取决于 InNext (r, s) 算法（求结点 r 的后继 s）。如果 r 的右孩子有 k 层左孩子，则寻找 r 的后继 s 需要进行 k+1 次比较，因此 Next_Thr 算法时间复杂度为 O(k)。故 InNext 算法的时间复杂度也为 O(k)。 同理，可以编写出将值为 e 的新结点 r 插入到中序线索树中，作为结点 p 的左孩子。

① 令 p 指向根结点，且当二叉树为非空树或遍历未结束时，继续做如下操作； 81 4. 遍历二叉线索树 (1) 算法思想 ① 令 p 指向根结点，且当二叉树为非空树或遍历未结束时，继续做如下操作； ② 顺着 p 的左链域寻找，直到结点的左标志域 ltag = 1 时为止，即结点的左链域 lchild 为空； ③ 访问其左链域 lchild 为空的结点；

④ 当 p 的右标志域 rtag = 1，并且右链域 rchild 不指向头结点时（即 p 的 rchild 指向后继），则访问后继； 82 ④ 当 p 的右标志域 rtag = 1，并且右链域 rchild 不指向头结点时（即 p 的 rchild 指向后继），则访问后继； ⑤ 当 p 的右标志域 rtag = 0（即 p 的 rchild 指向右孩子），或右链域 rchild 指向头结点时，则令 p = p->rchild ⑥ 当 p 指向非空树或遍历未结束时，则重复执行上述步骤 ② ~ ⑤。

(2) 算法描述 void TInOrder ( BiThrTree Thrt) { /*Thrt 指向中序线索树的头结点， 头结点的左链域 lchild 指向根结点，遍历中序线索树 T 的非递归算法， 对每个数据元素调用函数 Visit 。*/ { p = Thrt->lchild; // p 指向根结点 while ( p != Thrt ) // 当空树或遍历结束时，p = = Thrt { while ( p->ltag = = 0 ) p = p->lchild; // 顺着 p 的左链域寻找，直到结点左标志是 1 时为止 if ( ! Visit ( p->data ) ) return ERROR; // 访问其左子树为空的结点 while ( p->rtag = = 1 && p->rchild ! = Thrt ) { // 当 p 右标志为 1 且右链域 rchild 不为头结点时， 则访问后继结点 p = p->rchild; Visit ( p->data ); } // while } // InOrderTraverse

(2) 算法描述 void TInOrder ( BiThrTree Thrt) { 84 (2) 算法描述 void TInOrder ( BiThrTree Thrt) /*Thrt 指向中序线索树的头结点， 头结点的左链域 lchild 指向根结点， 遍历中序线索树 T 的非递归算法， 对每个数据元素调用函数 Visit 。*/ { p = Thrt->lchild; // p 指向根结点 while ( p != Thrt ) // 当空树或遍历结束时，p = = Thrt { while ( p->ltag = = 0 ) p = p->lchild; // 顺着 p 的左链域寻找，直到结点左标志是 1 时为止 if ( ! Visit ( p->data ) ) return ERROR; // 访问其左子树为空的结点 while ( p->rtag = = 1 && p->rchild ! = Thrt ) { // 当 p 右标志为 1 且右链域 rchild 不为头结点时， 则访问后继结点 p = p->rchild; Visit ( p->data ); }

TInOrder 算法的时间复杂度为 O(n)。 85 (3) 算法分析 TInOrder 算法的时间复杂度为 O(n)。 在中序线索树上遍历，虽然时间复杂度也为 O(n)，但是其常数因子要比在中序二叉树上遍历小，并且不需要设立栈。

先线索化以 root 为根的二叉树， 后线索化头结点。 86 5. 二叉树的线索化 (1) 算法思想 由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。 为了记下遍历过程中访问结点的先后关系，需要附设指针 pre 始终指向刚刚访问过的结点，若指针 p 指向当前访问的结点，则 pre 指向它的前驱。 先线索化以 root 为根的二叉树， 后线索化头结点。

87 6.5 树和森林与二叉树的转换 树与二叉树的转换 森林与二叉树的转换 树和森林的遍历

88 6.5.1 树与二叉树的转换 由于树和二叉树都可以使用二叉链表作为存储结构，因此可以用二叉链表作为媒介导出树与二叉树之间的一个对应关系。也就是说，给定一棵树，可以找到惟一的一棵二叉树与之对应，从物理结构来看，它们的二叉链表是相同的，只是解释不同而已。

除线：对任何结点，除了其最左边的孩子之外，去掉该结点与其余孩子的各枝； 89 1. 树转换为二叉树 树转换为二叉树的可以按照如下步骤进行： 加线：在各兄弟结点之间加一连线； 除线：对任何结点，除了其最左边的孩子之外，去掉该结点与其余孩子的各枝； 旋转：将添加的水平连线和原有的连线，以树的根结点为轴心，按顺时针方向旋转 45°。

除线：去除原二叉树中所有双亲结点与右孩子的连线； 90 2. 二叉树还原为树 二叉树还原为树可以按照如下步骤进行： 加线：若 p 结点是双亲的左孩子，则将 p 结点的右孩子，右孩子的右孩子，……，沿着右分支搜索到的所有右孩子，都分别与 p 结点的双亲用线连起来； 除线：去除原二叉树中所有双亲结点与右孩子的连线； 旋转：以树的根结点为轴心，按逆时针方向旋转 45°。

91 6.5.2 森林与二叉树的转换 从树与二叉树的转换中可知，转换之后的二叉树的根结点没有右孩子，如果把森林中的第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可以导出森林和二叉树的对应关系。

连线：将各棵转换后的二叉树的根结点相连； 92 1. 森林转换为二叉树 森林转换为二叉树可以按照如下步骤进行： 转换：将森林中的每一棵树转换成二叉树； 连线：将各棵转换后的二叉树的根结点相连； 旋转：将添加的水平连线和原有的连线以第一棵树根结点为轴心，按顺时针方向粗略地旋转 45°。

经过这种方法转换所对应的二叉树是惟一的，且其第一棵树的子树森林转换成二叉树的左子树，剩余树的森林转换成二叉树的右子树。 A 93 A B D C E F G H I J A B E C D F G H I J 经过这种方法转换所对应的二叉树是惟一的，且其第一棵树的子树森林转换成二叉树的左子树，剩余树的森林转换成二叉树的右子树。 A B C D E F G H I J 连 线 转 换 旋 转

抹线：抹掉二叉树根结点右链上所有结点上的连线，分成若干个以右链上结点为根结点的子二叉树； 94 2. 二叉树还原为森林 二叉树还原为森林可以按照如下步骤进行： 抹线：抹掉二叉树根结点右链上所有结点上的连线，分成若干个以右链上结点为根结点的子二叉树； 转换：将分好的子二叉树转换成树； 调整：将转换好的树的根结点排列成一排。

6.5.3 树和森林的遍历 1. 树的遍历 先根遍历：若树非空，则先访问树的根结点，然后依次先根遍历根的每棵子树。 95 6.5.3 树和森林的遍历 1. 树的遍历 先根遍历：若树非空，则先访问树的根结点，然后依次先根遍历根的每棵子树。 后根遍历：若树非空，则先依次后根遍历根的每棵子树，然后访问树的根结点。 层次遍历：若树非空，则从树的根结点起按层从左到右依次访问各结点。

先序遍历：若森林非空，则：访问森林中第一棵树根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除去第一棵树后剩余的树构成的森林。 96 2. 森林的遍历 先序遍历：若森林非空，则：访问森林中第一棵树根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除去第一棵树后剩余的树构成的森林。 中序遍历：若森林非空，则：中序遍历第一棵树中根结点的子树森林；访问森林中第一棵树根结点；中序遍历除去第一棵树后剩余的树构成的森林。 层次遍历：若森林非空，则：对第一棵树从根结点起按层从左到右依次访问结点；按层访问森林中除第一棵树外剩余的树构成的森林。

森林的先序序列对应转换之后二叉树的先序序列。 97 对应的二叉树 A B E C D F G H I J 森林 A B D C E F G H I J 森林的先序序列对应转换之后二叉树的先序序列。 先序遍历森林 A B C D E F G H I J 先序遍历二叉树 A B C D E F G H I J

98 6.6 赫夫曼树及其应用 赫夫曼 (Huffman) 树，又称最优二叉树，它是 n 个带权叶子结点构成的所有二叉树中，带权路径长度最短的二叉树，有着广泛的应用。因为构造这种树的算法最早由赫夫曼 (Huffman) 于 1952 年提出的，所以被称为赫夫曼树。

99 基本概念 赫夫曼算法 赫夫曼编码 赫夫曼树和赫夫曼编码的存储表示 赫夫曼编码的算法 示例

6.6.1 基本概念 在赫夫曼树及其应用中经常会用到一些基本术语。例如： 路径 路径长度 树的路径长度 结点的带权路径长度 树的带权路径长度 100 6.6.1 基本概念 在赫夫曼树及其应用中经常会用到一些基本术语。例如： 路径 路径长度 树的路径长度 结点的带权路径长度 树的带权路径长度 赫夫曼树

例如：结点 a 的带权路径长度为路径长度 3×结点权值 7 = 21 101 a 7 例如：结点 a 的带权路径长度为路径长度 3×结点权值 7 = 21 c d a b 7 5 4 2 树的带权路径长度：树中所有叶子结点的带权路径长度之和称为树的带权路径长度。通常记作 结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积称为结点的带权路径长度。 树的路径长度：从树根到每一个结点的路径长度之和称为树的路径长度。完全二叉树就是这种路径长度最短的二叉树。 路径：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径。 例如：此树的带权路径长度为 2×4＋3×7＋3×5＋1×2 = 46 路径长度：路径上的分支数目称为路径长度

102 赫夫曼树的定义： 假设有 n 个权值 { w1, w2, … , wn }，构造一棵有 n 个叶子结点的二叉树，每个叶子结点带权为 wi ，则其中带权路径长度 WPL 最小的二叉树称为最优二叉树或赫夫曼树。

103 下面所示的 3 棵二叉树都含有 4 个叶子结点 A、B、C、D，分别带权 7、5、2、4。 a b c d 7 5 2 4 c d a b 7 5 4 2 a b c d 7 5 2 4 在 3 棵二叉树中，以图(c) 所示的二叉树带权路径长度最小。可以验证，它恰为赫夫曼树，即其带权路径长度在所有带权为 7、5、2、4 的 4 个叶子结点的二叉树中居最小。 (a) (b) (c) 图 (a) 的带权路径长度为 WPL = 7×2＋5×2＋2×2＋4×2 = 36 图 (b) 的带权路径长度为 WPL = 7×3＋5×3＋2×1＋4×2 = 46 图 (c) 的带权路径长度为 WPL = 7×1＋5×2＋2×3＋4×3 = 35

6.6.2 赫夫曼算法 1. 赫夫曼算法思想 构造赫夫曼树的算法称之为赫夫曼算法，其具体步骤如下： 6.6.2 赫夫曼算法 104 1. 赫夫曼算法思想 构造赫夫曼树的算法称之为赫夫曼算法，其具体步骤如下： ① 根据给定的 n 个权值 { w1, w2, … , wn } ，构成 n 棵二叉树的集合 F = { T1, T2, … , Tn }，其中每棵二叉树 Ti 中只有一个带权 wi 的根结点，其左子树和右子树均为空。

③ 在 F 中删除在②中选中的那两棵根结点权值最小的二叉树，同时将新得到的二叉树加入 F 中。 105 ② 在 F 中选取两棵根结点的权值最小的树作为左子树和右子树，构造一棵新的二叉树，并且置新的二叉树的根结点的权值为其左子树和右子树上根结点的权值之和。 ③ 在 F 中删除在②中选中的那两棵根结点权值最小的二叉树，同时将新得到的二叉树加入 F 中。 ④ 重复②和③ ，直到 F 中只含一棵树为止。这棵树便是赫夫曼树。

6.5.2 哈夫曼树的构造 举例：{5，11，26，18，34，15，6}构成一棵哈夫曼树 ^ 125 77 48 22 11 33 5 6 6.5.2 哈夫曼树的构造 举例：{5，11，26，18，34，15，6}构成一棵哈夫曼树 ^ 125 77 48 22 11 33 5 6 11 15 18 26 34

6.5.2 哈夫曼树的构造 整理上面的哈夫曼树如图： ^ 6 5 11 15 18 26 34 22 33 48 77 125

哈夫曼树的构造算法 哈夫曼树的类型定义：用静态三叉链表实现哈夫曼树类型定义如下： #define N 20 /*叶子结点最大值*/ #define M 2*N-1 /*所有结点的最大值*/ typedef struct { int weight; /*结点的权值*/ int parent; /*双亲的下标*/ int Lchild; /*左孩子结点的下标*/ int Rchild; /*右孩子结点的下标*/ }HTNode,HuffmanTree[M+1]; ^

哈夫曼树的构造 哈夫曼树构造算法分为两步： 第一步对初始状态的设置。在该步骤中，让第1到n的单位的权值为所給权值，从第n+1到第m=2n-1的单元的权值都为0.让所有结点的双亲和孩子值都为0.即创建n个子树，每棵树只有根结点。 第二步开始实现构造过程，即选取权值最小的两棵树根（双亲为0）进行合并，构造一棵新的树（产生新的结点），该树的根结点权值为所选的两棵树的权值之和，且左右孩子分别为上述所选的两棵树，即所选出的两棵树的双亲为新构造的结点。构造出来的新结点依次存放在第n+1到第m的单元上。 ^

哈夫曼树的构造 ^ void CrtHuffmanTree(HuffmanTree ht, int w [ ], int n) { // 第一步：对初始状态的设置。 for(i=1;i<=n;i++) ht[i]={w[i],0,0,0} ; m=2*n-1; for(i=n+1;i<=m;i++) ht[i]={0,0,0,0}; //第二步:创建非叶子结点，开始实现构造过程. for(i=n+1;i<=m;i++) { /*在ht[1]~ht[i-1]范围内选择两个parents为0的且weight最小的结点，分别用s1和s2返回序号*/ select(ht ,i-1 , &s1 , &s2); //构造新结点ht[i] ht[i].weight=ht[s1.weight+ht[s2].weight; ht[s1].parent=i ; ht[s2].parent= i ; ht[i].Lchild=s1 ; ht[i].Rchild=s2; } ^

哈夫曼树的构造 例如：一组权值为{5，7，3，2，8}，构造哈夫曼树的初始状态和下一个状态分别为： 初始状态 下一状态 ^ Weight Parents Lchild Rchild 1 2 3 4 5 6 7 8 9 5 0 0 0 7 0 0 0 3 0 0 0 2 0 0 0 8 0 0 0 0 0 0 0 Weight Parents Lchild Rchild 1 2 3 4 5 6 7 8 9 5 0 0 0 7 0 0 0 3 6 0 0 2 6 0 0 8 0 0 0 5 0 4 3 0 0 0 0

① 在选取两棵根结点权值最小的二叉树时，如果出现权值相同的情况，可以在相同权值的二叉树中选取一棵； 2. 赫夫曼算法说明 112 ① 在选取两棵根结点权值最小的二叉树时，如果出现权值相同的情况，可以在相同权值的二叉树中选取一棵； ② 当两棵根结点的权值最小的二叉树组成新的二叉树的左子树和右子树时，谁左谁右没有规定； ③ 在赫夫曼树中，权值越大的叶子结点离根越近，这也是 WPL 最小的实际根据和赫夫曼树的应用依据； ④ 在赫夫曼树中没有度为 1 的结点，根据二叉树性质 n0 = n2 + 1，可以推得 n 个叶子结点的赫夫曼树共有 2n-1 个结点。

6.6.3 赫夫曼编码 赫夫曼树的应用很广，赫夫曼编码就是其在电报通信中的最早应用之一，现在扩展到其他的计算机及通信领域。 113 6.6.3 赫夫曼编码 赫夫曼树的应用很广，赫夫曼编码就是其在电报通信中的最早应用之一，现在扩展到其他的计算机及通信领域。 在电报的传送过程中，传送的电文以二进制代码作为电报编码。即电报的发出方需要将电文转换成二进制编码发出，而接收方又将接收到一串二进制码并按编码原则翻译成原电文。

当传送电文时，希望总长尽可能地短，若对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。 1. 前缀编码 114 当传送电文时，希望总长尽可能地短，若对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。 若设计 A、B、C、D 编码分别为 0、00、1、01，则上述七字符电文可转换总长为 9 的字符串 000011010。但这中电文无法翻译，如传送过去的字符串中前 4 个字符子串 0000 就有多种译法，或是 AAAA，或是 ABA，也可是 BB  等。这样就要求设计前缀编码。 例如，假设需要传送的电文为 ABACCDA，它只含有 4 种字符，每种字符只需要二位的字符串作为定长编码即可发送电文和接收电文。假设 A、B、C、D 的编码分别为 00、01、10、11，则上述 7 个字符的电文便为 00010010101100，总长是 14 位，对方接收时，按照二位一组进行译码即可。 若要设计长度不等的编码，则必须是任一个字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。

可以证明，如此得到的编码必为二进制前缀编码。 115 2. 赫夫曼编码 A B C D ① 利用二叉树设计二进制前缀编码 假设有一棵二叉树。 1 1 二叉树 4 个叶子结点分别表示 A、B、C、D 四个字符，且约定左分支表示字符 0，右分支表示字符 1，则可从根到叶子结点的路径上分支字符组成的字符串作为该叶子结点的字符编码。 1 编码 A (0) B (10) C (110) D (111) 可以证明，如此得到的编码必为二进制前缀编码。

② 利用赫夫曼树设计电文总长最短二进制前缀编码 116 ② 利用赫夫曼树设计电文总长最短二进制前缀编码 假设每种字符在电文中出现的次数为 wi ，其编码长度为 li ，电文中只有 n 种字符，则电文总长为 对应到二叉树上，若置 wi 为叶子结点的权， li 恰为从根到叶子的路径长度，则二叉树上带权路径长度为 这正好是对应赫夫曼树的 WPL。故可利用赫夫曼树原理设计二进制前缀编码，并使译得电文总长最短。

当然，也可以在赫夫曼树中规定左子树分支表示 1，右子树分支表示 0 ，得到的二进制前缀编码虽然不一样，但是使用效率一样。 117 将可能出现的字符作为叶子结点，在电文中字符出现的频率作为各个对应叶子结点的权值，设计一棵赫夫曼树，树中的左子树分支表示二进制数 0，右子树分支表示二进制数 1 ，则可以将从根结点到叶子结点的路径上分支字符组成的字符串作为叶子结点字符的编码，即每一个字符的二进制前缀编码。这种二进制前缀编码称为赫夫曼编码。 当然，也可以在赫夫曼树中规定左子树分支表示 1，右子树分支表示 0 ，得到的二进制前缀编码虽然不一样，但是使用效率一样。

118 6.6.6 示例 假设用于通信的电文由 8 个字母组成，字母在电文中出现的概率分别为 0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，试设计赫夫曼编码。 1. 分析 设权 w = ( 5, 29, 7, 8, 14, 23, 3, 11 )，n = 8，则 m = 2n-1=15，按赫夫曼算法可构造一棵赫夫曼树，且从叶子结点到根结点逆向求出每个字符赫夫曼编码。

119 权 w = ( 5, 29, 7, 8, 14, 23, 3, 11 )，n = 8 的赫夫曼树 100 42 58 23 19 29 29 11 8 14 15 5 3 7 8

120 HC 的形成过程 5 3 11 23 7 8 14 29 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 0 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 0 4 1 1 1 1 1 1 1 1 1 1 5 1 1 0 6 0 0 7 0 1 1 1 8 0 1 0

6.6 二叉排序树 二叉排序树又称为二叉查找树，他是一种特殊的二叉树。 其定义为：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： 6.6 二叉排序树 ^ 二叉排序树又称为二叉查找树，他是一种特殊的二叉树。 其定义为：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： 1）若它的左子树非空，则左子树上所有结点的值均小于它的根结点的值； 2）若它的右子树非空，则右子树上所有结点的值均大于它的根结点的值； 3）它的左右子树也分别为二叉排序树。

请大家观察下面的两棵树，判断是否为二叉排序树？ ^ 请大家观察下面的两棵树，判断是否为二叉排序树？ D B Z A C X Y D A Y C B X Z

二叉排序树的插入与创建 二叉排序树的插入：已知一个数据域data的结点s，欲将其插入到二叉排序树中，使得插入后的树仍然是一个二叉排序树。 算法思想： 1）若二叉排序树为空树，则s作为二叉排序树的根； 2）若二叉排序树非空，则将s.data的关键值与二叉排序树的根结点的数据域的关键值进行比较： a)如果s.data的关键值等于根结点的数据域的关键值，则停止插入； b)如果s.data的关键值小于根结点数据域的关键值，则将s插入到根结点的左子树； c)如果 s.data的关键值大于根结点数据域的关键值，则将s插入到根结点的右子树；

二叉排序树的插入与创建 如果关键字的输入顺序为45，24，53，12，28，90，则按照上述的算法生成的二叉排序树为： 容易发现，对一棵二叉排序树执行中序遍历，其结果就是按照从小到大排序的关键值序列.

KeyType key ; //存放数据的关键字 struct node *Lchild ; //左孩子指针 二叉排序树结点结构 typedef struct { KeyType key; OtherInfo other; //除却关键字外的其他信息 }DataType; typedef struct node DataType data; //数据域 struct node *Lchild ,*Rchild; //指针域 }BSTNode , *BSTree; typedef struct node { KeyType key ; //存放数据的关键字 struct node *Lchild ; //左孩子指针 struct node *Rchild ; //右孩子指针 }BSTNode , *BSTree ;

void InsertBST（BSTree *bst , DataType e) { 二叉排序树插入算法描述： void InsertBST（BSTree *bst , DataType e) /*若在二叉排序树bst中不存在关键字等于key的元素，插入该元素*/ { else if(key<(*bst)->key) InsertBST(&(*(bst)->Lchild),key); else if(key>(*bst)->key) InsertBST(&(*(bst)->Rchild),key); void InsertBST（BSTree *bst , DataType e) /*若在二叉排序树bst中不存在关键字等于key的元素，插入该元素*/ { BSTNode *s; if(*bst==NULL) { s=(BSTNode*)malloc(sizeof(BSTNode)); s->key=key; s->Lchild=NULL; s->Rchild=NULL; *bst=s; } void InsertBST（BSTree *bst , DataType e) /*若在二叉排序树bst中不存在关键字等于key的元素，插入该元素*/ { else if(key<(*bst)->key) InsertBST(&(*(bst)->Lchild),key);

void CreateBST（BSTree *bst) { KeyType key; *bst=NULL; 键盘输入元素值key； 二叉排序树创建算法描述： void CreateBST（BSTree *bst) /*从键盘输入元素的值，创建相应的二叉排序树*/ { KeyType key; *bst=NULL; 键盘输入元素值key； while（当key值满足条件） { InsertBST(bst , key); //插入 键盘输入元素值key; } 练习： 设关键字的输入顺序为：12，24，28，53，90，45，画出所生成的二叉排序树。 void CreateBST（BSTree *bst) /*从键盘输入元素的值，创建相应的二叉排序树*/ { KeyType key; *bst=NULL; 键盘输入元素值key； while（当key值满足条件） { InsertBST(bst , key); //插入 键盘输入元素值key; }

首先将待查关键字与根结点关键字t进行比较，如果： 1）key=t: 则返回根结点地址； 2）key<t: 则进一步查找左子树； 二叉排序树查找 算法思想： 首先将待查关键字与根结点关键字t进行比较，如果： 1）key=t: 则返回根结点地址； 2）key<t: 则进一步查找左子树； 3） key>t: 则进一步查找右子树；

算法实现（递归） BSTree SearchBST(BSTree bst , KeyType key) { if(!bst) return NULL; else if(bst->key==t)return bst; //如果查找成功，则返回 else if(bst->key>key ) return SearchBST(bst->Lchild , key); return SearchBST(bst->Rchild , key); }

二叉排序树的删除 从二叉排序树中删除一个结点，要保证删除后的二叉树还是一棵二叉排序树。 算法思想：首先查找要删除结点，如果查找失败，则不作任何删除操作，否则，假设要删除的结点为p，其双亲结点为f，并假设p是f的左孩子（右孩子情况类似），则删除过程分为三种情况讨论： （1）若p为叶子结点，则直接删除该结点，其双亲的左孩子为空： f->Lchild=NULL;free(p); （2）若p为单分支结点，即p只有左子树，或者只有右子树，则可将p的左子树或者右子树直接改为其双亲结点f的左子树： f->Lchild=p->Lchild;(或者 f->Lchild=p->Rchild;) free(p);

二叉排序树的删除 （3）若p为双分支结点，则有两种处理方法： 方法1：找到p结点在中序遍历序列中的直接前驱s，将p的左子树改为f的左子树，将p的右子树改为s的右子树： f->Lchild=p->Lchild; s->Rchild=p->Rchild;free(p); 方法2：找到p结点在中序遍历序列中的直接前驱s，然后用s结点代替p结点的值，再将s结点删除，原s结点的左子树改为其双亲结点（假设为q）的右子树： p->key=s->key ; q->Rchild=s->Lchild; free(s); 上述的两种方法中还可以将寻找p结点的中序遍历前驱改成寻找中序遍历后继，请同学们考虑一下。

二叉排序树的删除算法描述 BSTNode * DelBST(BSTree t , KeyType k) {BSTNode *p , *q , *f , *s ; /*查找关键字为k的待删除结点位置*/ p=t; f=NULL ; //从根结点开始查找 while(p) { if(p->key==k)break ; f=p; //记录双亲结点位置 if(p->key>k)p=p->Lchild; else p=p->Rchild ; } if(p==NULL)return t ; //查找不成功，不作任何操作，直接返回 //如果查找成功，则查看p的情况 if(p->Lchild==p->Rchild==NULL) //p是叶子结点 { if(f==NULL){t=f ; return t;} else if(p==f->Lchild){f->Lchild==NULL; free(p); else if(p==f->Rchild){f->Rchild==NULL;free(p);

二叉排序树的删除算法描述 else { //如果p是单分支结点 if(p->Lchild==NULL) //p无左子树 { if(f==NULL)t=p->Rchild; else if (f->Lchild==p) //若p是f的左孩子 f->Lchild=p->Rchild; //p的右子树作为f的左子树 else f->Rchild=p->Rchild ; //p的右子树作为f的右子树 free(p); } if(p->Rchild==NULL) //p无右子树 { if(f==NULL)t=p->Lchild; else if(f->Lchild==p) f->Lchild=p->Lchild; else f->Rchild=p->Lchild;

二叉排序树的删除算法描述 //如果p是双分支结点 if(p->Lchild!=NULL && p->Rchild!=NULL) q=p; s=p->Lchild; while(s->Rchild) { q=s ; s=s->Rchild; } if(q==p)q->Lchild=s->Lchild; else q->Rchild=s->Lchild; p->key=s->key; free(s); } //if } //else return t; } //DelBST

举例：如图是一棵二叉排序树，分别删除20和90的状态为 45 24 53 12 28 48 90 8 40 72 80 60 43 20

举例：删除45的状态为 45 45 24 53 24 53 12 12 44 44 44 48 90 48 48 90 8 40 43 8 72 80 60 40 72 80 60 43

平衡二叉排序树 平衡二叉排序树又称为AV树。其定义如下： 一棵平衡二叉排序树 或者是空树，或者是具有如下性质的二叉排序树： (1)左子树与右子树的深度之差（平衡因子Balance Factor）的绝对值小于等于1； (2) 左右子树都是平衡二叉树。 45 24 53 12 28 90 -1 45 24 53 12 28 90 72 -1 -2

综合设计：二叉排序树的综合运用 实验描述： 随机产生100个数，用二叉排序树和任选一种内排序方法进行排序，并对二种算法进行比较。 实验要求： 输入：要求产生的随机数先写入文本数据文件input.txt中，如没有数据文件input.txt,则先创建数据文件input.txt，之后每次产生的100个随机数均追加到文件input.txt中。 输出： （1）从文件input中顺序读出100个数，生成二叉排序树，并对二叉排序树进行中序遍历输出到文件output1.txt中，并从屏幕输出； （2）从文件input中读出相同的数据到数组中，用采用一种内部排序进行排序，输出到文件output2.txt中，并从屏幕输出。 对上述算法进行分析，给出①和②两种算法的优劣比较。 所涉及的数据结构：顺序表、二叉链表、文件等。 所涉及的算法：二叉排序树生成和遍历，排序算法等。