|
|
| 二叉树和树 |
|
|
|
|
第六章二叉树和树1.教学目的掌握一种重要的非线性结构——树的定义、特点、典型算法及在实际中的实用。2.教学要求①理解二叉树的结构
特点。②掌握二叉树的各种存储结构的特点及适用范围。③掌握按各种次序遍历二叉树的递归和非递归算法。④掌握树的各种存储结构
、特点。⑤掌握建立最优二叉树和哈夫曼编码的方法。3．教学重点：①掌握二叉树的定义、性质和存储结构。②掌握二叉树的遍历方
法及递归和非递归算法实现。③掌握建立最优二叉树和哈夫曼编码的方法。4．教学难点：①线索二叉树。②遍历二叉树的递归和非递归算
法。树的定义树（Tree）是n（n≥0）个结点的有限集，它或为空树（n?=?0），或为非空树；对于非空树T：（1）有且仅有一个称之
为根的结点；（2）除根结点以外，其余结点可分为m（m＞0）个互不相交的有限集T1,T2,…,Tm,其中每一个集合本身又是一
棵树，称为根的子树（SubTree）。树是n个结点的有限集T1T2T3树的其它表示方式嵌套集合凹入表示广义表基本术语——即根结点(
没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)根叶子森林有序树无序树——结点各子
树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。基本术语双亲孩子兄弟堂兄弟祖先子孙——即上层的那个结点(直接前驱)—
—即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）——即从
根到该结点所经分支的所有结点——即该结点下层子树中的任一结点基本术语层次1234结点结点的度结点的层次终端结点分支结点——即树的数
据元素——结点挂接的子树数——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为内部结点）
树的度树的深度(或高度)——所有结点度中的最大值——指所有结点中最大的层数6.1二叉树6.1.1二叉树的定义二叉树（Binar
yTree）是n（n≥0）个数据元素的有限集合。该集合或者为空,或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树
的二叉树组成。普通树（多叉树）若不转化为二叉树，则运算很难实现为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，
规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。二叉树特点①左子树和右子树是两棵互不相交的二叉树；②每个结点至多
有两棵子树（结点的度小于等于2），且有左右之分，次序不能任意颠倒；③有序性。即若左、右子树颠倒，就成为另一棵二叉树。五种基本形态左
子树右子树右子树左子树（ｅ）（ａ）（ｂ）（ｃ）（ｄ）6.1.2二叉树的基本概念结点:包含一个数据元素及指向子树的分支。结点
的度:结点所拥有的子树的个数。叶子结点（终端结点）:度为0的结点。分支结点（非终端结点）:度不为0的结点。左孩子结点:
结点的左子树的根，称为该结点的左孩子。(右孩子定义相同)双亲结点:结点的直接前驱。兄弟结点:同一双亲的孩子结点之间互称兄弟结点
。祖先结点:从根结点到该结点路径上的所有结点.。子孙结点:以某结点为根的子树中的任一结点。二叉树的度:二叉树中各结点度的最大
值。结点的层次:从根开始定义，根结点层次为1，根孩子的层次为2，依此类推。二叉树的高度（深度）:叶子结点的最大层次数。练习
具有3个结点的二叉树可能有几种不同形态？5种案例1：数据压缩问题将数据文件转换成由0、1组成的二进制串，称之为编码。（a）等
长编码方案（b）不等长编码方案1（c）不等长编码方案2字符编码字符编码字符编码a00a0a0b01b10b
01c10c110c010d11d111d111案例2：利用二叉树求解表达式的值以二叉树表示表达式的递归定义如下：（1）若表达式
为数或简单变量，则相应二叉树中仅有一个根结点，其数据域存放该表达式信息；（2）若表达式为“第一操作数运算符第二操作数”的形式，
则相应的二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符（若为一元运算符，则左子树为空），其中，操作
数本身又为表达式。(a+b(c-d)-e/f)的二叉树满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且
所有叶子结点都在同一层上，称作满二叉树。顺序表示：从二叉树的根开始，层间从上到下，层内从左到右，逐层进行编号（1，2，……，n）
。(a)满二叉树(b)非满二叉树满二叉树的特点有：叶子只能出现在最下一层。非叶子结点的度一定是2。在同样深度的二叉树中，满二叉树的
结点个数最多，叶子最多。完全二叉树：深度为k，结点数为n的二叉树，如果其结点1～n的位置序号分别与满二叉树的结点1～n的位置序号一
一对应，则为完全二叉树。满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树。完全二叉树的特点：叶子结点只能出现在最下两层
。最下层的叶子一定集中在左部连续位置。倒数二层若有叶子结点，一定都在右部连续位置。如果结点度为1，则该结点只有左孩子，即不存
在只有右孩子的情况。同样结点数的二叉树，完全二叉树的深度最小。(a)满二叉树(a)完全二叉树特殊形态的二叉树满二叉树：一棵深度
为k且有2k-1个结点的二叉树。（特点：每层都“充满”了结点）完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结
点都与深度为k的满二叉树中编号从1至n的结点一一对应只有最后一层叶子不满，且全部集中在左边满二叉树和完全二叉树的区别满二叉树是叶
子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。6.1
.3二叉树的性质性质1:在二叉树的第i层上至多有2i-1个结点(i≥1)。证明：用数学归纳法。性质2:深度为k的二
叉树至多有2k-1个结点（k≥1）。性质3:对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0=n2+
1。性质4：具有n个结点的完全二叉树的深度为［log2n］+1。6.1.3二叉树的性质性质1:在二叉树的第i层上至多有2
i-1个结点1提问：第i层上至少有个结点？性质2:深度为k的二叉树至多有2k-1个结点k提问：深度为k时至少有个结点？性质3
:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2＋1（即n0=n2+1）性质4:具有n个结点的完全二叉树
的深度必为[log2n]＋1k-1层k层2k?1?1＜n≤2k?1或2k?1≤n＜2kk?1≤log2n＜k，因为k是整数所
以k?=??log2n??+?1n性质5:对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点
从1开始顺序编号，则对于任意的序号为i的结点有：（1）如i=1，则i是根结点，无双亲；如i>1，则i的结点的双亲结点序号为
i/2（“/”表示整除）（2）如2i>n，则i的结点无左孩子；否则Lchild(i)=2i（3）如2i＋1>n，则i的结点无右孩
子；否则Rchild(i)=2i+1性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其
右孩子编号必为2i＋1；其双亲的编号必为i/2（取整）。练习一棵完全二叉树有5000个结点，可以计算出其叶结点的个数是（
）。2500解题思路：n0+n1+n2=5000,二叉树性质3：n0=n2+1,代入得：2n2
+1+n1=5000可以看出n1是奇数,而对于完全二叉树n1≤1,故n1=1因此n2=2499,n0=
25006.2二叉树的存储结构6.2.1顺序存储结构用一组连续的存储单元存放二叉树中的结点。一般按照二叉树结点从上至下
、从左到右的顺序存储。结点在存储位置上的前驱、后继关系并不一定就是它们在逻辑上的邻接关系，只有通过一些方法确定某结点在逻辑上的前驱
结点和后继结点，这种存储才有意义。实现：按满二叉树/完全二叉树的结点层次编号，依次存放二叉树中的数据元素。AABCBCDEDEFG
FGABCDEFG(a)一棵二叉树(b)改造后的完全二叉树(c)改造后的完全二叉树存储状态二叉树的顺序存储表示可描述为：#def
ineMAXNODE /二叉树的最大结点数/typedefdatatypeSqBi
Tree[MAXNODE];/0号单元存放结点数目/SqBiTreebt;即将bt定义为含有MAXNODE个dat
atype类型元素的一维数组。二叉树的顺序存储abcdefg单支树0123456
78910abcde0000fg特
点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树6.2.2链式存储结构（1）二叉链表存储LChildDat
aRChild数据域右孩子域左孩子域typedefstructNode{datatypedata;struc
tNodeLChild;structNodeRChild;}BiTNode,BiTree;Bi
Treebt;头指针bt(a)二叉树(b)带头指针的二叉链表指向双亲的指针（2）三叉链表存储LChildDataparent
RChild优点：既便于查找孩子结点，又便于查找双亲结点；缺点：增加了空间开销。(a)二叉树(b)二叉树的三叉链表存储结构练习
^FDAGCBE^^^^^^^n+1在n个结点的二叉链表中，有个空指针域思路1：必有2n个链域。除根结点外，每个结点
有且仅有一个双亲，所以只会有n－1个结点的链域存放指针，指向非空子女结点。空指针数目＝2n－(n-1)=n+1思路2：n=n0+n
1+n2根据性质3n0=n2+1，得到n=2n0+n1-1度为0的结点空指针数目为2，度为1的结点空指针数目为1所以空指针
数目=2n0+n1=n+1，尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树
，甚至比顺序存储结构还节省空间。因此，二叉链表是最常用的二叉树存储方式。本书后面所涉及到的二叉树的链式存储结构不加特别说明的都是
指二叉链表结构。性质：含有n个结点的二叉树必有n＋1个空的链域。6.3二叉树的遍历6.3.1二叉树的遍历方法及递归实现遍历
的定义：按某条搜索路径巡访树中的每个结点，使每个结点访问且仅被访问一次。遍历的用途：树结构插入、删除、修改、查找和排序运算的前提
，是二叉树一切运算的基础和核心。对二叉树的遍历顺序有六种方式，若约定Lch在前，Rch在后，则有三种方式：(1)RootL
chRch前序遍历（先根）；(2)LchRootRch中序遍历（中根）；(3)LchRchRoot后序遍历（
后根）。遍历规则D先左后右LRDLRLDRLRDDRLRDLRLDABCDE先序遍历：中序
遍历：后序遍历：ABDECDBEACDEBCA口诀：DLR—先序遍历，即先根再左再右LDR—中序遍历，即先
左再根再右LRD—后序遍历，即先左再右再根+EDC/BA先序遍历+/ABCDE前缀表示中序遍历A/B
CD+E中缀表示后序遍历AB/CDE+后缀表示层序遍历+ED/CAB用二叉树
表示算术表达式ABCEDHFG举例1：先序遍历过程：ABCEDHFG先序遍历结果：BADFGCEHABCEDHFG中序遍历过程：
ABCEDHFG中序遍历结果：BFADGCEHABCEDHFG后序遍历过程：ABCEDHFG后序遍历结果：BAFGDHEC-+/e
adbc举例2：最早提出遍历问题是对存储在计算机中的表达式求值。例如：（a+bc）-d/e。表达式的前缀、中缀、后缀形式：
前缀：-+abc/de中缀：a+bc-d/e后缀：abc+de/-前缀表达式称为波兰表达式；后缀表
达式被称作逆波兰表达式。遍历的算法实现－先序遍历ACBDADLRDLR>>>BCDLR
>>D若二叉树为空，则空操作否则访问根结点(D)前序遍历左子树(L)前序遍历右子树(R)DL
R先序遍历序列：ABDC遍历的算法实现－－用递归形式格外简单！则遍历算法可写出:回忆:longFact
orial(longn){if(n==0)return1;//基本项elsereturnnF
actorial(n-1);//归纳项}先序遍历算法StatusPreOrderTraverse(BiTreeT){if
(T==NULL)returnOK;//空二叉树else{cout<data;//访问根结点PreOrder
Traverse(T->lchild);//递归遍历左子树PreOrderTraverse(T->rchild);//递归遍
历右子树}}ABC左是空返回左是空返回>右是空返回TDT左是空返回BTD右是空返回Tprintf(B);>ATprintf(D
);主程序pre(TL);printf(A);pre(TL);pre(TR);pre(TL);>p
re(TR);TPre(T)pre(TR);TC>Tprintf(C);pre(TL);>pre(T
R);T先序序列：ABDCStatusPreOrderTraverse(BiTreeT){if(T==NULL)re
turnOK;else{cout<data;PreOrderTraverse(T->lchild);PreO
rderTraverse(T->rchild);}}ABCD返回返回返回返回返回1先序遍历：若二叉树为空，则空操作，否则依次执
行如下3个操作：(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。1voidPreOrd
er(BiTreebt)2{/先序遍历二叉树bt/3if(bt==NULL)return;
/递归调用的结束条件/4Visite(bt->data); /访问结点的数据域/5
PreOrder(bt->lchild); /先序递归遍历bt的左子树/6PreOrder(b
t->rchild); /先序递归遍历bt的右子树/7}遍历的算法实现－中序遍历ACBDBLD
RLDR>>>ACLDR>>DLDR若二叉树为空，则空操
作否则:中序遍历左子树(L)访问根结点(D)中序遍历右子树(R)中序遍历序列：BDAC中序遍历算法Status
InOrderTraverse(BiTreeT){if(T==NULL)returnOK;//空二叉树else{In
OrderTraverse(T->lchild);//递归遍历左子树cout<data;//访问根结点InOrde
rTraverse(T->rchild);//递归遍历右子树}}2中序遍历：若二叉树为空，则空操作，否则依次执行如下3个操
作：(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。中序遍历二叉树的递归算法如下：1vo
idInOrder(BiTreebt)2{/中序遍历二叉树bt/3if(bt==NULL)retu
rn; /递归调用的结束条件/4InOrder(bt->lchild); /中序递归遍历bt的
左子树/5Visite(bt->data); /访问结点的数据域/6InOrder
(bt->rchild); /中序递归遍历bt的右子树/7}遍历的算法实现－后序遍历ACBDLR
DLRDBLRD>>AC>>D若二叉树为空，则空操作否则后序遍历左子树(L)后序遍历右子树(R)访
问根结点(D)LRD后序遍历序列：DBCA后
序遍历算法StatusPostOrderTraverse(BiTreeT){if(T==NULL)returnOK;/
/空二叉树else{PostOrderTraverse(T->lchild);//递归遍历左子树PostOrderTrav
erse(T->rchild);//递归遍历右子树cout<data;//访问根结点}}3后序遍历：若二叉树为
空，则空操作，否则依次执行如下3个操作：(1)先序遍历左子树；(2)先序遍历右子树；(3)访问根结点。后序遍历二
叉树的递归算法如下：1voidPostOrder(BiTreebt)2{/后序遍历二叉树bt/3
if(bt==NULL)return; /递归调用的结束条件/4PostOrder(bt->lchi
ld); /后序递归遍历bt的左子树/5PostOrder(bt->rchild); /后序递归
遍历bt的右子树/6Visite(bt->data); /访问结点的数据域/7}遍历算
法的分析StatusInOrderTraverse(BiTreeT){if(T==NULL)returnOK;els
e{InOrderTraverse(T->lchild);cout<data;InOrderTraverse(T-
>rchild);}}StatusPreOrderTraverse(BiTreeT){if(T==NULL)retu
rnOK;else{cout<data;PreOrderTraverse(T->lchild);PreOr
derTraverse(T->rchild);}}StatusPostOrderTraverse(BiTreeT){i
f(T==NULL)returnOK;else{PostOrderTraverse(T->lchild);PostO
rderTraverse(T->rchild);cout<data;}}遍历算法的分析ACBEDFG如果去掉输出语
句，从递归的角度看，三种算法是完全相同的，或说这三种算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径上，
每个结点经过3次。第1次经过时访问＝先序遍历第2次经过时访问＝中序遍历第3次经过时访问＝后序遍历遍历算法的分析ACBEDFG时间效
率:O(n)//每个结点只访问一次空间效率:O(n)//栈占用的最大辅助空间6.3.2二叉树遍历的非递归实现从根结点开始，
沿着虚线由根结点的左子树、根结点的右子树依次遍历二叉树。△标记先序序列，深入时遇到结点就访问；○标记中序序列，从左子树返回时遇到结
点访问，□标记后序序列，从右子树返回时遇到结点访问1先序遍历的非递归实现15else16
{17printf(″栈溢出″);18return;19
}20p=p->lchild;21}22if(top<=0)return
;//栈空23else24{25top--;26p=sta
ck[top];//pop27p=p->rchild;28}29}30}1
voidNRPreOrder(BiTreebt)2{/非递归先序遍历二叉树/3BiTreestack
[MAXNODE],p;4inttop;5if(bt==NULL)return;6top=0;
7p=bt;8while(!(p==NULL&&top==0))9{while(p!=NUL
L)10{visite(p->data);if(topp;13top++;14}2中序遍历的非递归实现中序遍历的非递归算法的实现
，只需将先序遍历的非递归算法中的语句10：visite(p->data)移到语句26：p=stack[top]和语句27：p=p-
>rchild之间即可。flag＝1第一次出栈，结点不能访问?2第二次出栈，结点可以访问{3后序遍历的非递归实现算法思想
:在后序遍历过程中，结点要入两次栈，出两次栈，而访问结点是在第二次出栈时访问。因此，为了区别同一个结点指针的两次出栈，设置一标志
flag，令：当结点指针进、出栈时，其标志flag也同时进、出栈。数据类型定义：typedefstruct{BiTree
link;intflag;}stacktype;1voidNRPostOrder(BiTreebt)
/非递归后序遍历二叉树bt/2{3stacktypestack[MAXNODE];4
BiTreep;5inttop,sign;6if(bt==NULL)return;7
top=-1 /栈顶位置初始化/8p=bt;9wh
ile(!(p==NULL&&top==-1))10{11if(p!=NULL)
/结点第一次进栈/12{top++;13stack[top].link=p;1
4stack[top].flag=1;15p=p->lchild;
/找该结点的左孩子/16}17else18{p=stack[top].
link;19sign=stack[top].flag;20top--;21
if(sign==1) /结点第二次进栈/22{top++;23
stack[top].link=p;24stack[top].flag=2
; /标记第二次出栈/25p=p->rchild;26}27
else28{29visite(p->data);
/访问该结点数据域值/30p=NULL;31}32}33
}34}6.3.3二叉树的层次遍历算法在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入
队列，依次执行下面操作：(1)队列不空，出队列，取队头元素。(2)访问该元素所指结点。(3)若该元素所指结点的左、右孩
子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。按层次遍历所
得到的结果序列为：ABCDEFG。在下面的层次遍历算法中，二叉树以二叉链表存放，一维数组Queue[MAXNODE]?用以实现队列
，变量front和rear分别表示当前队首元素和队尾元素在数组中的位置。1voidLevelOrder(BiTreebt
) /层次遍历二叉树bt/2{3BiTreeQueue[MAXNODE];4intfro
nt,rear;5if(bt==NULL)return;6front=-1;7rear=0
;8queue[rear]=bt; /根入队列/9while(front!=rear)
/队列不空/10{front++;11visite(queue[front]->data);
/访问队首结点的数据域/12if(queue[front]->lchild!=NULL)/将队首结
点的左孩子结点入队列/13{rear++;14queue[rear]=queue[fr
ont]->lchild;15}16if(queue[front]->rchild!=NULL)
/将队首结点的右孩子结点入队列/17{rear++;18queue[rear]=qu
eue[front]->rchild;19}20}21}6.3.4遍历序列恢复二叉树已知一棵二
叉树的先序序列与中序序列分别为：ABCDEFGHIBCAEDGHFI试恢复该二叉树。下面给出
用C语言描述的该算法。假设二叉树的先序序列和中序序列分别存放在一维数组preod[]?与inod[]?中，并假设二叉树各结点的数据
值均不相同。1voidReBiTree(charpreod[],charinod[],intn,BiTree
root)2{/n为二叉树的结点个数，root为二叉树根结点的存储地址/3if(n<=0)4
root=NULL;5else6PreInOd(preod,inod,1,n,1,
n,&root);7}8voidPreInOd(charpreod[]，charinod[]，inti,
intj,intk,inth，BiTreet)9{/以先序序列preod[i..j]，中序序列inod
[k..h]恢复二叉树t/10t=(BiTNode)malloc(sizeof(BiTNode));11
t->data=preod[i];12m=k;13while(inod[m]!=preod[i
])14m++; /在inod[]中查找preod[i]/15if(m==k)16
t->lchild=NULL17else18PreInOd(preod,inod
,i+1,i+m-k,k,m-1,&t->lchild);/以先序序列preod[i+1..i+m-k],中序序
列inod[k..m-1]恢复二叉树&t->lchild/19if(m==h)20t->r
child=NULL21else22PreInOd(preod,inod,i+m-k+1,j,
m+1,h,&t->rchild);/以先序序列preod[i+m-k+1..j]，中序序列inod[m+1..h]恢
复二叉树&t->rchild/23}练习已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，请
画出这棵二叉树。①由后序遍历特征，根结点必在后序序列尾部（A）；②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（
BDCE），其右部必全部是右子树子孙（FHG）；③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的
右孩子；以此类推。中序遍历：BDCEAFHG后序遍历：DECBHGFABAFBFABFCGDEH（B
DCE）（FHG）（DCE）（HG）重要结论若二叉树中各结点的值均不相同，则：?前序序列+中序序列，
能唯一地确定一棵二叉树?后序序列+中序序列能唯一地确定一棵二叉树?前序序列+后序序列不一定能唯一地确定一棵二叉树6.3
.5遍历二叉树的应用例6.1给定一棵二叉树，我们可以得到它的遍历序列；反过来，给定一棵二叉树的遍历序列，我们也可以创建相应的二
叉链表。这里所说的遍历序列是一种“扩展的遍历序列”。在通常的遍历序列中，均忽略空子树，而在扩展的遍历序列中，必须用特定的元素表示空
子树。例如，图6.17(a)中二叉树的“扩展先序遍历序列”为：AB#D##C##其中用“#”表示空子树。假设二叉树的结点均为一个
字符，从键盘将前序序列AB#D##C##?逐个输入。利用“扩展先序遍历序列”创建二叉链表的算法如下：1voidCreate
BiTree(BiTreebt)2{/先序遍历建立二叉树/3charch;4c
h=getchar();5if(ch==''#'')bt=NULL;6else7
{8bt=(BiTree)malloc(sizeof(BiTNode));9(bt)
->data=ch;10CreateBiTree(&((bt)->LChild));/先序遍历建立左
子树/11CreateBiTree(&((bt)->RChild));/先序遍历建立右子树/12
}13}例6.2统计二叉树中叶子结点数目。1voidCountleaf(BiTreeroot)2
{/LeafCount是保存叶子结点数目的全局变量，调用之前初始化值为0/3if(root!=NULL)4
{5Countleaf(root->LChild);6Countleaf(r
oot->RChild);7if(root->LChild==NULL&&root->RChild==
NULL)8LeafCount++;9}10}例6.3在二叉链表中查找数据
元素。函数Search(bt，x)的功能是在二叉链表bt中查找数据元素x。查找成功时返回该结点的指针；查找失败时返回空指针。算法实
现如下：1BiTreeSearch(BiTreebt，datatypex)2{/在bt为根结点指针的二
叉树中查找数据元素x/3BiTreep;4if(bt->data==x)returnbt;
/查找成功返回/5if(bt->lchild!=NULL)return(Search(bt->lchild
,x));/在bt->lchild为根结点指针的二叉树中查找数据元素x/6if(bt->rchild!=NUL
L)return(Search(bt->rchild,x));/在bt->rchild为根结点指针的二叉树中查找数据元素x
/7returnNULL;/查找失败返回/8}^FDAGCBE^^^^^^^在n个
结点的二叉链表中，有n+1个空指针域二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？——可以用它来存放当前结点的直
接前驱和后继等线索，以加快查找速度。线索化二叉树思考线索化二叉树普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继
只能在遍历过程中获得若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树可能是根、或最左（右
）叶子例如中序遍历结果：BDCEAFHG，实际上已将二叉树转为线性排列，显然具有唯一前驱和唯一后继！6.4线索二
叉树1线索二叉树的定义按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排列为一个线性序列。n个结点的二叉链表中共有n
+1个空链域。指向直接前驱结点和指向直接后继结点的指针被称为线索（thread），加了线索的二叉树称为线索二叉树。2线索二叉
树的结构方法一：为了区分孩子结点和前驱、后继结点，为结点结构增设两个标志域，如下所示：LChildLtagDataRtagRC
hildLtag0指示孩子＝Rtag1指示前驱,后继指向前驱和后继结点的指针叫做线索；以这种结构组成的二叉链表作
二叉树的存储结构，叫做线索链表；对二叉树以某种次序进行遍历并且加上线索的过程叫做线索化；线索化了的二叉树称为线索二叉树。举例
：方法二：不改变结点结构，仅在作为线索的地址前加一个负号，即负的地址表示线索，正的地址表示指针。本书采用第一种方法介绍线索二叉树
的存储线索化二叉树增加两个域：fwd和bwd；两种解决方法利用空链域（n+1个空链域）如何保存这类信息？线索二叉树的结点结构描述用
C语言如下：typedefchardatatype;typedefstructBiThrNode{datatyped
ata;structBiThrNodelchild;structBiThrNoderchild;unsigned
ltag;unsignedrtag;}BiThrNodeType,BiThrTree;1)建立一棵中序线索二叉树
下面是建立中序线索二叉树的递归算法，其中pre为全局变量。1intInOrderThr(BiThrTreehead,
BiThrTreeT)2{/中序遍历二叉树T，并将其中序线索化，head指向头结点。/3if(!(
head=(BiThrNodeType)malloc(sizeof(BiThrNodeType))))return0;4
(head)->ltag=0;(head)->rtag=1; /建立头结点/5(he
ad)->rchild=head; /右指针回指/6if(!T)7
(head)->lchild=head;/若二叉树为空，则左指针回指/8else9
{(head)->lchild=T;pre=head;10InThreading(T);
/中序遍历进行中序线索化/11pre->rchild=head;pre-
>rtag=1; /最后一个结点线索化/12(head)->rchild=pre;13}1
4return1;15}16voidInTreading(BiThrTreep)17{/中序
遍历进行中序线索化/18if(p)19{InThreading(p->lchild);
/左子树线索化/20if(!p->lchild) /前驱线索/21
{p->ltag=1;22p->lchild=pre;23}24
if(!pre->rchild) /后继线索/25{pre->rtag=1
;26pre->rchild=p;27}28pre=p;29
InThreading(p->rchild); /右子树线索化/30}31}语句20～语句2
3：if(!p->lchild)表示如果某结点的左指针为空，因为其前驱刚刚访问过，赋值给pre，所以可以将pre赋值给p->lch
ild，并修改p->ltag=1，即可完成前驱结点的线索化。语句24～语句27：对pre结点的指针进行判断，if(!pre->r
child)表示如果为空，则p就是pre的后继，做pre->rtag=1;pre->rchild=p;完成后继结点的线索化。线
索化二叉树1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱(即线索)；2）若结点有右子树，则r
child指向其右孩子；否则，rchild指向其直接后继(即线索)。为了避免混淆，增加两个标志域lchildLTagdata
RTagrchild线索化二叉树lchildLTagdataRTagrchildLTag:若LTag=0,lchild域指
向左孩子；若LTag=1,lchild域指向其前驱。RTag:若RTag=0,rchild域指向右孩子；若RTa
g=1,rchild域指向其后继。TABBDCE先序序列：ABCDElchildLTagdata
RTagrchildAECD先序线索二叉树LTag=0,lchild域指向左孩子LTag=1,lchi
ld域指向其前驱RTag=0,rchild域指向右孩子RTag=1,rchild域指向其后继001010^1111中序线索二
叉树TABBDCE中序序列：BCAEDlchildLTagdataRTagrchil
dAECD00^^10101111后序线索二叉树TABBDCE后序序列：CBEDAlchildLTag
dataRTagrchildAECD001010^1111线索化二叉树的几个术语线索：指向结点前
驱和后继的指针线索链表：加上线索二叉链表线索二叉树：加上线索的二叉树（图形式样）线索化：对二叉树以某种次序遍历使其变为线索二叉树的
过程练习ArootCBGFEDIH画出以下二叉树对应的中序线索二叉树。该二叉树中序遍历结果为:H,D,I,B,E,A
,F,C,G悬空？为避免悬空态，应增设一个头结点悬空？root--00A00CB00001GFE1D111010H11I11
对应的中序线索二叉树存储结构如图所示：注：此图中序遍历结果为:H,D,I,B,E,A,F,C,G练习282
533NILNIL4060085455画出与二叉树对应的中序线索二叉树因为中序遍历序列是：5540256028083
354对应线索树应当按此规律连线，即在原二叉树中添加虚线。ACBFGEDHI6.5树和森林6.5.1树和森林的定义树（Tr
ee）是n（n≥0）个有限数据元素的集合。根当n==0时，称这棵树为空树。当n>0时，（1）有一个数据元素称为树的根结点，根结点
没有前驱。（2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（
1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。子树T2子树T1ACBCFGEDHI树的定义还可形式化的
描述为二元组的形式：T＝（D，R）ADTTree数据对象：D={t|t∈D}数据关系：R：若D中仅含有一个数据
元素，则R为空集否则R={H}，H是如下的二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下没有前驱。
(2)除root以外，D中每个结点在关系H下都有且仅有一个前驱。树的特点：（1）根结点没有前驱结点，除根结点之外的所有结
点有且只有一个前驱结点。（2）树中所有结点可以有零个或多个后继结点。概念：在二叉树中介绍的有关概念在树中仍然适用。有序树和无
序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，则称为无序树。森林（forest）：零棵或有限棵不相交
的树的集合称为森林。任何一棵树，删去根结点就变成了森林。ACBCFGEDHIAsTCBC…….FGEDHI根结点双亲结点树的基本
操作X结点X结点B的右兄弟（1）Initiate(t)：初始化一棵空树t。（2）Root(x)：求结点x所在树的根结点。（3）Pa
rent(t，x)：求树t中结点x的双亲结点。（4）Child(t，x，i)：求树t中结点x的第i个孩子结点。（5）RightSi
bling(t，x)：求树t中结点x的第一个右边兄弟结点。（6）Insert(t，x，i，s)：把以s为根结点的树插入到树t中作为
结点x的第i棵子树。（7）Delete(t，x，i)：在树t中删除结点x的第i棵子树。（8）Tranverse(t)：是树的遍历操
作，即按某种方式访问树t中的每个结点，且使每个结点只被访问一次。序号dataparent012345678
ACBCFGEDHI6.5.2树的存储结构1.双亲表示法用一组连续的空间来存储树中的结点，同时附设一个指示器来指示其双亲
结点在表中的位置。DataParentABCDEFGHI-100111244序号dataparent01
2345678ACBCFGEDHI#defineMAXNODE<结点的最大个数>typedefstruct{dataty
pedata;intparent;}NodeType;NodeTypet[MAXNODE];操作
分析：Parent(t,x)操作Root(x)操作Child(t,x,i)操作ABCDEFGHI-100111244AC
BCFGEDHI2.孩子表示法1）多重链表法#defineMAXSON<树的度数>typedefstructTree
Node{datatypedata;structTreeNodeson[MAXSON];}NodeType;操
作分析：Parent(t,x)操作Root(x)操作Child(t,x,i)操作ACBCFGEDHI2）孩子链表表示法把
每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。n个结点共有n个孩子链表n个结点的数据和n个孩子链表的头指针又组成一
个顺序表。#defineMAXNODE<树中结点的最大个数>typedefstructChildNode
/孩子结点/{intchildcode; /孩子结点在数组中的下标/str
uctChildNodenextchild; /指向下一个孩子结点/}typedefstruct
/表头结点/{datatypedata; /结点的数据域
/structChildNodefirstchild; /指向第一个孩子结点/}NodeType;type
defstruct /树结构/{NodeTypenodes[MAXNODE]; /结
点数组/intr,n; /根结点r的位置和结点数n/}Ctree;操作分析：Parent
(t,x)操作Root(x)操作Child(t,x,i)操作ACBCFGEDHI3.双亲孩子表示法是将双亲表示法和孩子
表示法相结合双亲孩子表示法ACBCFGEDHI4.孩子兄弟表示法(树的二叉链表表示法)typedefstructTreeNo
de{datatypedata;structTreeNodeFirstChild;structTreeNode
Nextsibling;}NodeType;方法：每个结点除其信息域外，两个指针分别指向该结点的第一个孩子和下一个兄弟。孩
子兄弟表示法5.树、森林与二叉树的转换1）树转换为二叉树方法：①树中所有相邻兄弟之间加一条连线。②对树中的每个结点，只保
留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。③以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层
次分明。ABCDCEFGDFG2）森林转换为二叉树方法：①将森林中的每棵树转换成相应的二叉树。②第一棵二叉树不动，从第二
棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到
的二叉树。GACHIBDEFJK森林转换为二叉树的过程演示：ACGCDBHDEGIJEHFKIFJK二叉树树对应存储存
储解释解释3)二叉树转换为树和森林方法：①若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点
的双亲结点用线连起来；②删去原二叉树中所有的双亲结点与右孩子结点的连线；③整理由①、②两步所得到的树或森林，使之结构层次分
明。AEBAEGFGCBCDFIKIDK6.5.3树和森林的遍历1.树的遍历1）先根遍历若树为空，遍历结束。否则：①访
问根结点；②按照从左到右的顺序先根遍历根结点的每一棵子树。A结果为：ABEFCDGDBCGEF2）后根遍历若树为
空，遍历结束。否则：①按照从左到右的顺序后根遍历根结点的每一棵子树。②访问根结点；A结果为：EFBCGDADBC
GEF2.森林的遍历1）前序遍历若森林为空，遍历结束。否则：①访问森林中第一棵树的根结点；②前序遍历第一棵树的根结点的子树森
林；③前序遍历去掉第一棵树后的子森林。GACHIBDEFJK前序遍历：ABCDEFGHJIK2）中序遍历
若森林为空，遍历结束。否则：①中序遍历第一棵树的根结点的子树森林；②访问森林中第一棵树的根结点；③中序遍历去掉第一棵树后的子
森林。GACHIBDEFJK中序遍历：BADEFCJHKIG3）后序遍历若森林为空，遍历结束。否则：①
后序遍历森林中第一棵树的根结点的子树森林。②后序遍历除去第一棵树之后剩余的树构成的森林。③访问第一棵树的根结点。GACH
IBDEFJK后序遍历：BFEDJKIHGCA6.5哈夫曼树及其应用例如，要编制一个将百分制转换为五级
分制的程序。if(a<60)b=〝bad〝;elseif(a<70)b=〝pass〝；elseif(a
<80)b=〝general〝；elseif(a<90)b=〝good〝；elseb=〝excellent〝
;在实际中，学生的成绩在五个等级上的分布是不均匀的，假设其分布规律如下表所示：分数0－5960－6970－
7980－8990－100比例数0.050.150.40
0.300.10游戏中主角的生命值d，有这样的条件判定：当怪物碰到主角后，怪物的反应遵从下规则:if(d<1
00)state=嘲笑，单挑;elseif(d<200)state=单挑;elseif(d<300)state=嗜血
魔法;elseif(d<500)state=呼唤同伴;elsestate=逃跑;分析主角生命值d的特点，即预测出每种条
件占总条件的百分比，将这些比值作为权值来构造最优二叉树（哈夫曼树），作为判定树来设定算法。提高效率if(d>=200)&&(d<
300)state=嗜血魔法;elseif(d>=300)&&(d<500)state=呼唤同伴;elseif(d>=
100)&&(d<200)state=单挑;elseif(d<100)state=嘲笑，单挑;elsestate=逃跑
;if(d<100)state=嘲笑，单挑;elseif(d<200)state=单挑;elseif(d<300)s
tate=嗜血魔法;elseif(d<500)state=呼唤同伴;elsestate=逃跑;哈夫曼树应用实例－－哈夫
曼编码在远程通讯中，要将待传字符转换成二进制的字符串，怎样编码才能使它们组成的报文在网络中传得最快？ABACCDA00001101
0000110010101100出现次数较多的字符采用尽可能短的编码哈夫曼树应用实例－－哈夫曼编码ABACCDA000011010
0000AAAAABABB重码关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀－前缀编
码A—0B—110C—10D—1110110010101110ABACCDA采用二叉树设计前缀编码10A10C左分支用“0”右
分支用“1”01BD哈夫曼编码的译码过程分解接收字符串：遇“0”向左，遇“1”向右；一旦到达叶子结点，则译出一个字符，反复由根出发
，直到译码完成。011001010111010A10C01BDABACCDA特点：每一码都不是另一码的前缀，绝不会错译!称为前缀
码哈夫曼树的构造acbnWPL=?wklkgfk=1ed路径：路径长度：带权路径长度：树的带权路径长度：哈夫曼
树：由一结点到另一结点间的分支所构成路径上的分支数目a→e的路径长度＝2结点到根的路径长度与结点上权的乘积树中所有叶子结点的带权
路径长度之和带权路径长度最小的树权值分别为7，5，2，4，构造有4个叶子结点的二叉树abcd4752c27a4d5bab24cd7
5WPL=73+53+21+42=46WPL=72+52+22+42=36WPL=71+52+23+43=
35哈夫曼树的构造过程187777722222444441155555aaaaabbbbbcccccddddd6基本思想：使权大的
结点靠近根操作要点：对权值的合并、删除与替换，总是合并当前值最小的两个ACBCFGEDHI6.6.1哈夫曼树1.路径和路径
长度路径：从一个结点到另一个结点之间的分支序列.路径长度：从一个结点到另一个结点所经过的分支数目。524612.结点的
权和带权路径长度实际应用中，人们常常给树的每个结点赋予一个具有某种实际意义的实数，称该实数为这个结点的权。把从树根到某一结点
的路径长度与该结点的权的乘积，叫做该结点的带权路径长度。H：363.二叉树的带权路径长度设二叉树具有n个带权值的叶结点
，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度，记为：其中n为叶子结点的个数，wi为第i
个叶子结点的权值，li为第i个叶子结点的路径长度。WPL＝2×2＋4×2＋5×2＋3×2＝28。4.哈夫曼树的概念哈夫曼（H
affman）树，也称最优二叉树，是指对于一组带有确定权值的叶结点，构造具有最小带权路径长度的二叉树。如何找到带权路径长度最小的二
叉树（即哈夫曼树）呢？根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越
远离根结点。特点：值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。例如：以(1，3，5，7)为叶子构造二叉树：这
五棵树的带权路径长度分别为：a）WPL＝1×2＋3×2＋5×2＋7×2＝32b）WPL＝1×3＋3×3＋5×2＋7×1＝29
c）WPL＝1×2＋3×3＋5×3＋7×1＝33d）WPL＝7×3＋5×3＋3×2＋1×1＝43e）WPL＝7×1＋5×2＋3
×3＋1×3＝295.哈夫曼树的构造：（1）用给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,
T2,…,Tn}。（2）在F中选择结点权值最小和次小的作为二叉树的左、右子树的根节点，新二叉树的根结点权值为其左右子树的
根结点权值之和。（3）从F中删除被选中的两棵二叉树，同时把新构成的二叉树加入到森林F中。（4）重复(2)、(3)操作，直到
森林中只含有一棵二叉树为止，这棵二叉树就是哈夫曼树。哈夫曼树建立过程38752总结：
给定n个权值，需经过n-1次合并最终能得到一棵哈夫曼树。经过n-1次合并得到n-1个新结点，这n-1个新结点都是具有两个孩子结点的
分支结点。也就是说哈夫曼树中没有度为1的结点。给定n个权值，构造的哈夫曼树共有2n-1个结点。这一点读者可以自行证明。weight
lchildrchildparent哈夫曼树的存储设置结构数组HuffNode保存哈夫曼树中各结点的信息，数组大小设置为2n－
1(具有n个叶结点的哈树共有2n－1个结点)。结构：其中，weight域保存结点的权值lchild和rchild分别保存结点左、
右孩子在数组中序号。weightlchildrchildparent2-1-153-1-155-1-167-1-178-1-175
01610528153482567-1012345678哈夫曼树的构造算法实现weightlchildrchildparentt
ypedefstruct{intweight;intparent;intlchild;intrchild;}
HNodeType0-1-1-13387520-1-1-180-1-1-170-1-1-15
0-1-1-120-1-1-1HNodeTypeHuffNode[m];0-1-1-10-1-1-1voidHaffm
anTree(HNodeTypeHuffNode[]) {3inti,j,m1,m2,n;4s
canf(″%d″,&n); /输入叶子结点个数/5for(i=0;i<2n-1;i
++) /数组HuffNode[]初始化/6{HuffNode[i].weight=0
;7HuffNode[i].parent=-1;8HuffNode[i].lchild=-1;9
HuffNode[i].rchild=-1;10}0-1-1-1weightlchildrchildpare
nt0123456783-1-1-18-1-1-17-1-1-15-1-1-12-1-1-10-1-1-10-1-1-10-1-1
-10-1-1-111for(i=0;ii].weight);/输入n个叶子结点的权值/13for(i=0;i /构造哈夫曼树/14{15select(i-1,m1,m2);/在前n
+i-1中选择两个双亲域为-1且权值最小的结点/16HuffNode[m1].parent=n+i;17
HuffNode[m2].parent=n+i;18HuffNode[n+i].weight=HuffNod
e[m1].weight+HuffNode[m2].weight;19HuffNode[n+i].lchild=m1
;HuffNode[n+i].rchild=m2;20}21}25m25m27101510m17m261555
55578m15m150643877825323m12358103m2218156725字符编码字符编码字符编码字符编码A
0A01A000A00B110B010B010B01C10C001
C100C10D111D10D111D116.6.2哈夫曼树编码在数据通讯中，经常
需要将传送的文字转换成由二进制字符0，1组成的二进制串，我们称之为编码。例如，设传送的电文为ABACCDA(a)编码，代码为00
0010000100100111000，长度为21。(b)编码，代码为00010010101100，长度为14(c)编码，代码
为0110010101110，长度仅为13(d)编码，010100010011001这个存在解码二义性哈夫曼树可用于构造使电
文的编码总长最短的编码方案，且不会产生上述二义性问题。字符staec字符出现的次数3
8752按规定：0左1右，则有0000010110
1123578c
seat设需要编码的字符集合为{d1，d2，…，dn}，它们在电文中出现次数或频率集合为{w1，w2，…，wn}，以d1，d2，…，dn作为叶结点，w1，w2，…，wn作为权值，构造一棵哈夫曼树.规定左分支代表0，右分支代表1，从根到每个叶结点所经过的路径分支组成的0和1的序列为该结点对应字符的编码，称之为哈夫曼编码。下面讨论实现哈夫曼编码的算法。实现哈夫曼编码的算法可分为两大部分：（1）构造哈夫曼树；（2）在哈夫曼树上求叶结点的编码。哈夫曼编码算法:typedefstruct{intbit[MAXBIT];intstart;}HCodeType;1voidHaffmanCode()2{HNodeTypeHuffNode[MAXNODE];3HCodeTypeHuffCode[MAXLEAF],cd;4inti,j,c,p;5HuffmanTree(HuffNode); /建树/for(i=0;i
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
