第六章 树和二叉树 ￡6.1 树 ￡6.2 二叉树 ￡6. 3 二叉树的存储结构 ￡6.4 二叉树的遍历与线索化 ￡6.1.1 树的定义 第六章 树和二叉树 ￡6.1 树 ￡6.2 二叉树 ￡6.1.1 树的定义 ￡6.2.1 二叉树的定义 ￡6.1.2 基本术语 ￡6.2.2 二叉树的性质 ￡6. 3 二叉树的存储结构 ￡6.4 二叉树的遍历与线索化 ￡6.3.1 顺序存储结构 ￡6.4.1 二叉树的遍历 ￡6.3.2 链序存储结构 ￡6.4.2 二叉树的线索化 ￡6.5.2 森林与二叉树的转换 ￡6.5.3 树和森林的遍历

￡6.1 树 ￡6.1.1 树的定义 （1）定义 树（Tree）：是n（n≥0）个结点的有限集。 定义一：（递归定义）： ①在任意一棵非空树中，有且仅有一个特定的称为根（root） 的结点； ②当n>1时，其余结点可分为m（m>0）个互不相交的有限集 T1, T2, … , Tm，其中每一个集合本身又是一棵树。并且 T1, T2, … , Tm，称为根的子树（SubTree）。 定义二：（形式定义） 任何一棵树是一个二元组Tree = (root, F)。 其中：root是数据元素，称做树的根结点；F是m（m≥0）棵树的森林， F＝（T1, T2, … , Tm），其中Ti = (ri, Fi)称做根root的第i棵子树；当m≠0 时，在树根和其子树森林之间存在下列关系： RF = {<root, ri> | i = 1, 2, … ,m; m > 0}

（2）表示形式 层次 A 1 B C D 2 E F G H I J 3 K L M 4 图6.1 一般的树 该树有13个结点。其中，A是树根，其余结点分成3个互不相交的子集： T1={B, E, F, K, L}，T2={C, G}，T3={D, H, I, J, M}; T1、T2和T3都是A的子树， 其本身也是一棵树。

(A(B(E(K, L), F), C(G), D(H(M), I, J))) 该树又可表示为如下三种形式： A B C D E F G H I J K L M A B C D E F G H I J K L M (a) 嵌套集合表示 (A(B(E(K, L), F), C(G), D(H(M), I, J))) (b) 广义表表示 (c) 凹入表示法 图6.2 树的其他3种表示法

（3）树的抽象数据类型定义 ADT Tree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 若D仅含一个数据元素，则R为空集，否则R={H},H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D－{root}≠Ф，则存在D－{root}的一个划分D1,D2,…,Dm(m>0), 对任意j≠k(1≤j,k≤m)有Dj∩Dk＝Ф，且对任意的i(1≤i≤m)，唯 一存在数据元素xi∈Di，有<root, xi>∈H； （3）对应于D－{root}的划分，H－{<root, xi>, … , <root, xm>}有唯一 的一个划分H1, H2, … , Hm(m>0)，对任意j≠k (1≤j,k≤m)有 Hj∩Hk＝Ф，且对任意i(1≤i≤m)，Hi是Di上的二元关系， (Di, {Hi})是一棵符合本定义的树，称为根root的子树。 基本操作： InitTree (&T); 操作结果：构造空树T。 DestroyTree (&T); 初始条件：树T存在。 操作结果：销毁树T。

CreateTree (&T, definition); 初始条件：definition给出树T的定义。 操作结果：按definition构造树T。 ClearTree (&T); 初始条件：树T存在。 操作结果：将树T清为空树。 TreeEmpty(T); 操作结果：若T为空树，则返回TRUE，否则返回FALSE。 TreeDepth(T); 操作结果：返回T的深度。 Root(T); 操作结果：返回T的根。 Value(T, cur_e); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：返回cur_e的值。 Assign(T, cur_e, value); 操作结果：结点cur_e赋值为value。

Parent(T, cur_e); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。 LeftChild(T, cur_e); 操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。 RightSibling(T, cur_e); 操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”。 InsertChild(&T, &P, i, c); 初始条件：树T存在，p指向T中某个结点，1≤i≤p所指结点的度＋1，非空 树c与T不相交。 操作结果：插入c为T中p指结点的第i棵子树。 DeleteChild(&T, &P, i); 初始条件：树T存在，p指向T中某个结点，1≤i≤p指结点的度。 操作结果：删除T中p所指结点的第i棵子树。 TraverseTree(T, visit()); 初始条件：树T存在，visit是对结点操作的应用函数。 操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。 一旦visit()失败，则操作失败。 }ADT Tree

￡6.1.2 基本术语 结点：包含一个数据元素及若干指向其子树的分支。在树的 图形表示中为一个圆圈。 结点的度（Degree）：结点拥有的子树树。 叶子（或终端结点）（Leaf）：度为0的结点。即没有子树 的结点。 孩子（Child）：结点的子树的根，称为该结点的孩子。 内部结点：除根结点之外的分支结点。 树的度：树内各结点的度的最大值。 分支结点（或非终端结点）：度不为0的结点。 双亲（Parent）：结点的子树的根，称为该结点的孩子，该 结点称为孩子的双亲。 兄弟（Sibling）：同一个双亲的孩子之间互称为兄弟。

祖先：从根到某结点所经分支上的所有结点，称为该结点的祖先。 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。 层次（Level）：从根开始定义起，根为第一层，根的孩子为第二 层。若某结点在第k层，则其子树的根就在第k＋1层。 堂兄弟：其双亲在同一层的结点互为堂兄弟。 深度（高度）（Depth）：树中结点的最大层次。 有序树：若将树中结点的各子树看成从左至右是有次序的（即不能 互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子 树的根称为第一个孩子，最右边的称为最后一个孩子。 森林（Forest）：是m（m≥0）棵互不相交的树的集合。对树中 每个结点而言，其子树的集合即为森林。

￡6.2 二叉树 ￡6.2.1 二叉树的定义 图6.3 二叉树的5种基本形态 （1）定义 二叉树（Binary Tree）：是另一种树型结构。 特点：①每个结点至多只有两棵子树（即二叉树中不存在度大于2 的结点）。 ②子树有左右之分，其次序不能任意颠倒。 （2）图形表示 (a) 空二叉树 (b) 仅有根结点的二叉树 (c) 右子树为空的二叉树 (d) 左、右子树均非空的二叉树 (e) 左子树为空的二叉树 (a) (b) (c) (d) (e) 图6.3 二叉树的5种基本形态

（3）二叉树的抽象数据类型定义 ∈H，且存在Dl上的关系Hr H；H = {<root, xl>, <root, xr>, Hl, Hr}； （4）(Dl, {Hl})是一棵符合本定义的二叉树，称为根的左子树，(Dr, {Hr}) 是一棵符合本定义的二叉树，称为根的右子树。 基本操作： ADT BinaryTree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若D = Ф，则R =Ф，称BinaryTree为空二叉树； 若D≠Ф，则R={H},H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D－{root}≠Ф，则存在D－{root} = {Dl, Dr}，Dl且∩Dm =Ф； （3）若Dl≠Ф，则Dl中存在唯一的元素x1，有<root, xl>∈H，且存在Dl 上的关系Hl H;若 Dr≠Ф,则Dr中存在唯一的元素xr,有<root, xr> InitBiTree (&T); 操作结果：构造空二叉树T。 DestroyBiTree (&T); 初始条件：二叉树T存在。 操作结果：销毁二叉树T。

CreateBiTree (&T, definition); 初始条件：definition给出二叉树T的定义。 操作结果：按definition构造二叉树T。 ClearBiTree (&T); 初始条件：二叉树T存在。 操作结果：将二叉树T清为空树。 BiTreeEmpty(T); 操作结果：若T为空二叉树，则返回TRUE，否则返回FALSE。 BiTreeDepth(T); 操作结果：返回T的深度。 Root(T); 操作结果：返回T的根。 Value(T, e); 初始条件：二叉树T存在， e是T中某个结点。 操作结果：返回e的值。 Assign(T, &e, value); 操作结果：结点e赋值为value。

Parent(T, e); 初始条件：二叉树T存在， e是T中某个结点。 操作结果：若e是T的非根结点，则返回它的双亲，否则函数值为“空”。 LeftChild(T, e); 操作结果：返回e的左孩子。若e无左孩子，则返回“空”。 RightChild (T, e); 操作结果：返回e的右孩子。若e无右孩子，则返回“空”。 LeftSibling(T, e); 操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”。 RightSibling (T, e); 操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”。 InsertChild(T, P, LR, c); 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉 树c与T不相交且右子树为空。 操作结果：根据LR为0或1，插入c为T中p指结点的左或右子树。p所指 结点的原有左或右子树则成为c的右子树。

DeleteChild(T, P, LR); 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。 操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。 PreOrderTraverse (T, visit()); 初始条件：二叉树T存在，visit是对结点操作的应用函数。 操作结果：先序遍历T，对每个结点调用函数visit()一次且仅一次。 一旦visit()失败，则操作失败。 InOrderTraverse (T, visit()); 操作结果：中序遍历T，对每个结点调用函数visit()一次且仅一次。 PostOrderTraverse (T, visit()); 操作结果：后序遍历T，对每个结点调用函数visit()一次且仅一次。 LevelOrderTraverse (T, visit()); 操作结果：层序遍历T，对每个结点调用函数visit()一次且仅一次。 }ADT BinaryTree

满二叉树：一棵深度为k且有2k－1个结点的二叉树称为满二叉树。 特点：每一层上的结点数都是最大结点数。 （4）特殊形态的二叉树 满二叉树：一棵深度为k且有2k－1个结点的二叉树称为满二叉树。 特点：每一层上的结点数都是最大结点数。 完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一 个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称 之为完全二叉树。 特点：①叶子结点只可能在层次最大的两层上出现； ②对任一结点，若其右分支下的子孙的最大层次为l， 则其左分支下的子孙的最大层次必为l或l＋1。 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 (a) 满二叉树 (b) 完全二叉树

6 7 1 1 2 3 2 3 4 5 4 5 6 (c) 非完全二叉树 (d) 非完全二叉树 图6.4 特殊形态的二叉树

￡6.2.2 二叉树的性质 性质一：在二叉树的第i层上至多有2i-1个结点，(i≥1)。 性质二：深度为k的二叉树至多有2k－1个结点，(k≥1)。 性质三：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结 点数为n2，则n0 = n2 + 1。 性质四：具有n个结点的完全二叉树的深度为 。 ） 性质五：如果一棵有n个结点的完全二叉树（其深度为 的结点按层序编号(从第1层到第 到右),则对任一结点i(1≤i≤n),有 层，每层从左 （1）如果i＝1，则结点i是二叉树的根，无双亲；如果i>1， 则其双亲PARENT(i)是结点 。 （2）如果2i > n，则结点i无左孩子（结点i为叶子结点）； 否则其左孩子LCHILD(i)是结点2i。 （3）如果2i＋1> n，则结点i无右孩子；否则其右孩子 RCHILD(i)是结点2i＋1。

￡6. 3 二叉树的存储结构 ￡6.3.1 顺序存储结构 //-----------------------二叉树的顺序存储表示--------------------------- #define MAX_TREE_SIZE 100 //二叉树的最大结点数 typedef TElemType SqBiTree[MAX_TREE_SIZE]; //0号单元存储根结点 SqBiTree bt; 用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结 点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标 为i－1的分量中。 例如，图6.5所示为图6.4(b)所示完全二叉树和图6.4(c)所示二叉树的顺序存储 结构。 1 2 3 4 5 6 7 8 9 10 11 12 (a) 完全二叉树 1 2 3 4 5 0 0 0 0 6 7 图中以“0”表示不存在此结点 (b) 一般二叉树 图6.5 二叉树的顺序存储结构

￡6.3.2 链序存储结构 （1）二叉链表 ①结点结构 lchild data rchild 其中，data：数据域； ②定义 二叉链表：用上述结点结构所得二叉树的存储结构称之为二叉链表。

易知，在含有n个结点的二叉链表中有n＋1个空链域。 ③图形表示 A A B B C C D D C D C D A A B B E F E F G G (a) 单支树的二叉链表 (b) 二叉链表 图6.7 二叉链表存储结构

④二叉链表的存储表示 typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; //左右孩子指针 } BiTNode, * BiTree Status CreateBiTree (BiTree &T); //按先后次序输入二叉树中结点的值（一个字符），空格字符表示空树， //构造二叉链表表示的二叉树T。 Status PreOrderTraverse (BiTree T, Status ( * Visit )( TElemType e)); //采用二叉链表存储结构，Visit是对结点操作的应用函数。 //先序遍历T，对每个结点调用函数Visit()一次且仅一次。 //一旦Visit()失败，则操作失败。 Status InOrderTraverse (BiTree T, Status ( * Visit )( TElemType e)); //中序遍历T，对每个结点调用函数Visit()一次且仅一次。 //---------------------基本操作的函数原型说明（部分）--------------------

Status PostreOrderTraverse (BiTree T, Status ( * Visit )( TElemType e)); //后序遍历T，对每个结点调用函数Visit()一次且仅一次。 //一旦Visit()失败，则操作失败。 Status LevelOrderTraverse (BiTree T, Status ( * Visit )( TElemType e)); //层序遍历T，对每个结点调用函数Visit()一次且仅一次。 （2）三叉链表 ①结点结构 lchild data parent rchild 其中，data：数据域； lchild：左指针域，指向该结点的左孩子； rchild：右指针域，指向该结点的右孩子； parent：双亲指针域，指向该结点的双亲结点。

②定义 三叉链表：用上述结点结构所得二叉树的存储结构称之为三叉链表 ③图形表示 A B C D E F G A B C D E F G 图6.8 三叉链表存储结构

￡6.4 二叉树的遍历与线索化 ￡6.4.1 二叉树的遍历 遍历二叉树（traversing binary tree）：按某条搜索路径巡访树中的每 个结点，使得每个结点均被访问一次，而且仅被访问一次。 例如，图6.9所示的二叉树表示下述表达式：a + b * (c－d)－e / f。 先序遍历：－+ a * b－c d / e f 表达式的前缀表示（波兰式） 中序遍历：a + b * c－d－e / f 表达式的中缀表示 后序遍历：a b c d－* + e f /－ 表达式的后缀表示（逆波兰式） 层序遍历：－+ / a * e f b－cd - + / a * e f b - c d 图6.9 ( a + b * (c－d)－e / f )表达式的二叉树

（1）递归算法 先序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 ①访问根结点； ②先序遍历左子树； ③先序遍历右子树。 中序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 ①中序遍历左子树； ②访问根结点； ③中序遍历右子树。 后序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 ①后序遍历左子树； ②后序遍历右子树； ③访问根结点。 层序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 按从上到下，从左到右的次序访问各结点。

若定义二叉树的存储结构为二叉链表，则有先序遍历二叉树的递归算法6.1如下： Status PreOrderTraverse (BiTree T, Status ( * Visit )( TElemType e)) { //采用二叉链表存储结构，visit是对数据元素操作的应用函数。 //先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。 //最简单的Visit函数是： // Status PrintElement (TElemType e) { //输出元素e的值 // printf ( e ); //实用时，加上格式串 // return OK; // } //调用实例：PreOrderTraverse (T, PrintElement); if (T) { if (Visit (T－>data)) if (PreOrderTraverse (T－>lchild, Visit)) if (PreOrderTraverse (T－>rchild, Visit)) return OK; return ERROR; } else } // PreOrderTraverse

（2）非递归算法 以中序遍历为例说明二叉树遍历的非递归算法。 仿照递归算法执行过程中递归工作栈的状态变化状况可直接写成相应 的非递归算法： ①工作记录中包含两项，其一是递归调用的语句编号，其二是指向根 结点的指针，则当栈顶记录中的指针非空时，应遍历左子树，即指 向左子树树根的指针进栈； ②若栈顶记录中的指针值为空，则应退至上一层，若是从左子树返回, 则应访问当前层即栈顶记录中指针所指的根结点； ③若是从右子树返回，则表明当前层的遍历结束，应继续退栈。

由上述分析可得两个中序遍历二叉树的非递归算法如下所示： 算法6.2如下： Status InOrderTraverse (BiTree T, Status ( * Visit )( TElemType e)) { //采用二叉链表存储结构，visit是对数据元素操作的应用函数。 //中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。 InitStack (S); Push (S, T); //根指针进栈 while (!StackEmpty (S) ) { while (GetTop(S, p) & & p) Push (S, p－>lchild); //向左走到尽头 Pop (S, p); if (!StackEmpty (S) ) { //访问结点，向右一步 if (!Visit (p－>data) ) return ERROR; Push (S, p－>rchild); } // if } // while return OK; } // InOrderTraverse

算法6.3如下： Status InOrderTraverse (BiTree T, Status ( * Visit )( TElemType e)) { //采用二叉链表存储结构，visit是对数据元素操作的应用函数。 //中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。 InitStack (S); P = T; while (p | |!StackEmpty (S) ) { if (p) { //根指针进栈，遍历左子树 Push (S, p); p = p－>lchild; } // if else { //根指针退栈，访问根结点，遍历右子树 Pop (S, p); if (!Visit (p－>data) ) return ERROR; p = p－>rchild); } // else } // while return OK; } // InOrderTraverse

（3）二叉树的建立 算法6.4是一个按先序序列建立二叉树的二叉链表的过程。 算法6.4如下： Status CreateBiTree (BiTree &T) { //按先序次序输入二叉树中结点的值（一个字符）， //空格字符表示空树，构造二叉链表表示的二叉树T。 scanf (&ch); if (ch = = ‘ ‘) T = NULL; else { if (!(T = (BiTNode *) malloc (sizeof (BiTNode) ) ) ) exit (OVERFLOW); T－>data = ch; //生成根结点 CreateBiTree (T－>lchild); //构造左子树 CreateBiTree (T－>rchild); //构造右子树 } return OK; } // CreateBiTree

例如，对图6.10所示二叉树，按下列次序顺序读入字符： A B CФФD EФG ФФFФФФ A B C D E F G 图6.10 二叉树

￡6.4.2 二叉树的线索化 当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直 接得到结点在任一序列（先序、中序或后序序列）中的前驱和后继信息，这种 信息只有在遍历的动态过程中才能得到。为了保存这种在遍历过程中得到的信 息，我们利用二叉链表中的空链域（由于结点没有左子树或右子树），来存放 结点的前驱和后继信息。 作如下规定： ①若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱； ②若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。 （1）线索链表的结点结构 lchild LTag data RTag rchild 其中：data：数据域； lchild：左指针域，指向该结点的左孩子； rchild：右指针域，指向该结点的右孩子；

线索链表：以上述结点结构构成的二叉链表作为二叉树的存储结构，称之 为线索链表。 0 lchild域指示结点的左孩子 LTag = 1 lchild域指示结点的前驱 0 rchild域指示结点的右孩子 RTag = 1 rchild域指示结点的后继 （2）线索链表的定义 线索链表：以上述结点结构构成的二叉链表作为二叉树的存储结构，称之 为线索链表。 （3）相关术语 线索：在线索链表中指向结点前驱和后继的指针。 线索二叉树（Threaded Binary Tree）：加上线索的二叉树。 线索化：对二叉树以某种次序遍历使其变为线性二叉树的过程。

（4）图形表示 - + / NIL NIL a * e f b - c d - + / a * e f b - c d (a) ( a + b * (c－d)－e / f )表达式的二叉树 (b) 中序线索二叉树

thrt 0 1 bt 0 － 0 0 ＋ 0 0 / 0 1 a 1 0 * 0 1 e 1 1 f 1 1 b 1 1 c 1 1 d 1 (c) 中序线索链表 图6.11 线索二叉树及其存储结构 图中，实线为指针（指向左、右子树），虚线为线索（指向前驱和后继）。

（5）C语言描述 //---------------------------二叉树的二叉线索存储表示---------------------------- typedef enum PointerTag {Link, Thread}; //Link = = 0:指针，Thread = = 1:线索 typedef struct BiThrNode { TElemType data; struct BiThrNode *lchild, *rchild; //左右孩子指针 PointerTag LTag, RTag; //左右标志 } BiThrNode, * BiThrTree; （6）遍历算法 仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，并令其 lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最 后一个结点；反之，令二叉树中序序列中的第一个结点的lchild域指针和最后一 个结点rchild域的指针均指向头结点。这就为二叉树建立了一个双向线索链表， 既可从第一个结点起顺后继进行遍历，也可从最后一个结点起顺前驱进行遍历。 下述算法正是以双向线索链表为存储结构时对二叉树进行遍历的算法。

算法6.5如下： Status InOrderTraverse_Thr (BiThrTree T, Status ( * Visit )( TElemType e)) { //T指向头结点，头结点的左链lchild指向根结点，可参加线索化算法。 //中序遍历二叉线索树T的非递归算法，对每个数据元素调用函数Visit。 p = T－>lchild; //p指向根结点 while (p != T) { //空树或遍历结束时，p = = T while (p－>LTag = =Link) p = p－>lchild; if (!Visit (p－>data) ) return ERROR; //访问其左子树为空的结点 while (p－>RTag = = Thread & & p－>rchild != T) { p = p－>rchild; Visit (p－>data); //访问后继结点 } return OK; } // InOrderTraverse_Thr

（7）二叉树的线索化算法 算法6.6如下： Status InOrderThreading (BiThrTree &Thrt, BiThrTree T) { //中序遍历二叉线索树T，并将其中序线索化，Thrt指向头结点。 if (!(Thrt = (BiThrTree) malloc (sizeof (BiThrNode)))) exit (OVERFLOW); Thrt－>LTag = Link; Thrt－>RTag = Thread; //建头结点 Thrt－>rchild = Thrt; //右指针回指 if (!T) //若二叉树空，则左指针回指 Thrt－>lchild = Thrt; else { Thrt－>lchild = T; pre = Thrt; InThreading (T); //中序遍历进行中序线索化 pre－>rchild = Thrt; pre－>RTag = Thread; //最后一个结点线索化 Thrt－>rchild = pre; } // else return OK; } // InOrderThreading 指针pre始终指向刚刚访问过的结点,若指针p指向当前访问的结点,则pre指向它的前驱

算法6.7如下： void InThreading (BiThrTree p) { if (p) { InThreading (p－>lchild); //左子树线索化 if (! p－>lchild) { //前驱线索 p－>LTag = Thread; p－>lchild = pre; } if (! pre－>rchild) { //后继线索 pre－>RTag = Thread; pre－>rchild = p; pre = p; InThreading (p－>rchild); //右子树线索化 } // if } // InThreading 线索化的过程是在遍历过程中修改二叉链表中的空指针为指向前驱或后继的线索的过程。

￡6.5 树和森林 ￡6.5.1 树的存储结构 （1）双亲表示法 ①C语言描述 假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器 指示其双亲结点在链表中的位置。 #define MAX_TREE_SIZE 100 typedef struct PTNode { //结点结构 TElemType data; int parent; //双亲位置域 } PTNode typedef struct { //树结构 PTNode nodes[MAX_TREE_SIZE]; int r, n; //根的位置和结点数 } PTree;

数组下标 0 R -1 1 A 0 2 B 0 3 C 0 4 D 1 5 E 1 6 F 3 7 G 6 8 H 6 9 K 6 ②图形表示 数组下标 R A B C D E F G K H 图6.12 树的双亲表示法示例

（2）孩子表示法 ①定义 孩子表示法：把每个结点的孩子结点排列起来，看成是一个线性表， 且以单链表作存储结构，则n个结点有n个孩子链表（叶子的孩子链表为 空表）。而n个头指针又组成一个线性表，为了便于查找，可采用顺序存 储结构。 ②C语言描述 typedef struct CTNode { //孩子结点 int child; struct CTNode *next; } * ChildPtr typedef struct { TElemType data; ChildPtr firstchild; //孩子链表头指针 } CTBox; CTBox nodes[MAX_TREE_SIZE]; int n, r; //结点数和根的位置； } CTree

③图形表示 0 A 3 5 1 B 2 C 6 3 D 4 R 0 1 2 5 E 6 F 7 8 9 7 G 8 H 9 K R A B C D E F G K H (a) 原树 (b) 孩子链表

0 4 A 3 5 1 4 B 2 4 C 6 3 0 D 4 -1 R 0 1 2 6 2 F 7 8 9 5 0 E 7 6 G 8 6 H 9 6 K (c) 带双亲的孩子链表 图6.13 树的另外两种表示法 上图(c)是把双亲表示法和孩子表示法结合起来，即将双亲表示和孩 子链表合在一起的存储结构。

（3）孩子兄弟表示法 ①定义 孩子兄弟表示法：又称二叉树表示法，或二叉链表表示法。即以二叉 链表作树的存储结构。链表中的两个域分别指向该结点的第一个孩子结点 和下一个兄弟结点。 ②C语言描述 typedef struct CSNode { TElemType data; struct CSNode *firstchild, *nextsibling; } CSNode , * CSTree

R A B D E F G K H C ③图形表示 R A B C D E F G K H 图6.14 树的二叉链表表示法

￡6.5.2 森林与二叉树的转换 （1）森林转换成二叉树 如果F = {T1, T2, … ,Tm}是森林，则可按如下规则转换成一棵二叉树 B = (root, LB, RB)。 ① 若F为空，即m＝0，则B为空树； ② 若F非空，即m≠0，则B的根root即为森林中第一棵树的根ROOT(T1)； B的左子树LB是从T1中根结点的子树森林F1 = {T11, T12, … ,T1m}转换而 成的二叉树;其右子树RB是从森林F’ = {T2, T3, … ,Tm}转换而成的二叉树。 （2）二叉树转换成森林 如果B = (root, LB, RB)是一棵二叉树，则可按如下规则转换成森林 F = {T1, T2, … ,Tm}。 ①若B为空，则F为空； ②若B非空，则F中第一棵树T1的根ROOT(T1)即为二叉树B的根root；T1中 的根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除T1之外 其余树组成的森林F’ = {T2, T3, … ,Tm}是由B的右子树RB转换而成的森林。

例，图6.15展示了森林与二叉树之间的对应关系。 A B C D B E A J I H C D G F E F G H I J 森林与二叉树对应 树与二叉树对应 A B C D G J I H E F 树根相连 图6.15 森林与二叉树的对应关系

￡6.5.3 树和森林的遍历 树的遍历方法： ①先根（次序）遍历，即：先访问树的根结点，然后依次先根遍历根的每 棵子树； ②后根（次序）遍历，即：先依次后根遍历每棵子树，然后访问根结点。 例如，对图6.16的树进行遍历，可得树的序列为： 先根遍历：A B C D E 后根遍历：B D C E A A C D E B 图6.16

森林的遍历方法： ①先序遍历森林 若森林非空，则可按下述规则遍历之： 1．访问森林中第一棵树的根结点； 2．先序遍历第一棵树中根结点的子树森林； 3．先序遍历除去第一棵树之后剩余的树构成的森林。 ②中序遍历森林 若森林非空，则可按下述规则遍历之： 1．中序遍历森林中第一棵树的根结点的子树森林； 2．访问第一棵树的根结点； 3．中序遍历除去第一棵树之后剩余的树构成的森林。 例如，对图6.15中森林进行遍历，得到森林的序列为： 先序遍历： A B C D E F G H I J 中序遍历： B C D A F E H J I G

￡6.6 赫夫曼树及其应用 ￡6.6.1 最优二叉树（赫夫曼树） （1）基本概念 路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 路径长度：路径上分分支数目。 树的路径长度：从树根到每一结点的路径长度之和。 结点的带权路径长度：指从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作： 最优二叉树（或赫夫曼树）：带权路径长度WPL最小的二叉树。

例1，图6.17中3棵二叉树，都有4个叶子结点a、b、c、d，分别带权7、5、 2、4，它们的带权路径长度分别为： (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 2 7 e a 7 5 2 4 4 5 a b c d d b 7 5 2 4 a b c d (a) (b) (c) 图6.17 具有不同带权路径长度的二叉树 例2，利用赫夫曼树得到最佳判定树（见书P144）。

（2）赫夫曼树的构造 赫夫曼算法： ①根据给定的n个权值{w1, w2, … , wn}构成n棵二叉树的集合F = {T1, T2, … , Tn}， 其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。 ②在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且 置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 ③在F中删除这两棵树，同时将新得到的二叉树加入F中。 ④重复②和③，直到F只含一棵树为止。这棵树便是赫夫曼树。 例如，图6.18展示了图6.17的赫夫曼树的构造过程。其中，根结点上标注的数字 是所赋的权。 7 5 2 4 a b c d 7 5 6 a b c d (a) (b)

b 7 11 c d a 18 b c d a (c) (d) 图6.18 赫夫曼树的构造过程

￡6.6.2 赫夫曼编码 （1）前缀编码 前缀编码：任一个字符的编码都不是另一个字符的编码的前缀，这种编码 称做前缀编码。 约定：在二叉树中，左分支表示字符’0’，右分支表示字符’1’，则可以从根 结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。 例如，假设有图6.19所示的二叉树，其4个叶子结点分别表示A、B、C、D 这4个字符。 由图6.19所得A、B、C、D的二进制前缀编码分别为0、10、110、111 编码 A(0) 0 1 B(10) A C(110) 0 1 D(111) B C D 图6.19 前缀编码示例

（2）赫夫曼编码 假设每种字符在电文中出现的次数为wi，其编码长度为li，电文中只有n种 。对应到二叉树上，若置wi为叶子结点的权,li 字符，则电文总长为 恰为从根到叶子的路径长度，则 恰为二叉树上带权路径长度。 由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率 作权,设计一棵赫夫曼树的问题,由此得到的二进制前缀编码便称为赫夫曼编码。 （3）赫夫曼树和赫夫曼编码的存储表示 typedef struct { unsigned int weight; unsigned int parent, lchild, rchild; } HTNode, * HuffmanTree //动态分配数组存储赫夫曼树 typedef char ** HuffmanCode; //动态分配数组存储赫夫曼编码表

void HuffmanCoding (HuffmanTree &HT, HuffmanCode &HC, int *w, int n) { （4）求赫夫曼编码的算法 算法6.8如下： void HuffmanCoding (HuffmanTree &HT, HuffmanCode &HC, int *w, int n) { //w存放n个字符的权值(均>0)构造赫夫曼树HT， //并求出n个字符的赫夫曼编码HC。 if (n <= 1) return; m = 2 * n – 1; HT = (HuffmanTree) malloc ((m + 1) * sizeof (HTNode)); //0号单元未用 for (p = HT, i = 1; i <= n; ++i, ++p ,++w) *p = {*w, 0, 0, 0}; for (; i <= m; ++i, ++p) *p = {0, 0, 0, 0}; for (i = n+1; i <= m; ++i) { //建赫夫曼树 //在HT[1..i-1]选择parent为0且weight最小的两个结点， //其序号分别为s1和s2 Select (HT, i – 1, s1, s2); HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } // for 向量HT的前n个分量表示叶子结点，最后一个分量表根结点。

//- - - - - 从叶子到根逆向求每个字符的赫夫曼编码 - - - - - - - HC = (HuffmanCode)malloc((n + 1)*sizeof(char*)); //分配n个字符编码的头指针向量 cd = (char *) malloc (n * sizeof (char)); //分配求编码的工作空间 cd[n – 1] = “\0”; //编码结束符 for (i = 1; i <= n; ++i) { //逐个字符求赫夫曼编码 start = n – 1; //编码结束符位置 for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) //从叶子到根逆向求编码 if (HT[f].lchild = = c) cd [– – start] = ‘0’; else cd [– – start] = ‘1’; HC[i] = (char *) malloc ((n – start) * sizeof (char)); //为第i个字符编码分配空间 strcpy (HC[i], &cd[start]); //从cd复制编码(串)到HC } // for free (cd); //释放工作空间 } // HuffmanCoding

在算法6.8中，求每个字符的赫夫曼编码是从叶子到根逆向处理的。也可以从 根出发，遍历整棵赫夫曼树，求得各个叶子结点所表示的字符的赫夫曼编码如算 法6.9所示。 算法6.9如下： //-------------无栈非递归遍历赫夫曼树，求赫夫曼编码---------- HC = (HuffmanCode) malloc ((n + 1) * sizeof (char *)); p = m; cdlen = 0; for (i = 1; i <= m; ++i) HT[i].weight = 0; //遍历赫夫曼树时用作结点状态标志 while (p) { if (HT[p].weight = = 0) { //向左 HT[p].weight = 1; if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen ++] = “0”; }

else if (HT[p].rchild = = 0) { //登记叶子结点的字符的编码 HC[p] = (char *) malloc ((cdlen + 1) * sizeof (char )); cd[cdlen] = “\0”; strcpy (HC[p], cd); //复制编码(串) } // else if } // if else if (HT[p].weight = = 1) { //向左 HT[p].weight = 2; if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] = “1”; } } else { HT[p].weight = 0; p = HT[p].parent; ――cdlen; //退到父结点，编码长度减1 } // else } // while

（5）例子 已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11，试设计赫夫曼编码。 设权w＝{5, 29, 7, 8, 14, 23, 3, 11}, n = 8，则m＝15，按上述算法可构造一棵赫 夫曼树如图6.20所示。其存储结构HT的初始状态如图6.21(a)所示，其终结状态 如图6.21(b)所示，所得赫夫曼编码如图6.21(c)所示。 0 1 0 1 0 1 23 29 11 14 5 3 7 8 图6.20 赫夫曼树

HT weight parent lchild rchild 1 5 0 0 0 1 5 9 0 0 2 29 0 0 0 2 29 14 0 0 3 7 0 0 0 3 7 10 0 0 4 8 0 0 0 4 8 10 0 0 5 14 0 0 0 5 14 12 0 0 6 23 0 0 0 6 23 13 0 0 7 3 0 0 0 7 3 9 0 0 8 11 0 0 0 8 11 11 0 0 9 － 0 0 0 9 8 11 1 7 10 － 0 0 0 10 15 12 3 4 11 － 0 0 0 11 19 13 8 9 12 － 0 0 0 12 29 14 5 10 13 － 0 0 0 13 42 15 6 11 14 － 0 0 0 14 58 15 2 12 15 － 0 0 0 15 100 0 13 14 (a) HT的初态 (b) HT的终态

HC 1 2 3 4 5 6 7 8 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 0 (c) 赫夫曼编码HC 图6.21 存储结构