第5章-树和二叉树

2024年12月28日

数据结构

2024年12月28日

树形结构:线性结构:有唯一的前驱，唯一的后继abcdefghi有唯一的前驱，多个的后继

2024年12月28日

第5章树和二叉树5.1树的定义和基本术语5.2二叉树5.3遍历二叉树与线索二叉树5.4树和森林5.5霍夫曼树及其应用

2024年12月28日

5.1树的定义和基本术语树(Tree)是ｎ(n≥0)个结点的有限集,它或者为空树(n=0)；或为非空树，对于非空树Ｔ:(1)有且仅有一个称之为根的结点(2)除根结点以外的其余结点可分为ｍ(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。

2024年12月28日

树(Tree)是ｎ(n≥0)个结点的有限集,它或者为空树(n=0)；或为非空树，对于非空树Ｔ:(1)有且仅有一个称之为根的结点(2)除根结点以外的其余结点可分为ｍ(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。T1T2T3

2024年12月28日

凹入表示嵌套集合广义表树的其它表示方式

2024年12月28日

结点：即树的数据元素结点的度：结点挂接的子树数树的度：所有结点度中的最大值叶子：度为０的结点称为叶子或终端结点(没有后继)分支结点：度不为０的结点称为分支结点或非终端结点内部结点：除根节点之外的分支结点称为内部节点根：即根结点(没有前驱)基本术语

2024年12月28日

双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该节点称为孩子的双亲。(一个结点的双亲是该节点的直接前驱，孩子是该节点的直接后继)兄弟：同一双亲下的孩子之间互称兄弟。祖先：即从根到该结点所经分支上的所有结点。子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。基本术语

2024年12月28日

结点的层次：从根到该结点的层数（根结点算第一层）。树中任一结点的层次等于其双亲结点的层次加１。堂兄弟：即双亲位于同一层的结点（但并非同一双亲）。树的深度(或高度)：树中结点的最大层次称为树的深度或高度。层次1234基本术语

2024年12月28日

有序树：结点各子树从左至右有序，不能互换（左为第一）无序树：结点各子树可互换位置。基本术语T1T2T3

2024年12月28日

森林：指m棵不相交的树的集合。基本术语例如，删除A后的子树集合

2024年12月28日

ADTTree{数据对象D:数据关系R:基本操作P：}ADTTree若D为空集，则称为空树；//允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据元素的说明D是具有相同特性的数据元素的集合。//至少有15个树的抽象数据类型定义教材p95

2024年12月28日

5.2二叉树普通树（多叉树）若不转化为二叉树，则运算很难实现为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。

2024年12月28日

二叉树基本特点：结点的度小于等于2有序树（子树有序，不能颠倒）二叉树的五种不同形态

2024年12月28日

具有3个结点的二叉树可能有几种不同形态？普通树呢？

练习5种/2种

2024年12月28日

ADTBinaryTree{数据对象D:数据关系R:基本操作P：}ADTBinaryTree若D=Φ，则R=Φ；若D≠Φ，则R={H}；存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据元素的说明④……//关于左子树和右子树的说明D是具有相同特性的数据元素的集合。//至少有20个二叉树的抽象数据类型定义教材p98

2024年12月28日

性质1:在二叉树的第i层上至多有2i-1个结点二叉树的性质提问：第i层上至少有

个结点？性质2:深度为k的二叉树至多有2k-1个结点提问：深度为k时至少有

个结点？1k

2024年12月28日

性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2＋1（即n0=n2+1）

2024年12月28日

北京林业大学信息学院满二叉树：一棵深度为k且有2k-1个结点的二叉树。（特点：每层都“充满”了结点）特殊形态的二叉树完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应只有最后一层叶子不满，且全部集中在左边

2024年12月28日

北京林业大学信息学院满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。满二叉树和完全二叉树的区别

2024年12月28日

北京林业大学信息学院一棵完全二叉树有5000个结点，可以计算出其叶结点的个数是（）。练习2500

2024年12月28日

北京林业大学信息学院性质4:具有n个结点的完全二叉树的深度必为＋1k层nk-1层

2024年12月28日

北京林业大学信息学院性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2。

2024年12月28日

北京林业大学信息学院二叉树的顺序存储实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。

2024年12月28日

北京林业大学信息学院abcde####fg1234567891011abcdefg特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树二叉树的顺序存储

单支树

2024年12月28日

北京林业大学信息学院DATAPARENTLCHILDRCHILD二叉树的链式存储

2024年12月28日

北京林业大学信息学院ABCDEFGABCDEFG^^^^^^^^二叉链表typedef

struct

BiNode{

TElemTypedata;

struct

BiNode*lchild,*rchild;//左右孩子指针}BiNode,*BiTree;lchilddatarchild

2024年12月28日

北京林业大学信息学院分析：必有2n个链域。除根结点外，每个结点有且仅有一个双亲，所以只会有n－1个结点的链域存放指针，指向非空子女结点。空指针数目＝2n－(n-1)=n+1在n个结点的二叉链表中，有

个空指针域练习ABCDEFG^^^^^^^^n+1

2024年12月28日

北京林业大学信息学院三叉链表ABCDEFGABCDEFG^^^^^^^^^lchilddataparentrchildtypedef

struct

TriTNode

{TelemTypedata;

struct

TriTNode

*lchild,*parent,*rchild;

}TriTNode,*TriTree;

2024年12月28日

北京林业大学信息学院5.3遍历二叉树和线索二叉树遍历定义——指按某条搜索路线遍访每个结点且不重复（又称周游）。遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。

2024年12月28日

北京林业大学信息学院DLR遍历规则左子树ROOT右子树DLRLDRLRDDRLRDLRLD子树先左后右先序遍历：若二叉树为空，则空操作，否则

访问根结点(D)

先序遍历左子树(L)

先序遍历右子树(R)DLR——先序遍历LDR——中序遍历LRD——后序遍历先序遍历

2024年12月28日

北京林业大学信息学院ALRBLR先序遍历序列：ABCDEFGH先序遍历ABFCD

EGHCLRDLRELRFLRGLRHLR23456781中序遍历：若二叉树为空，则空操作，否则

中序遍历左子树(L)

访问根结点(D)

中序遍历右子树(R)DLR——先序遍历LDR——中序遍历LRD——后序遍历中序遍历

2024年12月28日

北京林业大学信息学院LARLBR中序遍历序列：BDCEAFHG中序遍历ABFCD

EGHLCRLDRLFRLGRLHR23456781LER后序遍历：若二叉树为空，则空操作，否则

后序遍历左子树(L)

后序遍历右子树(R)访问根结点(D)DLR——先序遍历LDR——中序遍历LRD——后序遍历后序遍历

2024年12月28日

北京林业大学信息学院L

RALRB后序遍历序列：DECBHGFA后序遍历ABFCD

EGHLRCLRD

LRFLRG

LRH

23456781LRE

2024年12月28日

北京林业大学信息学院先序遍历：中序遍历：后序遍历：ABCDEABDECDBEACDEBCA

2024年12月28日

c用二叉树表示算术表达式dbef-*a+/-a+b*(c-d)–e/f

2024年12月28日

c用二叉树表示算术表达式dbef-*a+/-先序遍历–

+a*b–

cd/ef前缀表示中序遍历a+b*c

–

d

–e/f中缀表示后序遍历abcd–*+ef/–后缀表示层序遍历–

+/a

*

efb–cd

2024年12月28日

+*A*/EDCB先序遍历+**/ABCDE前缀表示中序遍历A/B*C*D+E中缀表示后序遍历AB/C*D*E+后缀表示层序遍历+*E*D/CAB用二叉树表示算术表达式

2024年12月28日

北京林业大学信息学院若二叉树中各结点的值均不相同，则：由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。重要结论

2024年12月28日

北京林业大学信息学院练习已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG

和

DECBHGFA，请画出这棵二叉树。①由后序遍历特征，根结点必在后序序列尾部（A）；②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（BDCE），其右部必全部是右子树子孙（FHG）；③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。

2024年12月28日

北京林业大学信息学院中序遍历：BDCEAFHG

后序遍历：DECBHGFAA的左子树:中序:BDCE后序:DECBAA的右子树:中序:FHG后序:HGF

2024年12月28日

北京林业大学信息学院中序遍历：BDCEAFHG

后序遍历：DECBHGFAB的右子树:中序:DCE后序:DECABCDE

2024年12月28日

北京林业大学信息学院中序遍历：BDCEAFHG

后序遍历：DECBHGFAABCDEFGHF的右子树:中序:HG后序:HG

2024年12月28日

北京林业大学信息学院DLRADLRDLR>B>>D>>CDLRADBC先序遍历序列：ABDC遍历的算法实现－先序遍历若二叉树为空，则空操作否则

访问根结点(D)

前序遍历左子树(L)

前序遍历右子树(R)

2024年12月28日

北京林业大学信息学院则三种遍历算法可写出:遍历的算法实现－－用递归形式格外简单！longFactorial(longn){if(n==0)return1;//基本项

elsereturnn*Factorial(n-1);//归纳项}回忆:

2024年12月28日

北京林业大学信息学院StatusPreOrderTraverse(BiTreeT){if(T==NULL)returnOK;//空二叉树

else{

cout<<T->data;//访问根结点

PreOrderTraverse(T->lchild);

//递归遍历左子树

PreOrderTraverse(T->rchild);

//递归遍历右子树

}}

先序遍历算法

2024年12月28日

北京林业大学信息学院StatusPreOrderTraverse(BiTreeT){

if(T==NULL)returnOK;else{

cout<<T->data;

PreOrderTraverse(T->lchild);

PreOrderTraverse(T->rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC

2024年12月28日

北京林业大学信息学院遍历的算法实现－中序遍历若二叉树为空，则空操作否则:

中序遍历左子树(L)

访问根结点(D)

中序遍历右子树(R)ADBCLDRBLDRLDR>A>>D>>CLDR中序遍历序列：BDAC

2024年12月28日

北京林业大学信息学院StatusInOrderTraverse(BiTreeT){

if(T==NULL)returnOK;//空二叉树

else{

InOrderTraverse(T->lchild);

//递归遍历左子树

cout<<T->data;//访问根结点

InOrderTraverse(T->rchild);

//递归遍历右子树

}}

中序遍历算法

2024年12月28日

北京林业大学信息学院遍历的算法实现－后序遍历若二叉树为空，则空操作否则

后序遍历左子树(L)

后序遍历右子树(R)

访问根结点(D)ADBCLRDLRDLRDA>>D>>CLRDB后序遍历序列：DBCA

2024年12月28日

北京林业大学信息学院StatusPostOrderTraverse(BiTreeT){

if(T==NULL)returnOK;//空二叉树

else{

PostOrderTraverse(T->lchild);

//递归遍历左子树

PostOrderTraverse(T->rchild);

//递归遍历右子树

cout<<T->data;//访问根结点

}}

后序遍历算法

2024年12月28日

北京林业大学信息学院StatusPreOrderTraverse(BiTreeT){

if(T==NULL)returnOK;else{

cout<<T->data;

PreOrderTraverse(T->lchild);

PreOrderTraverse(T->rchild);

}}

StatusPostOrderTraverse(BiTreeT){

if(T==NULL)returnOK;else{

PostOrderTraverse(T->lchild);

PostOrderTraverse(T->rchild);

cout<<T->data;}}

StatusInOrderTraverse(BiTreeT){

if(T==NULL)returnOK;else{

InOrderTraverse(T->lchild);

cout<<T->data;

InOrderTraverse(T->rchild);

}}

遍历算法的分析

2024年12月28日

北京林业大学信息学院如果去掉输出语句，从递归的角度看，三种算法是完全相同的，或说这三种算法的访问路径是相同的，只是访问结点的时机不同。AFEDCBG遍历算法的分析AFEDCBG

2024年12月28日

北京林业大学信息学院如果去掉输出语句，从递归的角度看，三种算法是完全相同的，或说这三种算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径上，每个结点经过3次。AFEDCBG第1次经过时访问＝先序遍历第2次经过时访问＝中序遍历第3次经过时访问＝后序遍历遍历算法的分析

2024年12月28日

北京林业大学信息学院AFEDCBG中序遍历二叉树的非递归算法ABDPush(A)Push(B)Push(D)…Pop(D)Push(E)EPop(B)visit(B)visit(D)

2024年12月28日

北京林业大学信息学院AFEDCBGAPop(A)visit(A)Push(C)C中序遍历二叉树的非递归算法…

2024年12月28日

北京林业大学信息学院AFEDCBGC？中序遍历二叉树的非递归算法…voidInOrderTraverse(BiTreeT){//中序遍历二叉树的非递归算法

InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){

push(S,p);p=p->lchild;}else{

pop(S,p);

cout<<p->data;p=p->rchild;}}//while}//InOrderTraverseAFEDCBG中序遍历二叉树的非递归算法

2024年12月28日

北京林业大学信息学院AFEDCBG时间效率:O(n)

//每个结点只访问一次空间效率:O(n)

//栈占用的最大辅助空间遍历算法的分析abdc左单支树时，栈占用的最大辅助空间

2024年12月28日

北京林业大学信息学院ABC二叉树的建立先序序列：ABCABCABCABCABC

2024年12月28日

北京林业大学信息学院二叉树的建立AB##C##ABCABCABCABCABCABC####AB#C###A#BC###A#B#C##

2024年12月28日

北京林业大学信息学院ABCDEFG二叉树的建立先序序列为：

ABC##DE#G##F###ABCDEFG

2024年12月28日

北京林业大学信息学院ABCDEFG二叉树的建立先序序列为：

ABC##DE#G##F###

ABC#D#EFG######

2024年12月28日

北京林业大学信息学院A^B^C^D^E^F^^G^二叉树的建立ABCDEFG先序序列为：

ABC##DE#G##F###

2024年12月28日

北京林业大学信息学院二叉树的建立先序序列为：

ABC##DE#G##F###

ABC#D#EFG######ABCDEFG^^^^^^^^

2024年12月28日

二叉树的建立（算法5.3）voidCreateBiTree(BiTree&T){ //按先序次序输入二叉树中结点的值（一个字符），//创建二叉链表表示的二叉树T charch;

cin>>ch;

if(ch=='#')T=NULL; //递归结束，建空树

else{ T=newBiTNode; T->data=ch;//生成根结点//递归创建左子树

CreateBiTree(T->lchild);

//递归创建右子树

CreateBiTree(T->rchild);

}//else} //CreateBiTree访问节点

2024年12月28日

北京林业大学信息学院复制二叉树计算二叉树深度计算二叉树结点总数二叉树遍历算法的应用

2024年12月28日

北京林业大学信息学院复制二叉树（算法5.4）二叉树遍历算法的应用voidCopy(BiTreeT,BiTree&NewT){if(T==NULL){

NewT=NULL;return;}else{

NewT=newBiTNode;

NewT->data=T->data;

copy(T->lchild,NewT->lchild);

copy(T->rchild,NewT->rchild);}}访问节点

2024年12月28日

北京林业大学信息学院计算二叉树深度（算法5.5）二叉树遍历算法的应用intDepth(BiTreeT){if(T==NULL)return0;else{m=Depth(T->lchild);n=Depth(T->rchild);if(m>n)return(m+1);elsereturn(n+1);}}

2024年12月28日

北京林业大学信息学院计算二叉树结点总数（算法5.6）二叉树遍历算法的应用int

NodeCount(BiTreeT){if(T==NULL)return0;elsereturnNodeCount(T->lchild)+NodeCount(T->rchild)+1;}

2024年12月28日

北京林业大学信息学院二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？——可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。思考线索化二叉树在n个结点的二叉链表中，有n+1个空指针域ABCDEFG^^^^^^^^

2024年12月28日

北京林业大学信息学院空指针域可以用来存放当前结点的直接前驱和后继等线索，以加快查找速度。ABCDEFG^^^^^^^线索化二叉树^先序遍历结果：A

BCDEGF

2024年12月28日

北京林业大学信息学院普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树例如中序遍历结果：BDCEAFHG，实际上已将二叉树转为线性排列，显然具有唯一前驱和唯一后继！可能是根、或最左（右）叶子线索化二叉树

2024年12月28日

北京林业大学信息学院两种解决方法增加两个域：fwd和bwd；利用空链域（n+1个空链域）如何保存这类信息？线索化二叉树

2024年12月28日

北京林业大学信息学院1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱(即线索)；2）若结点有右子树，则rchild指向其右孩子；否则，rchild指向其直接后继(即线索)

。为了避免混淆，增加两个标志域lchildLTagdataRTagrchild线索化二叉树

2024年12月28日

北京林业大学信息学院LTag:若LTag=0,lchild域指向左孩子；

若LTag=1,lchild域指向其前驱。RTag:若RTag=0,rchild域指向右孩子；

若RTag=1,rchild域指向其后继。

lchildLTagdataRTagrchild线索化二叉树

2024年12月28日

北京林业大学信息学院线索：指向结点前驱和后继的指针线索二叉树：加上线索的二叉树（图形式样）线索化二叉树的几个术语先序序列：ABCDEABCDENULL线索链表：加上线索二叉链表线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程

2024年12月28日

北京林业大学信息学院ABCDEABDCET先序序列：ABCDE00001111^11

lchildLTagdataRTagrchild先序线索二叉树LTag=0,lchild域指向左孩子

LTag=1,lchild域指向其前驱RTag=0,rchild域指向右孩子

RTag=1,rchild域指向其后继

先序线索链表

2024年12月28日

北京林业大学信息学院ABCDEABDCET中序序列：BCAED00001111^11^

lchildLTagdataRTagrchild中序线索二叉树中序线索链表

2024年12月28日

北京林业大学信息学院

lchildLTagdataRTagrchildABCDEABDCET后序序列：CBEDA0000111111^后序线索二叉树后序线索链表…………prepprep中序序列12ii+1i+2n中序线索化构造线索化二叉树中序遍历二叉树给pre加上右线索，给p加上左线索算法5.7以结点p为根的子树中序线索化构造线索化二叉树voidInThreading(BiThrTreep){//pre是全局变量，初始化时其//右孩子指针为空，便于在树的//最左点开始建线索if(p){

InThreading(p->lchild);

if(!p->lchild){p->LTag=1;p->lchild=pre;}

if(!pre->rchild){pre->RTag=1;pre->rchild=p;}pre=p;

InThreading(p->rchild);}

2024年12月28日

北京林业大学信息学院ABCGEIDHFroot悬空？悬空？该二叉树中序遍历结果为:

H,D,I,B,E,A,F,C,G画出以下二叉树对应的中序线索二叉树。为避免悬空态，应增设一个头结点练习

2024年12月28日

北京林业大学信息学院对应的中序线索二叉树存储结构如图所示：00A00C00B11E11F11G00D11I11H注：此图中序遍历结果为:H,D,I,B,E,A,F,C,G0--root0

2024年12月28日

北京林业大学信息学院画出与二叉树对应的中序线索二叉树

2825405560330854因为中序遍历序列是：5540256028083354对应线索树应当按此规律连线，即在原二叉树中添加虚线。NILNIL练习

2024年12月28日

北京林业大学信息学院平衡树——排序树——判定树——带权树——最优树——特点：左右子树深度差≤1特点：“左小右大”例如，12个球只称3次分出轻重特点：路径长度带权值带权路径长度最短的树，又称Huffman树，用途之一是通信中的压缩编码。二叉树的应用5.5霍夫曼树

2024年12月28日

北京林业大学信息学院5.4树和森林树的存储结构－－双亲表示法R-1A0B0D1C0F3K6G6H6E10123456789数组下标dataparent

2024年12月28日

北京林业大学信息学院RC

D

E

B

A

FG

H

K

datachild1child2…childd树的存储结构－－孩子表示法多重链表

2024年12月28日

北京林业大学信息学院C1B0A2

datadegreechild1…childdR3F3K0E0G0D0E0树的存储结构－－孩子表示法多重链表data指向孩子链表的指针树的存储结构－－孩子表示法孩子链表双亲

data指向孩子链表的指针树的存储结构－－孩子表示法带双亲的孩子链表

2024年12月28日

北京林业大学信息学院树的存储结构－－二叉链表表示法ABCDEFGRHK二叉树的节点n，n的左孩子是n在树中的第一个孩子，n的右孩子是n在树中右兄弟.树转换为二叉树

2024年12月28日

北京林业大学信息学院树的存储结构－－二叉链表表示法ABCR二叉树的节点n，n的左孩子是n在树中的第一个孩子，n的右孩子是n在树中右兄弟.树转换为二叉树

2024年12月28日

树的存储结构－－二叉链表表示法ABCDEFGRHK二叉树的节点n，n的左孩子是n在树中的第一个孩子，n的右孩子是n在树中右兄弟.树转换为二叉树注意：由于树根没有兄弟，故二叉树的树根没有右孩子

2024年12月28日

北京林业大学信息学院树的存储结构－－二叉链表表示法ABCDEFGRHK二叉树的节点n，n的左孩子是n在树中的第一个孩子，n的右孩子是n在树中右兄弟.ARBCDEFGHK二叉树转换为树

2024年12月28日

北京林业大学信息学院树的存储结构－－二叉链表表示法

对应

2024年12月28日

北京林业大学信息学院树的存储结构－－二叉链表表示法

2024年12月28日

北京林业大学信息学院树的存储结构－－二叉链表表示法

2024年12月28日

树二叉树

对应

存储

解释

解释

2024年12月28日

北京林业大学信息学院树的存储结构－－二叉链表表示法typedef

struct

CSNode{

ElemTypedata;

struct

CSNode

*firstchild,*nextsibling;}CSNode,*CSTree;说明:CS中，C—Child,S—SiblingBACDFEGJHIBACDFEGJHI树与二叉树对应BACDFEGJHI

对应树根相连森林与二叉树的转换－－森林转换为二叉树BACDFEGJHIBACDFEGJHI拆开树根BACDFEGJHI

对应二叉树与树对应森林与二叉树的转换－－二叉树转换为森林树和森林的遍历树的遍历——先序遍历（先根遍历）先访问树的根节点，然后依次先序遍历根的每棵子树。RADEBCFGHK先序序列：RADEBCFGHK先序序列：RADEBCFGHK先序遍历一棵树恰好等价于先序遍历该树对应的二叉树树和森林的遍历树的遍历——后序遍历（后根遍历）先依次后序遍历根的每棵子树。然后访问树的根节点。DEABGHKFCR后序遍历：DEABGHKFCR中序遍历：DEABGHKFCR后序遍历一棵树恰好等价于中序遍历该树对应的二叉树树和森林的遍历树和森林的遍历按照森林和树的相互递归定义，可以推出森林的两种遍历方法。1、树的先序遍历推出森林的先序遍历树和森林的遍历森林的遍历——先序遍历(1)访问森林中第一棵树的根节点(2)先序遍历第一棵树的根节点的子树森林(3)先序遍历除去第一棵树之后剩余的树构成的森林即，依次对每一棵树进行先序遍历。Part2RootPart1BACDFEGJHI树和森林的遍历森林的遍历——先序遍历先序序列：ADCDEFGHIJBACDFEGJHIBACDFEGJHI先序序列：ABCDEFGHIJ先序序列：ABCDEFGHIJ先序遍历森林等同于先序遍历该森林对应的二叉树。树和森林的遍历按照森林和树的相互递归定义，可以推出森林的两种遍历方法。2、树的后序遍历推出森林的中序遍历树和森林的遍历森林的遍历——中序遍历(1)中序遍历森林中第一棵树的根节点的子树森林(2)访问第一棵树的根节点(3)中序遍历除去第一棵树之后剩余的树构成的森林Part2Part1Root即，依次对每一棵树进行后序遍历。BACDFEGJHI树和森林的遍历森林的遍历——中序遍历中序序列：BCDAFEHJIGBACDFEGJHIBACDFEGJHI中序遍历森林等同于中序遍历该森林对应的二叉树。中序序列：BCDAFEHJIG中序序列：BCDAFEHJIG

2024年12月28日

北京林业大学信息学院5.5霍夫曼树及其应用路径：路径长度：带权路径长度：树的带权路径长度：霍夫曼树：由一结点到另一结点间的分支所构成路径上的分支数目结点到根的路径长度与结点上权的乘积debacfg树中所有叶子结点的带权路径长度之和带权路径长度最小的树a→e的路径长度＝2WPL=

wklk

k=1n

2024年12月28日

北京林业大学信息学院dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35abcd7524WPL=7*2+5*2+2*2+4*2=36权值分别为7，5，2，4，构造有4个叶子结点的二叉树

2024年12月28日

北京林业大学信息学院a7b5c2d4a7b5c2d46a7b5c2d411a7b5c2d418a7b5c2d4霍夫曼树的构造过程操作要点：对权值的合并、删除与替换，总是合并当前值最小的两个基本思想：使权大的结点靠近根

2024年12月28日

北京林业大学信息学院根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树。在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。在森林中删除这两棵树，同时将新得到的二叉树加入森林中。重复上述两步，直到只含一棵树为止，这棵树即霍夫曼树。霍夫曼树的构造过程

2024年12月28日

北京林业大学信息学院Ch5_8.ctypedef

struct{int

weght;

intparent;

int

lchild,rchild;}*HuffmanTree;霍夫曼树构造算法的实现（算法5.10）采用顺序存储结构——一维结构数组结点类型定义一棵有n个叶子结点的Huffman树有

个结点2n-1

2024年12月28日

北京林业大学信息学院1)初始化HT[1..2n-1]：lchild=rchild=parent=02)输入初始n个叶子结点：置HT[1..n]的weight值3)进行以下n-1次合并，依次产生HT[i]，i=n+1..2n-1：

3.1)在HT[1..i-1]中选两个未被选过的weight最小的两个结点HT[s1]和HT[s2](从parent=0的结点中选)3.2)修改HT[s1]和HT[s2]的parent值：parent=i3.3)置HT[i]：weight=HT[s1].weight+HT[s2].weight,

lch=s1,rch=s2霍夫曼树构造算法的实现529782314113霍夫曼树的叶节点数n=8,所有节点数m=2n-1=15已知w=(5,29,7,8,14,23,3,11),试构造一棵霍夫曼树.1)初始化HT[1..2n-1]：lchild=rchild=parent=0529782314113n=82)输入初始n个叶子结点：置HT[1..n]的weight值529782314113n=8

2024年12月28日

北京林业大学信息学院3)进行以下n-1次合并，依次产生HT[i]，i=n+1..2n-1：

3.1)……3.2)……3.3)……霍夫曼树构造算法的实现iiiiiii529782314113100292914781558428115319235297823141132978231411538结点iweightparentlchildrchild1500229000370004800051400062300073008110009010-000…………099i801700-3)进行以下n-1次合并，依次产生HT[i]，i=n+1..2n-1：

3.1)在HT[1..i-1]中选两个未被选过的weight最小的两个结点HT[s1]和HT[s2](从parent=0的结点中选)s2s13)进行以下n-1次合并，依次产生HT[i]，i=n+1..2n-1：

3.2)修改HT[s1]和HT[s2]的parent值:

HT[s1].parent=i,HT[s2].parent=i3)进行以下n-1次合并，依次产生HT[i]，i=n+1..2n-1：

3.3)置HT[i]：

HT[i].lchild=s1,HT[i].rchild=s2

HT[i].

weight=HT[s1].weight+HT[s2].weight

2978231411538结点iweightparentlchildrchild15900229000370048005140006230007390081100098017100…………01010415300-29782314115382923141153878150is2s13)进行以下n-1次合并，依次产生HT[i]，i=n+1..2n-1：

3.1)在HT[1..i-1]中选两个未被选过的weight最小的两个结点HT[s1]和HT[s2](从parent=0的结点中选)3)进行以下n-1次合并，依次产生HT[i]，i=n+1..2n-1：

3.2)修改HT[s1]和HT[s2]的parent值：

HT[s1].parent=i,HT[s2].parent=i3)进行以下n-1次合并，依次产生HT[i]，i=n+1..2n-1：

3.3)置HT[i]：

HT[i].lchild=s1,HT[i].rchild=s2，

HT[i].weight=HT[s1].weight+HT[s2].weight

结点iweightparentlchildrchild15900229000371000481000514000623000739008110098171015034110…………01111819900-2923141153878150292314781511538193)进行以下n-1次合并，依次产生HT[i]，i=n+1..2n-1：

3.1)在HT[1..i-1]中选两个未被选过的weight最小的两个结点HT[s1]和HT[s2](从parent=0的结点中选)is2s13)进行以下n-1次合并，依次产生HT[i]，i=n+1..2n-1：

3.2)修改HT[s1]和HT[s2]的parent值：

HT[s1].parent=i,HT[s2].parent=i3)进行以下n-1次合并，依次产生HT[i]，i=n+1..2n-1：

3.3)置HT[i]：

HT[i].lchild=s1,HT[i].rchild=s2，HT[i].weight=HT[s1].weight+HT[s2].weight

2024年12月28日

算法voidCreatHuffmanTree(HuffmanTree

HT,intn){if(n<=1)return;m=2*n-1;HT=newHTNode[m+1];//0号单元未用，HT[m]表示根结点

for(i=1;i<=m;++i){HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;}for(i=1;i<=n;++i)cin>>HT[i].weight;

weightparentlch

ildrchild1．．．８９．．15529781423311000000000000000例:设n=8,w={5,29,7,8,14,23,3,11}试设计huffmancode(m=2*8-1=15)000000000000000000000000000000

2024年12月28日

北京林业大学信息学院for(i=n+1;i<=m;++i)//构造Huffman树

{

Select(HT,i-1,s1,s2);

//在HT[k](1≤k≤i-1)中选择两个其双亲域为0,

//且权值最小的结点,

//并返回它们在HT中的序号s1和s2HT[s1].parent=i;HT[s2].parent=i;

//表示从F中删除s1,s2

HT[i].lchild=s1;HT[i].rchild=s2;

//s1,s2分别作为i的左右孩子

HT[i].weight=HT[s1].weight+HT[s2].weight;

//i的权值为左右孩子权值之和

}}100292914781558428115319238115319529782314113297823141153815782923141153815782923142914781581153192923428115319232914781529292914781558428115319231002929147815584281153192310029291478155842811531923注意：按程序构造出的赫夫曼树是唯一的!100292914781558428115319230010111111000000011001111111111011010字符的赫夫曼编码算法的实现已知某系统在通信联络中只可能出现8种字符,其概率分别为:0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,试设计哈夫曼编码.首先,用赫夫曼算法求以概率(乘以100)为权的最优2元树.这里w=(5,29.7.8.14,23,3,11).然后,对每个字符进行编码.1.a(0.05,5):01102.b(0.29,29):103.c(0.07,7):11104.d(0.08,8):11115.e(0.14,14):1106.f(0.23,23):007.g(0.03,3):01118.h(0.11,11):010010100292914781558428115319230010111111000000010011001111111111011010iiiiiiii//逐个字符求赫夫曼编码for(i=1;i<=n;++i){ //求出第i个字符的编码}字符的霍夫曼编码算法的实现100292914781558428115319230111111010029291478155842811531923cfcfccff11101110c=i;f=i的双亲节点;

while(f是树中结点){

if(f的左孩子==c)生成代码0else生成代码1;c=f;f=f的双亲;//回溯

}

}cf10029291478155842811531923cfcfccff11101110结点iweightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229155101342156111458152121510001314for(i=1;i<=n;++i){c=i;f=HT[i].parent;