数据结构课件 第6章 树和二叉树

10086510DataStructure第六章树和二叉树6/29/20231学习目标领会树和二叉树的类型定义，理解树和二叉树的结构差别。熟记二叉树的主要特性，并掌握它们的证明方法。熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。熟练掌握二叉树和树的各种存储结构及其建立的算法。学会编写实现树的各种操作的算法。了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。6/29/20232重点和难点重点：二叉树和树的遍历及其应用。难点：编写实现二叉树和树的各种操作的递归算法。知识点树的类型定义、二叉树的类型定义二叉树的存储表示二叉树的遍历以及其它操作的实现线索二叉树树和森林的存储表示树和森林的遍历以及其它操作的实现最优树和赫夫曼编码6/29/20233树型结构是一类非常重要的非线性数据结构。6/29/202346.1树的定义和基本术语——树(tree)的定义是n(n0)个结点的有限集T；在任意一棵非空树中，有且仅有一个特定的结点，称为树的根(root)；当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。特点：非空树中至少有一个结点——根；树中各子树是互不相交的集合。树的定义是采用递归方法6/29/20235AABCDEFGHIJKLM只有根结点的树有子树的树根子树6/29/20236(a)一棵树结构(b)一个非树结构(c)一个非树结构树中各子树互不相交的含义ACBGFEDHIACBGFDACBGFDE两点①某结点不能同时属于两个子集，如图(b)所示；②两个子集的结点之间不能有关系，如图(c)所示.6/29/20237结点的度：结点所拥有的子树的个数。树的度：树中各结点度的最大值。CGBDEFKLHMIJA6.1树的定义和基本术语——树的基本术语6/29/20238叶子结点：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点。CGBDEFKLHMIJA6.1树的定义和基本术语——树的基本术语6/29/20239孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；兄弟：具有同一个双亲的孩子结点互称为兄弟。

CGBDEFKLHMIJA6.1树的定义和基本术语——树的基本术语6/29/202310路径：如果树的结点序列n1,n2,…,nk有如下关系：结点ni是ni+1的双亲（1<=i<k），则把n1,n2,…,nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。CGBDEFKLHMIJA6.1树的定义和基本术语——树的基本术语6/29/202311祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。CGBDEFKLHMIJA6.1树的定义和基本术语——树的基本术语6/29/202312结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。树的深度：树中所有结点的最大层数，也称高度。1层2层4层3层高度＝4CGBDEFKLHMIJC6.1树的定义和基本术语——树的基本术语6/29/202313CBDEFKLHJA71234568910层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。6.1树的定义和基本术语——树的基本术语6/29/202314有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。数据结构中讨论的一般都是有序树

ACBGFEDACBGFED6.1树的定义和基本术语——树的基本术语6/29/202315CBDEFKLHJ森林：m(m≥0)棵互不相交的树的集合。

A6.1树的定义和基本术语——树的基本术语6/29/202316同构：对两棵树，若通过对结点适当地重命名，就可以使这两棵树完全相等（结点对应相等，结点对应关系也相等），则称这两棵树同构。ACBGFEDDAECFBG6.1树的定义和基本术语——树的基本术语6/29/202317ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点A是结点F，G的祖先结点F，G为堂兄弟6/29/202318树的抽象数据类型的定义ADTTree{数据对象：D是具有相同特性的数据元素的集合。数据关系： 若D为空集，则称为空树； 若D中仅含一个数据元素，则关系R为空集； 若D中含多于一个数据元素，则R={H}，H是如下二元关系：

(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；

(2)当n>1时，其余数据元素可分为m(m>0)个互不相交的(非空)有限

集T1,T2,…,Tm,其中每一个子集本身又是一棵符合本定义的树，

称为根root的子树，每一棵子树的根xi都是根root的后继，即

<root,xi>H，i=1,2,…,m。6/29/202319基本操作：

InitTree(&T);

操作结果：构造空树T。

CreateTree(&T,definition);

初始条件：definition给出树T的定义。

操作结果：按definition构造树T。

DestroyTree(&T);

初始条件：树T存在。

操作结果：销毁树T。

TreeEmpty(T);

初始条件：树T存在。

操作结果：若T为空树，则返回TRUE，否则返回FALSE。6/29/202320

TreeDepth(T);

初始条件：树T存在。

操作结果：返回T的深度。

Root(T);

初始条件：树T存在。

操作结果：返回T的根。

Value(T,cur_e);

初始条件：树T存在，cur_e是T中某个结点。

操作结果：返回cur_e的值。6/29/202321

Parent(T,cur_e);

初始条件：树T存在，cur_e是T中某个结点。

操作结果：若cur_e是T的非根结点，则返回它的双亲，

否则返回“空”。

LeftChild(T,cur_e);

初始条件：树T存在，cur_e是T中某个结点。

操作结果：若cur_e是T的非叶子结点，则返回它的最左

孩子，否则返回“空”。

RightSibling(T,cur_e);

初始条件：树T存在，cur_e是T中某个结点。

操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则

返回“空”。

6/29/202322

TraverseTree(T,visit());

初始条件：树T存在，visit是对结点操作的应用函数。

操作结果：按某种次序对T的每个结点调用函数visit()

一次且至多一次。一旦visit()失败，则操作

失败。

Assign(T,cur_e,value);

初始条件：树T存在，cur_e是T中某个结点。

操作结果：结点cur_e赋值为value。

ClearTree(&T);

初始条件：树T存在。

操作结果：将树T清为空树。6/29/202323

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棵子树。}ADTTree6/29/202324树的表示方法树形表示法：自然界倒长的树；文氏表示法：用集合表示；凹入表示法：类似书目；嵌套括号表示法：广义表表示法。树形文氏ABDCG凹入ABCDG嵌套括号(A(B,C(G),D))6/29/202325树和线性结构对照线性结构树结构存在唯一的没有前驱

的"首元素"存在唯一的没有前驱的

"根结点"存在唯一的没有后继

的"尾元素"存在多个没有后继的

"叶子"其余元素均存在唯一

的"前驱元素"和唯一

的"后继元素"其余结点均存在唯一的

"前驱(双亲)结点"和多

个"后继(孩子)结点"6/29/2023266·2二叉树二叉树的定义是n(n>=0)个结点的有限集，其子树分为互不相交的两个集合，分别称为左子树和右子树，左子树和右子树也是二叉树。ABCDEIJGH根结点左子树右子树6/29/202327二叉树不是树的特例。特点每个结点至多有二棵子树(即不存在度大于2的结点)；二叉树的子树有左、右之分，且其次序不能任意颠倒。基本形态AABABABC空二叉树只有根结点的二叉树右子树为空左子树为空左、右子树均非空6/29/202328斜树1.所有结点都只有左子树的二叉树称为左斜树；2.所有结点都只有右子树的二叉树称为右斜树；3.左斜树和右斜树统称为斜树。1.在斜树中，每一层只有一个结点；2.斜树的结点个数与其深度相同。

几种特殊形式的二叉树斜树的特点：ABCABC6/29/202329几种特殊形式的二叉树满二叉树深度为k且有2k-1个结点的二叉树。特点每一层上的结点数都是最大结点数；所有的分支结点的度数都为2；叶子结点都在同一层次上。1231145891213671014156/29/202330几种特殊形式的二叉树完全二叉树若对满二叉树的结点从上到下从左至右进行编号，则深度为k且有n个结点的二叉树称为完全二叉树，当且仅当其每一个结点都与深度为k的满二叉树的编号从1到n一一对应时。特点叶子结点只可能在层次最大的两层上出现；前k-1层中的结点都是“满”的，且第k层的结点都集中在左边。1231145891267106/29/202331判断是否为完全二叉树，说明理由。1234567123456思考：满二叉树与完全二叉树的关系？6/29/202332在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点6/29/202333二叉树的性质性质1：在二叉树的第i层至多有2i-1个结点(i1)。性质2：深度为k的二叉树至多有2k-1个结点。性质3：对于任何一棵二叉树T，若其终端结点(叶子)数为

n0，度为1的结点数为n1，度为2的结点数n2，

则n0=n2+1。6/29/202334性质4：具有n个结点的完全二叉树的深度是log2n+1。性质5：如果对一棵有n个结点的完全二叉树的结点按层序

编号，则对任一结点i(1in)，有：如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2；如果2i>n，则结点i无左孩子；如果2in，则其左孩子是2i；如果2i+1>n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1。6/29/202335二叉树的存储结构顺序存储结构用一组地址连续的存储单元存储二叉树中的数据元素。完全二叉树，只要从根起按层序存储即可。将完全二叉树上编号为i的结点元素存储在一维数组中下标为i-1的分量中。一般的二叉树，可对照完全二叉树的编号进行相应的存储，但在没有结点的分量中需填充空白字符(例如填充0)。顺序存储表示

#defineMAX_TREE_SIZE100 //最大结点数

Typedef

TElemType

SqBiTree[MAX_TREE_SIZE]; //0号根结点

SqBiTree

bt;6/29/202336深度为4，有12个结点的完全二叉树的顺序存储123451011678912111210987654321

123456789101112没有浪费6/29/202337深度为4，有7个结点的一般二叉树的顺序存储abcdefggf0000edcba

1234567891011浪费4个6/29/202338深度为4，只有4个右孩子的二叉树的顺序存储0000400030002011234123456789101112131415浪费11个6/29/202339顺序存储结构适用于满二叉树和完全二叉树的存储。6/29/202340链式存储结构二叉链表结点除包括元素自身的信息外，还包括指向其左、右子树的指针。即结点要包括数据域，左子树指针域和右子树指针域。二叉链表的存储表示

typedef

struct

BiTNode{

TElemType

data;

struct

BiTNode

*lchild,*rchild;

}BiTNode,*Bitree;

lchilddatarchild6/29/202341ABCDEFGAB

CD

E

F

G^^^^^^^^在n个结点的二叉链表中，有n+1个空指针域。6/29/202342二叉链存储结构的二叉树操作实现

二叉树的初始化算法的基本思想：创建二叉树的头结点。voidInitiate(BiTreeNode**root){ *root=(BiTreeNode*)malloc(sizeof(BiTreeNode)); (*root)->leftChild=NULL; (*root)->rightChild=NULL;}6/29/202343二叉链存储结构的二叉树操作实现

二叉树中给某结点插入一个左结点的操作

算法的基本思想：……BiTreeNode*InsertLeftNode(BiTreeNode*curr,DataTypex){BiTreeNode*s,*t;

if(curr==NULL)returnNULL; t=curr->leftChild; s=(BiTreeNode*)malloc(sizeof(BiTreeNode));s->data=x; s->leftChild=t; s->rightChild=NULL;

curr->leftChild=s; returncurr->leftChild; }6/29/202344二叉链存储结构的二叉树操作实现

删除二叉树中某结点的左子树操作

算法的基本思想：……BiTreeNode*DeleteLeftTree(BiTreeNode*curr){

if(curr==NULL||curr->leftChild==NULL)returnNULL;

Destroy(&curr->leftChild);

curr->leftChild=NULL; returncurr;}6/29/202345三叉链表结点包括数据域，左子树指针域、双亲域和右子树指针域。lchilddataparentrchild三叉链表的存储表示

typedef

struct

TriTNode{

TElemType

data;

struct

TriTNode

*lchild,*rchild,*parent;

}TriTNode,*Tritree;6/29/202346ABC

DEF

G^^^^^^^^^ABCDEFG6/29/2023476.3遍历二叉树遍历是树结构的一种常用的、重要的运算，是树的其它运算的基础。6/29/202348遍历按一定的规律，走遍二叉树的每个结点，使每个结点被访问一次，且只被访问一次。遍历方式按根、左子树、右子树三个部分进行访问；按层次访问；

遍历的过程就是把非线性结构的二叉树中的结点排成一个线性序列的过程。6/29/202349按根、左子树、右子树三个部分进行访问设D表示根结点，L表示左子树，R表示右子树，则对这三个部分进行访问的组合共有6种，DLRDRLLDRLRDRDLRLD若限定先左后右，则只有DLR，LDR，LRD三种，分别称为先序遍历，中序遍历，后序遍历。6/29/202350先序遍历若二叉树为空，则空操作；否则访问根结点：先序遍历左子树；先序遍历右子树。6/29/202351ADBCDLRADLRDLR>B>>D>>CDLR先序遍历序列：ABDC6/29/202352算法6.1先序遍历的递归算法StatusPreOrderTraverse(BiTreeT，Status(*visit)(TElemTypee)){

//采用二叉链表存储结构，visit是对元素操作的应用函数，

//先序遍历二叉树T的递归算法，对每个数据元素调用函数visit。

//最简单的visit函数是输出元素的值。

if(T){

visit(T->data)；

PreOrderTraverse(T->lchild,visit)；

PreOrderTraverse(T->rchild,visit);}//if}//PreOrderTraverse6/29/202353ABCDGEFH先序遍历：ABDGCEFH6/29/202354中序遍历若二叉树为空，则空操作；否则中序遍历左子树；访问根结点；中序遍历右子树。6/29/202355ADBCLDRBLDRLDR>A>>D>>CLDR中序遍历序列：BDAC6/29/202356中序遍历的递归算法StatusInOrderTraverse(BiTreeT，Status(*visit)(TElemTypee)){

//采用二叉链表存储结构，visit是对元素操作的应用函数，

//中序遍历二叉树T的递归算法，对每个数据元素调用函数visit。

//最简单的visit函数是输出元素的值。

if(T){

InOrderTraverse(T->lchild,visit)；

visit(T->data)；

InOrderTraverse(T->rchild,visit)；

}//if}//InOrderTraverse6/29/202357DGBAECH中序遍历：ABCDGEFHF6/29/202358后序遍历若二叉树为空，则空操作；否则后序遍历左子树；后序遍历右子树；访问根结点。6/29/202359ADBCLRDLRDLRD>A>>D>>CLRD后序遍历序列：DBCAB6/29/202360ABCDGEFH后序遍历：CGFDHBEA6/29/202361后序遍历的递归算法StatusPostOrderTraverse(BiTreeT，Status(*visit)(TElemTypee)){

//采用二叉链表存储结构，visit是对元素操作的应用函数，

//先序遍历二叉树T的递归算法，对每个数据元素调用函数visit。

//最简单的visit函数是输出元素的值。

if(T){

PostOrderTraverse(T->lchild,visit);

PostOrderTraverse(T->rchild,visit); visit(T->data);}//if}//InOrderTraverse6/29/202362三种遍历算法的比较相同点：如果把访问根结点这个不涉及递归的语句抛开，则三个递归算法走过的路线是一样的。6/29/202363三种遍历算法的比较不同点：前序遍历是每进入一层递

归调用时先访问根结点，

然后再依次向它的左、右

子树执行递归调用；中序遍历是在执行完左子

树递归调用后再访问根结

点，然后向它的右子树递

归调用；后序遍历则是在从右子树

递归调用退出后访问根结

点。6/29/202364实例1：统计二叉树中叶子结点的个数算法思想：对二叉树“遍历”一遍，并在遍历过程中对“叶子结点计数”

即可。为了在遍历的同时进行计数，在算法的参数中设

一个“计数器”。这个遍历的次序可以随意，即先序或中

序或后序均可。voidCountLeaf(BiTreeT,int&count){

//先序遍历二叉树，以count返回二叉树中叶子结点的数目

if(T){if((!T->Lchild)&&(!T->Rchild))

count++;

CountLeaf(T->Lchild,count);

CountLeaf(T->Rchild,count);}//if}//CountLeaf6/29/202365实例2：求二叉树的深度算法思想：深度为树中叶子结点所在层次的最大值。

结点的层次需从根结点起递推，根结点为第一层。

需要在先序遍历二叉树的过程中求每个结点的层次数，并

将其中的最大值设为二叉树的深度。算法一：voidBiTreeDepth(BiTreeT,intlevel,int&depth){

//T指向二叉树的根，level为T所指结点所在层次，

//其初值为1，depth为当前求得的最大层次,其初值为0if(T){if(level>depth)depth=level;

BiTreeDepth(T->Lchild,level+1,depth);

BiTreeDepth(T->Rchild,level+1,depth);}//if}//BiTreeDepth6/29/2023666/29/202367算法二：int

depth(BitreeT){ if(T==NULL)return0; else{ h1=depth(T->lchild); h2=depth(T->rchild); returnmax(h1,h2)+1; }}6/29/202368实例3：在二叉树上查询某个结点问题描述假设给定一个和二叉树中数据元素有相同类型的值，在已知二叉树中进行查找，若存在和给定值相同的数据元素，则返回函数值为TRUE，并用引用参数返回指向该结点的指针；否则返回函数值为FALSE。算法的基本思想为：若二叉树为空树，则二叉树上不存在这个结点，返回FALSE；否则，和根结点的元素进行比较，若相等，则找到，即刻返回指向该结点的指针和函数值TRUE，从而查找过程结束；否则，在左子树中进行查找，若找到，则返回TRUE；否则，返回在右子树中进行查找的结果。因为右子树上查找的结果即为整个查找过程的结果，即若找到，返回的函数值为TRUE，并且已经得到指向该结点的指针，否则返回的函数值为FALSE。6/29/202369boolLocate(BiTreeT,ElemTypex,BiTree&p){

//存在和x相同的元素，则p指向该结点并返回TRUE，否则p=NULL且返回FALSE

if(!T){

p=NULL;returnFALSE;}

//空树中不存在这样的结点

else{if(T->data==x){

p=T;returnTRUE;}

//找到所求结点elseif(Preorder(T->Lchild,x,p))

returnTRUE;

//在左子树中找到所求结点

elsereturn(Preorder(T->Rchild,x,p)); //返回在右子树

//中查找的结果

}//else}6/29/202370实例4：建立二叉树的存储结构--二叉链表voidCreateBiTree(BiTree&T){//按先序序列输入二叉树中结点的值（一个字符），空格表示空树，//构造二叉链表表示的二叉树T。

scanf(&ch)；

if(ch==‘’)T=NULL;

//建空树

else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))eixt(OVERFLOW);

T->data=ch; //生成根结点

CreateBiTree(T->Lchild); //递归建(遍历)左子树

CreateBiTree(T->Rchild); //递归建(遍历)右子树

}//else returnOK;}//CreateBiTree6/29/202371AB#CD###E#F##6/29/202372实例5：交换二叉树中所有结点的左、右子树。voidexchg_tree(bitreptrBT){

//采用后序遍历的方法，交换每一个结点的左右子树。

if(BT!=null){//非空

exchg_tree(BT->lchild);//交换左子树所有结点指针

exchg_tree(BT->rchild);//交换右子树所有结点指针

p=BT->lchild;//交换根结点左右指针

BT->lchild=BT->rchild;BT->rchild=p; }}6/29/202373实例6：输出后序序列的逆序。voidpreorder(treeT){

//输出后序序列的逆序

if(T!=NULL){

printf(“%f”,T->data);

preorder(T->rchild);

preorder(T->lchild);

}}6/29/202374递归算法转化为非递归算法递归算法优点形式简洁，可读性好，正确性容易得到证明，可以给程序的编制和调试带来很大的方便。递归算法缺点递归调用比非递归调用消耗的时间与存储空间多，运行的效率较低。所有的递归算法都可转化成相应的非递归算法。将递归算法改成相应的非递归算法需要一个栈来记

录调用返回的路径。通过分析递归调用的执行过程，

并观察栈的变化就可得到相应的非递归算法。6/29/202375statusInOrderTraverse(BiTreeT,status(*visit)(TElemTypee)){

//采用二叉链表存储结构，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)){ //访问结点，向右一步

Pop(S,p);if(!Visit(p->data))returnERROR;

Push(S,p->rchild);

}

} returnOK;}中序遍历二叉树T的非递归算法6/29/202376piP->AABCDEFG6/29/202377piP->AP->BABCDEFG6/29/202378piP->AP->BP->CABCDEFG6/29/202379p=NULLiP->AP->BABCDEFG访问：C6/29/202380piP->A访问：CBABCDEFG6/29/202381piP->AP->D访问：CBABCDEFG6/29/202382piP->AP->DP->E访问：CBABCDEFG6/29/202383访问：CBEpABCDEFGiP->AP->D6/29/202384访问：CBEP=NULLABCDEFGiP->AP->DP->G6/29/202385访问：CBEGpABCDEFGiP->AP->D6/29/202386访问：CBEGDpABCDEFGiP->A6/29/202387pABCDEFGiP->AP->F访问：CBEGD6/29/202388ABCDEFGiP->Ap=NULL访问：CBEGDF6/29/202389pABCDEFGi访问：CBEGDFA6/29/202390ABCDEFGip=NULL访问：CBEGDFA6/29/202391表达式a+b*(c-d)-e/f用二叉树表示-+/a*b-efcd先序遍历：-+a*b-cd/ef波兰式6/29/202392表达式a+b*(c-d)-e/f用二叉树表示-+/a*b-efcd中序遍历：-+a*b-cd/ef中缀表示6/29/202393表达式a+b*(c-d)-e/f用二叉树表示-+/a*b-efcd后序遍历：-+a*b-cd/ef逆波兰式6/29/202394已知一棵二叉树的先序遍历序列为ABECDFGHIJ，中序遍历序列为EBCDAFHIGJ，试画出这颗二叉树。AEBCDFHIGJ6/29/202395已知一棵二叉树的先序遍历序列为ABECDFGHIJ，中序遍历序列为EBCDAFHIGJ，试画出这颗二叉树。AFHIGJBECD6/29/202396已知一棵二叉树的先序遍历序列为ABECDFGHIJ，中序遍历序列为EBCDAFHIGJ，试画出这颗二叉树。AFHIGJBECD6/29/202397已知一棵二叉树的先序遍历序列为ABECDFGHIJ，中序遍历序列为EBCDAFHIGJ，试画出这颗二叉树。AFHIGJBDEC6/29/202398已知一棵二叉树的先序遍历序列为ABECDFGHIJ，中序遍历序列为EBCDAFHIGJ，试画出这颗二叉树。AFHIGJBECD6/29/202399已知一棵二叉树的先序遍历序列为ABECDFGHIJ，中序遍历序列为EBCDAFHIGJ，试画出这颗二叉树。AHIGJBECDF6/29/2023100已知一棵二叉树的先序遍历序列为ABECDFGHIJ，中序遍历序列为EBCDAFHIGJ，试画出这颗二叉树。AHIBECDFGJ6/29/2023101已知一棵二叉树的先序遍历序列为ABECDFGHIJ，中序遍历序列为EBCDAFHIGJ，试画出这颗二叉树。ABECDFGHJI试编写算法实现上述过程。

思考：先序、中序、后序序列中任意给定两个

序列就可以画出该二叉树吗？为什么？6/29/2023102按层次遍历ABECDFGHJI按层次遍历序列：ABFECGDHJI6/29/20231036.4线索二叉树遍历二叉树的实质二叉树遍历的过程，为沿着某一条搜索路径对二叉树中的结点进行一次且仅仅一次访问。也就是按一定规则将一个处于层次结构中的结点排列成一个线性序列之后进行依次访问，这个线性序列或是先序序列、或是中序序列或是后序序列。在这些线性序列中每个结点（除第一个和最后一个外）有且仅有一个直接前驱和直接后继。显然，这种信息是在遍历的动态过程中产生的，如果将这些信息在第一次遍历时就保存起来，则在以后再次需要对二叉树进行"遍历"时就可以将二叉树视作线性结构进行访问操作了。如何保存在遍历过程中得到的前驱和后继信息？6/29/2023104最简单的办法在结点中增加两个指针域分别指向该结点的前驱和后继。缺点：存储结构的存储密度大大降低，浪费。另一种方法（寻求存储结构中的空指针域）灵感：思想：一个含n个结点的二叉链表中有n+1个链域的值为

“NULL”。问题：利用这些空的指针域存放指向前驱和后继的信息。引起混淆。lchilddatarchild是左孩子还是前驱指针？是右孩子还是后继指针？6/29/2023105AB

CD

E

F

G^^^^^^^^6/29/2023106

解决办法：在结点中增加两个标志域。lchildLtagdataRtagrchild

0 lchild域指示结点的左孩子Ltag=

1 lchild域指示结点的前趋

0 rchild域指示结点的右孩子Rtag=

1 rchild域指示结点的后继6/29/2023107线索链表：以这种结点结构构成的二叉链表。线索：指向结点前趋和后继的指针。线索二叉树：加上线索二叉树。线索化：对二叉树以某种次序遍历使其变为线索二叉树

的过程。若某程序中所用二叉树需经常遍历或查找结点在遍历所得线性序列中的前驱或后继，应采用线索链表作存储结构。6/29/2023108先序线索链表和先序线索二叉树ABCDEABDCE先序序列：ABCDE先序线索链表0000111111thrt

0

1先序线索二叉树NIL指向根结点指向序列的最后一个结点最后一个结点的右线索指向头结点6/29/2023109中序线索链表和中序线索二叉树DABCE中序序列：BCAED中序线索链表0000111111ABCDEthrt

0

1中序线索二叉树NILNIL指向根结点指向序列的最后一个结点最后一个结点的右线索指向头结点第一个结点的左线索指向头结点6/29/2023110后序线索链表和后序线索二叉树ABCDEABDCE后序序列：CBEDA后序线索链表0000111111thrt

0

1后序线索二叉树指向根结点指向序列的最后一个结点第一个结点的左线索指向头结点NIL6/29/2023111对二叉树进行中序线索化的算法StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){

//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);

Thrt->Ltag=0;Thrt->Rtag=1; //建头结点

Thrt->rchild=Thrt; //右指针回指

if(!T)Thrt->lchild=Thrt; //若二叉树为空，则左指针回指

else{

Thrt->lchild=T;pre=Thrt;

InThreading(T); //中序遍历进行中序线索化

pre->rchild=Thrt;pre->Rtag=1; //最后一个结点线索化

Thrt->rchild=pre;//头结点的右指针指向遍历的最后一个结点

}returnOK;}//InOrderThreading空指针改为指向前驱或后继的线索1

2

34

5678910116/29/2023112voidInThreading(BiThrtTreep){if(p){

InThreading(p->lchild); //左子树线索化

if(!p->lchild)

{p->Ltag=1;p->lchild=pre;} //前驱线索

if(!pre->rchild)

{pre->Rtag=1;p->rchild=p;} //后继线索

pre=p;

InThreading(p->rchild);}}先序、后序线索化的算法？与中序的区别？123

45

67896/29/2023113在线索二叉树上进行遍历（以中序线索二叉树为例）遍历的关键问题找到访问的第一个结点；根据中序遍历的特点，第一个结点必定是“其左子树为空”的结点。若根结点没有左子树，根结点即为中序遍历访问的第一个结点；若根结点有左子树，第一个结点是其左子树中“最左下的结点”。即从根结点出发，顺指针lchild

找到其左子树直至某个结点的指针lchild

为"线索"止，该结点为中序序列中的第一个结点。找到每个结点在序列中的后继。若结点没有右子树，即结点的右指针类型标志Rtag

为“Thread”，则指针

rchild

所指即为它的后继。若结点有右子树，则它的后继应该是其右子树中访问的第一个结点。应该从它的右子树根出发，顺指针lchild

直至没有左子树的结点为止，该结点即为它的后继。6/29/2023114FJICAHEGBD6/29/2023115FJICAHEGBD另一种遍历方法：找最后一个结点；然后找每个结点的前驱。先序、后序线索二叉树上如何遍历？6/29/2023116对线索二叉树进行中序遍历的算法StatusInOrderTraverse_Tri(BiThrTreeT,Status(*Visit)(TElemTypee)){

//T指向头结点，头结点的lchid指向根结点，

//中序遍历二叉线索树T的非递归算法，对每个数据元素调用函数Visit。

p=T->lchild; //p指向根结点

while(p!=T){ //空树或遍历结束时，p==T while(p->Ltag==0) p=p->lchild; if(!Visit(p->data)) returnERROR;//访问左子树为空的结点

while(p->Rtag==1&&p->rchild!=T){

p=p->rchild; Visit(p->data);//访问后继结点

} p=p->rchild; } returnOK;}123

45

6

7896/29/2023117学习线索化时，有三点必须注意：何种“序”的线索化，是先序、中序还是后序；要“前驱”线索化、“后继”线索化还是“全”线索化；只有空指针处才能加线索；6/29/20231186.5树和森林6.5.1树的存储结构双亲表示法以一组连续的存储空间存放树的结点，每个结点中附设一个指针指示其双亲结点在这连续的存储空间中的位置。形式说明#defineMAX_TREE_SIZE=100;typedef

struct

PTNode{

//结点结构

TElemTypedata;

intparent;

//双亲位置域

}PTNode;typedef

struct{

//树结构

PTNodenodes[MAX_TREE_SIZE];

intr,n;

//根的位置和结点数

}PTree;6/29/2023119abcdefhgiacdefghib-1011244406012345789dataparent优点：找双亲容易。缺点：找孩子难，

需要遍历整个结构。r=0n=96/29/2023120孩子表示法把每个结点的孩子排列起来，看成一个线性表，以单链表存储；令其头指针和结点的数据元素构成一个结点，并将所有这样的结点存放在一个地址连续的存储空间里。形式说明typedef

struct

CTNode{

//孩子结点

intchild;

struct

CTNode*next;

}*ChildPtr;typedef

struct{

ElemTypedata;

//结点的数据元素

ChildPtr

firstchild;

//孩子链表头指针

}CTBox;typedef

struct{

CTBoxnodes[MAX_TREE_SIZE];

intn,r;

//结点数和根的位置

}CTree;6/29/2023121abcdefhgi优点：找孩子容易。缺点：找双亲难，

需要遍历整个结构。acdefghib6012345789datafc

1

2^

3

4^^8

6

7^5^^^^^n=9r=06/29/2023122abcdefhgi优点：找孩子和双亲容易。缺点：存储空间增加。acdefghib

1

2^

3

4^^8

6

7^5^^^^^n=9r=06012345789datafcpar-1011244406/29/2023123孩子兄弟表示法（二叉链表表示法）用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。形式说明typedef

struct

CSNode{

ElemTypedata;

struct

CSNode*firstchild,*nextsibling;

}CSNode,*CSTree;6/29/2023124abcdef

g

h

i^^^^^^^^^^abcdefhgi6/29/2023125优点：便于实现树的各种操作。缺点：破坏了树的层次。abcdefhgiabcdef

g

h

i^^^^^^^^^^6/29/20231266.5.2森林与二叉树的转换ACBED树ABCDE二叉树A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^对应存储存储解释解释6/29/2023127树转换为二叉树的方法加线：在兄弟之间加一连线。抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系。旋转：以树的根结点为轴心，将整树顺时针转45°。ABCDEFGHI6/29/2023128ABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空6/29/2023129森林转换成二叉树的方法将各棵树分别转换成二叉树。将每棵树的根结点用线相连。以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构。ABCDEFGHIJ6/29/2023130ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ6/29/2023131二叉树转换成树的方法加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩

子，……沿分支找到的所有右孩子，都与p的双亲用线连起来。抹线：抹掉原二叉树中双亲与右孩子之间的连线。调整：将结点按层次排列，形成树结构。ABCDEFGHI6/29/2023132ABCDEFGHIABCDEFGHIABCDEFGHI6/29/2023133二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的

所有右孩子间连线全部抹掉，使之变成孤立的二叉树。还原：将孤立的二叉树还原成树。ABCDEFGHIJ6/29/2023134ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ6/29/20231356.5.3

树和森林的遍历树的遍历先根遍历若树不空，则先访问根结点，然后依次从左到右先根遍历根的各棵子树。后根遍历若树不空，则先依次从左到右后根遍历根的各棵子树，然后访问根结点。6/29/2023136ABCDEFGHIJKLMNO先根遍历：后根遍历：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDA转换二叉树的先序遍历转换二叉树的中序遍历6/29/2023137森林的遍历先序遍历

访问森林中第一棵树的根结点；先序遍历第一棵树中的子树森林；先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历

中序遍历第一棵树中的子树森林；访问森林中第一棵树的根结点；中序遍历除去第一棵树之后剩余的树构成的森林。6/29/2023138ABCDEFGHIJ先序遍历：中序遍历：ABCDEFGHIJBCDAFEHJIG转换二叉树的先序遍历转换二叉树的中序遍历6/29/20231396.6哈夫曼树及其应用6.6.1哈夫曼树（最优二叉树---带权路径长度最短的树）基本概念路径：从树中一个结点到另一个结点之间的分支。路径长度：路径上的分支数目称为路径长度。树的路径长度：从树根到每一结点的路径长度之和。256714327134561710完全二叉树是路径长度最短的二叉树6/29/2023140结点的带权路径长度：从该结点到树根之间的路径长度与结点上

的权值的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。通常

记作其中，Wk叶子结点的权值，lk叶子结点的路径长度。dcab2475WPL=7*3+5*3+2*1+4*2=466/29/2023141结点的带权路径长度：从该结点到树根之间的路径长度与结点上

的权值的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。通常

记作其中，Wk叶子结点的权值，lk叶子结点的路径长度。WPL=7*2+5*2+2*2+4*2=36abcd75246/29/2023142结点的带权路径长度：从该结点到树根之间的路径长度与结点上

的权值的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。通常

记作其中，Wk叶子结点的权值，lk叶子结点的路径长度。WPL=7*1+5*2+2*3+4*3=35abcd75246/29/2023143结点的带权路径长度：从该结点到树根之间的路径长度与结点上

的权值的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。通常

记作其中，Wk叶子结点的权值，lk叶子结点的路径长度。加权后路径长度最小的并非是完全二叉树，而是权大的叶子离根最近的二叉树。6/29/2023144哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。例：给定4个叶子结点，其权值分别为{2，3，4，7}，可以构造出形状不同的多个二叉树。

WPL=32WPL=41WPL=302347234774236/29/2023145哈夫曼树的特点：1.权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。2.只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点.

2347WPL=32WPL=41WPL=30234774236/29/2023146构造哈夫曼树的过程（哈夫曼算法）根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令初始权值为wj；在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和；在森林中删除这两棵树，同时将新得到的二叉树加入森林中；重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。

哈夫曼树的形态不是唯一的，但对具有一组权值的各哈夫曼树的WPL是唯一的。6/29/2023147w={5,29,7,8,14,23,3,11}，构造哈夫曼树85311192342291487152958100WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=271w={5,29,7,8,14,23,3,11}w={29,7,8,14,23,11,8}w={29,14,23,11,8,15}w={29,14,23,15,19}w={29,23,19,29}w={29,29,42}w={42,58}w={100}6/29/2023148哈夫曼树应用------判定树等级分数段比例ABCDE0~5960~6970~7980~8990~1000.050.150.400.300.1070a<80YNCa<60EYNABYN80a<90DYN60a<70EADBC哈夫曼树6/29/2023149哈夫曼树应用------判定树等级分数段比例ABCDE0~5960~6970~7980~8990~1000.050.150.400.300.10a<80YNa<60EDYNCa<70YNa<90YNBA70a<80YNCa<60EYNABYN80a<90DYN60a<706/29/20231506.6.2哈夫曼编码背景目前，远距离通信的主要手段是电报，即将需传送的文字转换成由二进制的字符组成的字符串。编码时需要遵循以下原则解码的结果唯一；发送的二进制编码尽可能短。两类二进制编码等长编码：各个字符的编码长度相等。优点：解码简单。缺点：编码长度可能不最短。不等长编码：各个字符的编码长度不等。优点：编码长度尽可能地短。缺点：解码困难。等长编码什么情况下空间效率高？不等长编码什么情况下空间效率高？6/29/2023151例如：传送电文“ABACCDA”等长编码A：00B：01C：10D：11编码结果00010010101100，长度为14位。解码方以两位为一字段解码。不等长编码原则：出现次数较多的字符编码短，次数较少的字符编码长。A：0B：00C：1D：01编码结果000011010，长度为9位。解码方无法解码，因为解码的结果不唯一。6/29/2023152前缀编码任意一个字符的编码都不能是另一个字符的编码的前缀，这种编码称为前缀编码。哈夫曼编码（同时满足代码长度短，且解码唯一）目标：使电文总长最短。以字符出现的次数为权，构造一棵赫夫曼树；将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列，这样得到的编码称为哈夫码编码。哈夫曼编码为前缀编码。以这组编码传送电文可使电文总长最短(对所有其它前缀编码而言)。6/29/2023153vuiywtre

字符集vwertyui频率5297814233110000000111111100100000111011111110100001iuytrewv6/29/2023154哈夫曼解码从哈夫曼树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束。vuiywtre

00000001111111解码：111111100