页数：90页文件大小：914.2 KB来源： 数据结构与算法ppt课件
本课件讲解树的定义与基本术语，展开二叉树的定义性质与顺序、链式存储，重点给出先序中序后序遍历的递归与非递归算法及中序线索化，随后说明树和森林与二叉树的相互转换，最后讲赫夫曼树的构造与赫夫曼编码。
第六章树和二叉树
有关树的概述
本章目的：树和二叉树存储结构与操作算法、树和森林与二叉树的关系
第一节树的定义和基本术语
(1)树的定义
(2)抽象数据类型树的定义
(3)对应于D－{root}的划分，H-｛< root, x1>，
(3)树的基本术语
以某结点为根的子树中的任一结点都称为该结点的子孙
第二节二叉树
(1)二叉树定义
(2)抽象数据类型二叉树
基本操作：
(3)二叉树的性质
性质2深度为k的二叉树至多有2k－1个结点（k≥1）证明：由性质1，可得深度为k的二叉树最大结点数是(3)二叉树的性质(续)123456789101112
性质3对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1证明：设n1为二叉树T中度为1的结点数,则二叉树中结点总数为: n=n0+n1+n2∵二叉树中，除根结点外，其余结点都只有一个分支进入,设B为分支总数，则n=B+1又∵分支由度为1和度为2的结点射出，B=n1+2n2于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1(3)二叉树的性质(续)
(3)二叉树的性质(续)241132367567458910111213141589101112
性质4具有n个节点的完全二叉树的深度为[log2n]+1证明：假设深度为k，则根据性质2和完全二叉树的定义有:2k-1-1< n≦2k-1则k-1≦lon2n<kk=log2n+1或2k-1≦n<2k(3)二叉树的性质(续)
性质5如果对一棵有n个结点的完全二叉树（其深度为[log2n]+1）的结点按层序编号（从第1层到第[log2n]+1层，每层从左到右），则对任一结点i（1≤i≤n）有
(4)二叉树的存储结构
760000543211)顺序存储结构234567
特点：
2)链式存储结构
二叉链表存储表示
基本函数
rchilddatalchildABCDEFG在n个结点的二叉链表中，有n+1个空指针域ABDE^^C^^^F^^G^
第三节遍历二叉树和线索二叉树
(1)遍历二叉树
1)基于递规算法的先序遍历(算法6.1)
先序遍历主程序Pre(T)返回返回pre(TR);返回返回pre(TR);TBprintf(B);pre(TL);BTAprintf(A);ATDprintf(D);pre(TL);TCprintf(C);pre(TL);返回T>左是空返回pre(TR);T>T>T>T>C左是空返回右是空返回D左是空返回右是空返回pre(TL);pre(TR);先序序列：ABDCvoidpreorder(JD*bt){if(bt!=NULL){printf("%d\t",bt->data);preorder(bt->lchild);preorder(bt->rchild);}}
//中序遍历
2)三种遍历举例
ADBCDLRADLRDLR>B>>D>>CDLR先序遍历序列：ABDC
ADBCLDRBLDRLDR>A>>>>CLDRD中序遍历序列：BDAC
ADBCLRDLRD>A>>>>CLRDLRDD后序遍历序列：DBCA
递规算法的遍历二叉树应用程序二叉树：char*s="A(B(D,E(H,I)),C(G))";
3)基于非递规算法的遍历算法
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数visit
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数visit
ABCDEFGpiP->A(1)ABCDEFGpiP->BP->A(2)ABCDEFGpiP->CP->BP->A(3)ABCp=NULLDEFGiP->BP->A访问：C(4)
pABCDEFGiP->A访问：CB(5)ABCDEFGiP->DP->A访问：CBp(6)ABCDEFGiP->EP->DP->A访问：CBp(7)ABCDEFGiP->DP->A访问：CBEp(8)演示如下（续）
ABCDEFGiP->GP->DP->A访问：CBEP=NULL(9)ABCDEFGiP->A访问：CBEGDp(11)ABCDEFGiP->FP->A访问：CBEGDp(12)ABCDEFGiP->DP->A访问：CBEGp(10)演示如下（续）
ABCDEGiFp=NULLP->A访问：CBEGDF(13)ABCDEFi访问：CBEGDFApG(14)CDEFGp=NULLABi访问：CBEGDFA(15)演示如下（续）
4)构造二叉树算法//构造二叉链表表示的二叉树T StatusCreateBitree(Bitree&T){ scanf(&ch); if(ch==’‘)T=NULL; else{ if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(overflow); T－>data=ch;CreateBiTree(T－>rchild);returnOk; } 第45页：遍历算法的时间与空间复杂度
遍历二叉树算法的基本操作是访问结点，无任那种遍历，对含n个结点的二叉树，其时间复杂度为O(n)
- 遍历过程中栈的最大容量为树的深度，最坏情况（单支）为n，所以空间复杂度为S(n)
第46页：线索二叉树的问题引出
(2)线索二叉树
- 问题引出：
- 遍历二叉树实质是非线性结构的线性化，且每个结点有且仅有一个直接前驱和直接后继，但二叉链表中没有保留
- 为此可在每个结点上增加两个指针，分别志向他的直接前驱和后继
- n个结点的二叉链表中必定存在n+1个空链域，可以利用这些空域来存放结点的前驱和后继信息
- 结点设计
- 除左、右子树指针外，设置两个标志域:ltag,rtag
- lchild,指向左孩子（ltag=0）或前驱（ltag=1）
- rchild,指向右孩子（rtag=0）或后继（rltag=1）rchildrtagdataltagLchild
第47页：线索与线索化概念
线索链表：当由包含左右标志域和左右树指针域的结点的数据结构构成的二叉链表作为二叉树的存储结构时，称为线索链表
- 线索：指向结点前驱和后继的指针（lchild,rchild）
- 线索二叉树:加上线素的二叉树
- 线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程1)概念rchildrtagdataltagLchild
第48页：线索二叉树举例
2)例:表达式a+b*(c-d)-e/f的线索二叉树中序遍历情况：a+b*c-d-e/f
- 叶结点的左链是线索直接指向前驱，叶结点的右链是线索直接指向后继
- 中间结点无法直接得到前驱和后继，后继结点为右子树的最左下的结点，例如*的后继结点为c；前驱为左子树中最后访问的结点（东华左理子工学树院中程朋最根右下的结点），例如-(根)的前驱结点为d头结点
第49页：线索链表结点结构
Typedefenum{Link,Thread}PointerTag;//Link=0:指针，Thread==1:线索
- typedefstructBiThrNode{TelemTypedata;StructBiThrNode*lchild,*rchild;//左右孩子指针PointerTagLtag,Rtag;
- }BiThrNode，*BiThrTree;
- 二叉树的线索链表增加头结点，并约定：
- lchild指向树的根结点，rchild指向中序遍历时访问的最后一个结点
- 同时中序系列中的第一个结点的lchild和最后一个结点的rchild指向头结点
- 建立双向线索链表，可以从第一个结点起顺后续进行遍历，也可以从最后一个结点起顺前驱进行遍历3)二叉树线索存储结构
第50页：线索链表的遍历算法
4)基于双向线索链表的二叉树遍历算法
- //T指向头结点，头结点的左链lchild指向根结点
- //中序遍历二叉树T的非递归算法，对每个数据元素调用函数visit
- StatusInorderTraverse_Thr(BiThrTreeT, Status(*visit)(Telemtypee)){p=T－>lchild;while(p!=T){//p指向根结点//空树或遍历结束时，p==Twhile(p－>Ltag==Link)p=p－>lchild;//Link=0，向左到尽头if(!Visit(p－>data))returnERROR;//访问其左子树为空的结点while(p－>Rtag==Thread&&p－>rchild!=T){p=p－>rchild;Visit(p－>data);}p=p－>rchild;//访问后继结点}returnOk;
- }//InorderTraverse_Thr第一次-,+,a+*
第51页：中序线索化链表算法
5)中序遍历建立中序线索化链表算法//线索化的过程即为在遍历的过程中修改空指针的过程 Pre始终指向刚刚访问过的结点，若p为当前访问的结点，则pre为p的前驱 StatusInorderThreading(BiThrtree&Thrt,BiThrTreeT){ if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW); Thrt－>Ltag=Link; Thrt－>Rtag=Thread;if(!T)Thrt－>lchild=Thrt; else{ Thrt－>lchild=T//根结点; pre=Thrt;//中序遍历进行中序线索化pre－>rchild=Thrt; pre－>Rtag=Thread;} returnOk; } 第52页：中序线索化的递归实现
//中序遍历进行中序线索化（递归方式）
- voidInThreading(BiTrSTreep){if(p){InThreading(p->1child);//左子树线索化if(!p->1child){p->Ltag=Thread;p->1child=pre;}//当前结点的左子树为空，则建立指向其前驱结点的前驱线索if(!pre->rchild){pre->Rtag=Thread;pre->rchild=p;}//若前驱结点不为空，且其右子树为空，则建立前驱结点指向当前结点的后继线索pre=p;InThreading(p->rchild);//保持pre指向p的驱//右子树线索化}
- }//InTheading6)中序遍历进行中序线索化
第53页：第四节树和森林
第四节树和森林
第54页：树和森林的内容安排
(1)树的存储结构
- (2)森林与二叉树的转换
- (3)树和森林的遍历
第55页：树的存储结构
(1)树的存储结构
- 1)双亲表示法
- 2)孩子表示法
- 3)孩子兄弟表示法返回
第56页：双亲表示法
1)双亲表示法
- 以一组连续空间存储树的结点、每个结点附设一个指针指向其双亲
- #defineMAX_TREE_SIZE100
- typedefstructPTNode{TelemTypedata;intparent;
- }PTNode;
- typedefstruct{//双亲位置域PTNodenodes[MAX_TREE_SIZE];intn;
- }Ptree;
- 特点：//结点数
- 求父结点方便、可以在常量时间内实现
- 求结点的孩子时需要遍历整个结构-1R00A10B20C31D41E53F66G76H86K9RBCDEFGHKA返回
第57页：孩子表示法
2)孩子表示法
- 每个结点有多棵子树、存在多个指针域。保存方法：
- 各结点的结构相同，孩子指针数为树的度，浪费空间
- 各结点的结构不同，节省空间、操作困难
- 每个结点的孩子排列起来，构成n个孩子线性表；每个结点排列起来构成一个线性表，同时采用顺序存储结构
- typedefstructCTNode{//孩子结点intchild;structCTNode*next;
- }*ChildPtr;
- typedefstruct{intdata;ChildPtrfirstchild;
- }CTBox;
- typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//结点数和根的位置；
- }Ctree;//特点：适合对孩子的操作，但不适合对双亲的操作，可设计
- 带双亲的孩子链表K9H8G7F6E5R4D3C2B10A301789256返回
第58页：带双亲的孩子链表
KHGFERDCBA6968672605-1403424140301789256带双亲的孩子链表返回
第59页：孩子兄弟表示法
3)孩子兄弟表示法
- 又称二叉树表示法，或二叉链表表示法，链表中结点的两个链域分别指向该结点的第一个孩子和下一个兄弟结点
- typedefstructCSNode{ElemTypedata;StructSCNode*firstchild,*nextsibling;
- }CSNode,*CSTree;RBCDEFGHKARABCGEFDHK返回
第60页：森林与二叉树的转换
(2)森林与二叉树的转换
- 二叉树和树都可以用二叉链表做存储结构，因而可以用二叉链表作为二叉树和树之间转换的桥梁
第61页：树与二叉树的对应关系
树与二叉树转换BCED树ABCDE二叉树AA^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^对应存储存储解释解释
第62页：树转换成二叉树的方法
树(T)�二叉树(B)的转换方法与步骤
- 连兄弟
- 留第一个孩子、断其它孩子
- 以根为轴心将整个树顺时针转45度
第63页：树转换成二叉树的步骤
加线：在兄弟之间加一连线
- 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之B间的关系
- 旋转：以树的根结点为轴心，将整树顺时针转45°AACDBCDEFGHIEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空1）树转换成二叉树具体步骤
第64页：二叉树转换成树的步骤
加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来
- 抹线：抹掉原二叉树中双亲与右孩子之间的连线
- 调整：将结点按层次排列，形成树结构BCDEFGHIAABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI2）二叉树转换成树具体步骤
第65页：森林与二叉树的转换规则
森林(F(T1,T2,…,Tm))�二叉树(B)的转换
- 若F为空，B为空
- 若F非空，B的根为第一棵树T1的根，B的左子树为T1中根的子树森林转换的二叉树，B的右子树为森林F’(T2,…,Tm)转换成的二叉树
第66页：森林转换成二叉树的步骤
生成二叉树：将各棵树分别转换成二叉树
- 连根结点：将每棵树的根结点用线相连
- 旋转：以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构ABCDFEGHIJBCDEFAGHIJABCDEFGHIJABCDEFGHIJ3）森林转换成二叉树具体步骤
第67页：二叉树转换成森林的规则
二叉树(B)-+森林(F(T1,T2,…,Tm))的转换
- 若B为空，F为空
- 若B非空，F中第一棵树T1的根为B的根，T1中根结点的子树森林为B的左子树转换而成，其余森林F’(T2,…,Tm)由B的右子树转换成
第68页：二叉树转换成森林的步骤
抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
- 还原：将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ4）二叉树转换成森林具体步骤返回
第69页：树和森林的遍历
(3)树和森林的遍历
- 树的遍历方法
- 先根（次序）遍历树:先访问树的根结点,然后依次先根遍历根的每一棵子树(ABCDE)
- 后根（次序）遍历树:先依次后根遍历每棵子,然后访问根结点(BDCEA)
- 森林的遍历方法
- 先序遍历森林:(ABCDEFGHIJ)
- 中序遍历森林(BCDAFEHJIG)
- 森林的先序和中序遍历即为其对应的二叉树的先序和中序遍历ABCEDBCDAEFGHIJ
第70页：树的遍历示例
ABCDEFGHIJKLMNO先序遍历：ABEFIGCDHJKLNOM后序遍历：EIFGBCJKNOLMHDA层次遍历：ABCDEFGHIJKLMNO下一节
第71页：第六节赫夫曼树及其应用
第六节赫夫曼树及其应用
第72页：最优二叉树的定义
哈夫曼树(Huffman)——带权路径长度最短的树
- 定义
- 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径
- 路径长度：路径上的分支数
- 树的路径长度：从树根到每一个结点的路径长度之和
- 树的带权路径长度：树中所有带权结点的路径长度之和其中：knkw——权值lk——结点到根的路径长度wlk记作：wplk1(1)最优二叉树(赫夫曼树)
第73页：赫夫曼树的定义
Huffman树——设有n个权值{w1,w2,……wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi，则wpl最小的二叉树叫做最优二叉树(赫夫曼树)
第74页：赫夫曼树构造示例
例如：有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35nWPLWKLKk1
第75页：赫夫曼树的应用背景
例如，编制一个将百分制转换成五级分制的程序时，先判断哪个分数段后判断哪个分数段？这是就要考虑学生在不同分数段的概率是不同的这个因素，概率大的先判断
第76页：赫夫曼树的构造步骤
(2)赫夫曼树构成
- （1）根据n个权值{w1,w2,….wn}构造n棵二叉树的集合F={T1,T2,…Tm},每棵树只有根结点，无左右子树
- （2）选两可权值最小的树作为左右子树构造一棵新树，该新树根结点的权为左右子树根结点的权之和
- （3）在F中删除这两棵树，将新得到的二叉树加入F中
- （4）中复（2）和（3），直到F中只有一棵树为止
第77页：赫夫曼树构造过程示例
例如17a5b2c4d7a5b2c4d67a5b2c4d6117a5b2c4d61118
第78页：赫夫曼树构造示例二
例如2w={5, 29, 7, 8, 14, 23, 3,11}52978142331129781423118537815291423118538192914231578111153823192914781553291429291578115381923421153819234214292915785811538192342142929157858100
第79页：赫夫曼编码的由来
(2)赫夫曼编码
- 问题由来
- 电文传输、出现次数多的字符采取尽可能短的编码可以减少电文长度
- 设计长短不等的编码，必须是任意一个字符的编码不是另一个字符的前后缀，这种编码称前缀编码
- 可以利用二叉树来设计二进制的前缀编码，并约定左分支表示字符‘0’，右分支为‘1’，则从根结点到叶结点的路径上分支字符组成的字符串即为该叶结点的字符编码
- 电文中，可利用n种字符出现的概率做权来设计赫夫曼编码
第80页：赫夫曼树的存储结构
1)赫夫曼树和赫夫曼编码的存储结构
- 由于赫夫曼树中没有度为1的结点，所以一棵具有n个叶结点的赫夫曼树共有2n-1个结点
- 存储结构
- typedefstruct{unsignedintweight;usingnedintparent,1child,rchild;
- }HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树
- typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表abcd
第81页：算法6.12求赫夫曼编码
2)求赫夫曼编码算法6.12voidHuffmanCoding(Huffmantree&HT,HuffmanCode&HC,int*w,intn){ if(n<=1)return; m=2*n-1; HT=(Huffmantree)malloc(m+1)*sizeof(HTNode));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[s1].parent=i; HT[s2].parent=i; HT[i].1child=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weghit; } (后续)
第82页：算法6.12续：逆向求编码
}//Huffmancoding2)求赫夫曼编码算法6.12(续)
- //从叶子到根逆向求每个字符的赫夫曼编码
- 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=HF[i].parent;f!=0//f==0为根//;c=f,f=HT[f].parent){//从叶子到逆向求编码if(HT[f].lchild==c)cd[--start]=‘0’elsecd[--start]=‘1’;}HC[i] =(char*)malloc(n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HC[i],&cd[start]);//从cd复制编码(串)到HC
- }
- free(cd);//释放工作空间startstart=n-1cd
第83页：算法6.13无栈非递归求编码
东华理工学
- 院3)求赫夫曼编码算法6.13HT[i].weight =0;//遍历赫夫曼树时作结点状态标志
- //从根到叶子，无栈非递归遍历赫夫曼树，求赫夫曼编码
- HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
- p=m;cdlen=0;//
- for(i=1;i<=m;++i)
- while(p){if(HT[p].weight ==0) {//向左HT[p].weight=1;if(HT[p].lchild!=0){p=HT[p].lchild;cd[cdlen++] =“0” ;}elseif(HT[p].rchild==0){//登记叶子结点的字符编码HC[p]=(char*)malloc((cdlen+1)*sizeof(char));cd[cdlen]=”\0”;strcpy(HC[p],cd);//复制编码（串）}}elseif(HT[p].weight==1){HT[p].weight=2;if(HT[p].rchild!=0){p=HT[p].rchild;cd[cdlen++]=“1”;}}else{//HT[p].weight==2,退回HT[p].weight=0;p=HT[p].parent;--cdlen;//退到父结点,编码长度减}//else程}朋//w根hile//向右
第84页：本章重点
本章重点
- 树的概念、术语
- 二叉树的性质、存储结构
- 二叉树遍历、线索二叉树的概念
- 树的结构、森林与二叉树的转换
- 赫夫曼树的构造过程和赫夫曼编码
第85页：习题（一）
习题：
- 1、树最适合用来表示：元素之间具有分支层次关系的数据。
- 2、深度为5的二叉树最多有31个结点。
- 3、深度为k的完全二叉树至少有2k-1个结点，至多有2k-1个结点，若自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶结点的编号是2k-1。
- 4、任何一棵二叉树的叶结点在先序、中序、后续遍历中的相对次序不发生变化。
- 5、已知一棵二叉树的中序遍历序列为cbedahgijf，后序遍历序列为cedbjigfa，画出该二叉树。
第86页：习题（二）
6、假设二叉树采用顺序存储结构1画出该二叉树2写出先序遍历、中序遍历和后序遍历的结果3写出结点c的双亲结点、其左、右孩子4画出把此二叉树还原成森林的图b0000ih00jc00g0d0fae作业：
第87页：习题（三）
7、有一份电文中共使用了5个字符：a、b、c、d、e，它们出现的频率依次为4、7、5、2、9，试画出对应的赫夫曼树，并求出每个字符的赫夫曼编码。赫夫曼树赫夫曼编码a:001b:10c:01d:000e:11627111624东华理dd工学院程朋aa根7b0115c19e1000
第88页：二叉树遍历练习图
acbdefghij
第89页：练习用二叉树图
ebadcfihjg二叉树
第90页：还原成的森林图
eadfijc还原成的森林bhg
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}