算法与数据结构：第六章 树和二叉树

《算法与数据结构：第六章 树和二叉树》由会员分享，可在线阅读，更多相关《算法与数据结构：第六章 树和二叉树（92页珍藏版）》请在装配图网上搜索。

1、数据结构-第六章 树和二叉树1第六章第六章 树和二叉树树和二叉树6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二叉树及其存储结构二叉树及其存储结构6.3 6.3 遍历二叉树遍历二叉树6.4 6.4 线索二叉树线索二叉树6.5 6.5 赫夫曼树及其应用赫夫曼树及其应用6.6 6.6 树和森林树和森林6.7 6.7 二叉树和树的应用示例二叉树和树的应用示例本章学习要点、习题与上机作业本章学习要点、习题与上机作业数据结构-第六章 树和二叉树26.1 树的定义和基本术语树的定义和基本术语 树是一类重要的非线性数据结构，是以分支关系定义的层次层次结构。6.1.1 树的定义树的定义

2、树树是由n(n0)个结点组成的有限集合T，非空树满足：1)有一个称之为根根(root)的结点。2)当n1时，除根以外的其余结点被分成m(m0)个互不相交的集合T1，T2，Tm，其中每一个集合本身又 是一棵树，且称为根的子树子树。数据结构-第六章 树和二叉树36.1.2 树的逻辑表示方法树的逻辑表示方法 AB C DE F G H IJ1层2层3层4层特点特点 除根结点外，每个结点都仅有一个前趋(父)结点。数据结构-第六章 树和二叉树4树的其它表示方法树的其它表示方法 嵌套集合表示法（文氏图表示法）嵌套集合表示法（文氏图表示法）凹入表表示法凹入表表示法ABEFGJCDHI 广义表表示法广义表表示

3、法 A(B(E，F(J)，G )，C，D(H，I)A B E F J G C D H I数据结构-第六章 树和二叉树56.1.3 基本术语基本术语结点的度结点的度 结点拥有的子树数目。树的度树的度 树的各结点度的最大值。叶子叶子(终端终端)结点结点 度为0的结点。分支分支(非终端非终端)结点结点 度不为0的结点。内部结点内部结点 除根结点之外的分支结点。双亲与孩子双亲与孩子(父与子父与子)结点结点 结点的子树的根称为该结点的孩子；该结点称为孩子的双亲。兄弟兄弟 属于同一双亲的孩子。堂兄弟堂兄弟 双亲在同一层的结点互为堂兄弟。结点的祖先结点的祖先 从根到该结点所经分支上的所有结点。结点的子孙结点

4、的子孙 该结点为根的子树中的任一结点。数据结构-第六章 树和二叉树6结点的层次结点的层次 表示该结点在树中的相对位置。根为第一层，其它的结点依次下推；若某结点在第L层上，则其孩子在第L+1层上。树的深树的深(高高)度度 树中结点的最大层次。有序树有序树 树中各结点的子树从左至右是有次序的，不能互换。否则，称为无序树无序树。路径长度路径长度 从树中某结点Ni出发，能够“自上而下地”通过树中结点到达结点Nj，则称Ni到Nj存在一条路径，路径长度等于这两个结点之间的分支数。树的路径长度树的路径长度 从根到每个结点的路径长度之和。森林森林 是m(m0)棵互不相交的树的集合。数据结构-第六章 树和二叉树

5、76.1.4 树的基本操作树的基本操作1)构造空树 InitTree(&T)2)销毁已存在的树 DestroyTree(&T)3)将树清为空树 ClearTree(&T)4)求树的深度 TreeDepth(T)5)求树的根 Root(T)6)求指定结点的双亲 Parent(T,Cur_e)7)求指定结点的最左孩子 LeftChild(T,Cur_e)8)求指定结点的右兄弟 RightSibling(T,Cur_e)9)插入子树c作为结点p的第i棵子树 InsertChild(&T,&p,i,c)10)删除p结点的第i棵子树 DeleteChild(&T,&p,i)11)遍历操作 Travers

6、eTree(T,Visit()数据结构-第六章 树和二叉树86.2 二叉树及其存储结构二叉树及其存储结构 引入二叉树是作为一般树（森林）的规范形式，它与树引入二叉树是作为一般树（森林）的规范形式，它与树（森林）可以建立一一对应，为解决树的问题提供方便。（森林）可以建立一一对应，为解决树的问题提供方便。6.2.1 二叉树的概念二叉树的概念二叉树的定义二叉树的定义 二叉树是n(n0)个结点的有限集合，它或为空树空树(n=0)，或由一个根根结点和两棵互不相交的左子树左子树和右子树右子树的二叉树组成。二叉树的特点二叉树的特点 定义是递归的 0结点的度2 是有序树左子树右子树根结点数据结构-第六章 树和

7、二叉树9二叉树的五种基本形态二叉树的五种基本形态两种特殊的二叉树两种特殊的二叉树 满二叉树满二叉树 每一层上的结点数都是最大结点数。完全二叉树完全二叉树 只有最下面两层结点的度可小于2，而最下一层的叶结点集中在左边若干位置上。12 34 5 6 712 34 5 6 78 9 10数据结构-第六章 树和二叉树106.2.2 二叉树的重要性质二叉树的重要性质性质性质1 二叉树的第i层上至多有2i-1(i1)个结点。证明归纳法 i=1时，只有一个根结点，20=1正确；假设第i-1层至多有2i-2 个结点，又二叉树每个结点的度至多为2 第i层上最大结点数是第i-1层的2倍，即2i-1 个。性质性质2

8、 深度为k的二叉树至多有2k-1个结点(k1)。证明由性质1，可得深度为k 的二叉树最大结点数是122)(111kkikiii层的最大结点数第数据结构-第六章 树和二叉树11性质性质3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明以两种方式统计二叉树的分支数，设n1为T中度为1的结点数 总度数即分支数B=n1+2n2 又二叉树中，除根结点外，其余结点都只有一个分支进入，则B=n0+n1+n2-1 n0=n2+1性质性质4 具有n个结点的完全二叉树的深度为 log2n+1(或 log2(n+1)。证明设完全二叉树的深度为k，则 2k-1-1 n 2k-

9、1 可得：2k-1 n 2k 取对数：k-1 log2n 1，则i的的双亲双亲是是 i/2；若i=1，则i是根，无双亲。(2)若2in，则i的的左孩子左孩子是是2i；否则，i无左孩子。(3)若2i+1n，则i的的右孩子右孩子是是2i+1；否则，i无右孩子。123114589126710数据结构-第六章 树和二叉树136.2.3 二叉树的基本操作二叉树的基本操作1)构造空二叉树 InitBiTree(&T)2)销毁已存在的二叉树 DestroyBiTree(&T)3)将二叉树清为空树 ClearBiTree(&T)4)求二叉树的深度 BiTreeDepth(T)5)求二叉树的根 Root(T)6

10、)求指定结点的双亲 Parent(T,e)7)求指定结点的左/右孩子 LeftChild(T,e)/RightChild(T,e)8)求指定结点的左/右兄弟 LeftSibling(T,e)/RightSibling(T,e)9)插入子树c作为结点p的左/右子树 InsertChild(&T,&p,LR,c)10)删除p结点的左/右子树 DeleteChild(&T,&p,LR)11)遍历操作 TraverseBiTree(T,Visit()数据结构-第六章 树和二叉树146.2.4 二叉树的存储结构二叉树的存储结构6.2.4.1 顺序存储结构顺序存储结构按完全二叉树编号存放按完全二叉树编号存

11、放 A B C -D E 0 1 2 3 6 13AB CDE12 3613typedef MAX_TREE_SIZE 100 /对应完全二叉树的最大结点编号typedef TElemType SqBiTreeMAX_TREE_SIZE+1 btSqBiTree bt;空间浪费可能大，特例：单枝树。空间浪费可能大，特例：单枝树。数据结构-第六章 树和二叉树15存储结点数据和左、右孩子在向量中的序号存储结点数据和左、右孩子在向量中的序号 0 1 2 3 4 data A B C D E lc 1 -1 3 -1 -1 rc 2 -1 -1 4 -1#define MAX_SIZE 80 /预定义

12、最大结点数目 typedef struct TElemType data;int lc,rc;int parent;TNode;typedef TNode SBiTreeMAX_SIZE;AB CDE01 23 4btSBiTree bt;data lc rc数据结构-第六章 树和二叉树166.2.4.2 链式存储结构链式存储结构二叉链表二叉链表三叉链表三叉链表 /带双亲的二叉链表带双亲的二叉链表lchild data rchild lchild data parent rchild A B C D E A B C D E btbt数据结构-第六章 树和二叉树17二叉链表的类型定义三叉链表的类

13、型定义typedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;typedef struct TriTNode TElemType data;struct TriTNode*lchild,*rchild,*parent;TriTNode,*TriTree;数据结构-第六章 树和二叉树186.3 遍历二叉树遍历二叉树 目的：非线性结构线性结构6.3.1 概念概念 指按某条搜索路线走遍二叉树的每个结点，使得树中每个结点都被访问一次，且仅被访问一次。方法：方法：二叉树每个结点有两个后继，则存

14、在如何遍历即按什么样的搜索路径进行遍历的问题。必须找到一种规律，将二叉树转换为一种线性结构，然后进行遍历。必要性：必要性：在实际应用中通常要在二叉树中查找具有某些特性的结点，或是对二叉树中的所有结点作某种处理，这就需要涉及二叉树的遍历问题。数据结构-第六章 树和二叉树196.3.2 典型的遍历方法典型的遍历方法 TraverseBiTree(T,Visit()先先(根)序遍历(DLR)：PreOrderTraverse(T,Visit()中中(根)序遍历(LDR)：InOrderTraverse(T,Visit()后后(根)序遍历(LRD)：PostOrderTraverse(T,Visit(

15、)层层序遍历：LevelOrderTraverse(T,Visit()上述逆序方式很少使用上述逆序方式很少使用DL RT 对对“二叉树二叉树”而言，可以有三条搜索路径：而言，可以有三条搜索路径：先上后下先上后下的按层次遍历；先左先左（子树）后右后右（子树）的遍历；先右先右（子树）后左后左（子树）的遍历。数据结构-第六章 树和二叉树20ADBCD L RAD L RD L RBDCD L R先序遍历序列：A B D C先序遍历:访问根结点、遍历左子树、遍历右子树访问根结点、遍历左子树、遍历右子树数据结构-第六章 树和二叉树21ADBCL D RBL D RL D RADCL D R中序遍历序列：

16、B D A C中序遍历:遍历左子树、访问根结点、遍历右子树遍历左子树、访问根结点、遍历右子树数据结构-第六章 树和二叉树22ADBC L R DL R DL R DADCL R D后序遍历序列：D B C A后序遍历:B遍历左子树、遍历右子树、访问根结点遍历左子树、遍历右子树、访问根结点数据结构-第六章 树和二叉树23确定遍历结果的一种简单方法确定遍历结果的一种简单方法先序遍历(DLR)：中序遍历(LDR)：后序遍历(LRD)：利用遍历结果确定二叉树利用遍历结果确定二叉树 先序序列+中序序列 中序序列+后序序列 先序序列+后序序列 先序序列:ABCDEFGH 中序序列:BDCEAFHGAB C

17、D EABFCGDEH思考：层序思考：层序+先序先序/中序中序/后序后序 能否确定？如何做？能否确定？如何做？DL RABDECDBEACDEBCA数据结构-第六章 树和二叉树246.3.3 二叉树遍历算法二叉树遍历算法(存储结构为二叉链表)约定：遍历要求对每个数据元素调用函数约定：遍历要求对每个数据元素调用函数 VisitVisit。6.3.3.1 先序遍历算法先序遍历算法Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if (T)if(Visit(T-data)if (PreOrderTraverse(T-lchild

18、,Visit)if (PreOrderTraverse(T-rchild,Visit)return OK;return ERROR;else return OK;/PreOrderTraverse递归算法递归算法TDL R数据结构-第六章 树和二叉树25Status pre(BiTree T)if (T)printf(T-data);pre(T-lchild);pre(T-rchild);主程序主程序Pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T

19、L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C数据结构-第六章 树和二叉树26算法分析：算法分析：时间复杂度时间复杂度 沿遍历路线访问每一个结点，对含n个结点的二叉树，时间复杂度为O(n)。空间复杂度空间复杂度 递归算法所需辅助空间为树的深度，最坏情况下树的深度为h。空间复杂度O(h)。数据结构-第六章 树和二叉树27改进的递归算法改进的递归算法Status PreOrderTraverse1(BiTree T)if (T)if(visit(T-data)if(T-

20、lchild)if (!PreOrderTraverse1(T-lchild)return ERROR;if(T-rchild)if (!PreOrderTraverse1(T-rchild)return ERROR;return OK;else return ERROR;else return OK;/PreOrderTraverse1目的：减少对空二叉树的递归调用。数据结构-第六章 树和二叉树28非递归算法非递归算法Status PreOrderTraverse2(BiTree T)IniStack(S);p=T;Push(S,NULL);while(p)if (!visit(p-data

21、)return ERROR;if (p-rchild)Push(S,p-rchild);if (p-lchild)p=p-lchild;else Pop(S,p);return OK;/PreOrderTraverse2p1p2p3T数据结构-第六章 树和二叉树296.3.3.2 中序遍历算法中序遍历算法Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if (T)if (InOrderTraverse(T-lchild,Visit)if(Visit(T-data)if (InOrderTraverse(T-rchild,Vi

22、sit)return OK;return ERROR;else return OK;/InOrderTraverse递归算法递归算法TDL R数据结构-第六章 树和二叉树30非递归算法一非递归算法一Status InOrderTraverse1(BiTree T)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)return ERROR;Push(S,p-rchild);return

23、 OK;/InOrderTraverse1 P130-6.2p1p2p3NULLNULLp3p2p1数据结构-第六章 树和二叉树31非递归算法二非递归算法二Status InOrderTranverse2(BiTree T)InitStack(S);p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;else pop(S,p);if(!Visit(p-data)return ERROR;p=p-rchild;return OK;/InOrderTraverse2 P131-6.3LDRp3p2p1数据结构-第六章 树和二叉树326.3.3.2

24、 后序遍历算法后序遍历算法Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if (T)if (PostOrderTraverse(T-lchild,Visit)if (PostOrderTraverse(T-rchild,Visit)if(Visit(T-data)return OK;return ERROR;else return OK;/PostOrderTraverse递归算法递归算法TDL R数据结构-第六章 树和二叉树33非递归算法非递归算法 为了区分两次返回根结点时栈的不同处理方式，在堆栈中增加一个mark域

25、：mark=0表示刚刚经过此结点；mark=1表示左子树处理结束返回；mark=2表示右子树处理结束返回每次根据栈顶元素的mark域值决定做何种动作。TDL R数据结构-第六章 树和二叉树34Status PostOrderTraverse1(BiTree T)InitStack(S);Push(S,T,0);/根结点(指针、mark)入栈 while(!StackEmpty(S)Pop(S,a);switch(a.mark)case 0:Push(S,a.p,1);/修改mark域 if(a.p-lchild)Push(S,a.p-lchild,0);/访问左子树 break;case 1:

26、Push(S,a.p,2);/修改mark域 if(a.p-rchild)Push(S,a.p-rchild,0);/访问右子树 break;case 2:if (!visit(a.p-data)return ERROR;return OK;/PostOrderTraverse1数据结构-第六章 树和二叉树356.3.3.4 按层次遍历的算法按层次遍历的算法Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if(T)InitQueue(Q);EnQueue(Q,T);/根结点的指针T入队列 while(!QueueEmp

27、ty(Q)DeQueue(Q,p);/从队头取一个指针 if(!Visit(p-data)return ERROR;if(p-lchild)EnQueue(Q,p-lchild);if(p-rchild)EnQueue(Q,p-rchild);return OK;/LevelOrderTraverseAB CD ETEABCD数据结构-第六章 树和二叉树366.3.4 二叉树递归遍历算法的利用二叉树递归遍历算法的利用在二叉树中查找结点值为在二叉树中查找结点值为x的结点的结点BiTNode*PreFind(BiTree T,TElemType x)if (!T)return NULL;if (T

28、-data=x)return T;else p=PreFind(T-lchild,x);if (p)return p;else return PreFind(T-rchild,x);/PreFind TDL R(先序先序/中序中序/后序后序)数据结构-第六章 树和二叉树37求二叉树中每个结点所处的层次求二叉树中每个结点所处的层次Status PreLevel(BiTree T,int level)if (T)printf(T-data,level);PreLevel(T-lchild,level+1);PreLevel(T-rchild,level+1);return OK/PreLevel调

29、用语句：PreLevel(T,1)TDL R(先序先序)数据结构-第六章 树和二叉树38若二叉树为空树，则深度为0;否则，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度。求二叉树的高度求二叉树的高度int PostHeight(BiTree T)if (!T)return 0;h1=PostHeight(T-lchild);h2=PostHeight(T-rchild);if (h1h2)return h1+1;else return h2+1;/PostHeightTDL R方法方法1.1.分析二叉树的深度和它的分析二叉树的深度和它的 左、右子树深度之间的关

30、系。左、右子树深度之间的关系。(后序后序)数据结构-第六章 树和二叉树39求二叉树的高度求二叉树的高度TDL R方法方法2.2.分析二叉树的深度和结点的分析二叉树的深度和结点的 “层次层次”间的关系。间的关系。从二叉树深度的定义可知，二叉树的深度即为其叶子结点所在层次的最大值。由此，可通过遍历求得二叉树中所有结点的“层次”，从中取其最大值。void Depth(BiTree T,int level,int&dval)if(T)if(leveldval)dval=level;Depth(T-lchild,level+1,dval);Depth(T-rchild,level+1,dval);/调用

31、之前 level 的初值为 1。/dval 的初值为 0.(先序先序)数据结构-第六章 树和二叉树40复制一棵二叉树复制一棵二叉树右子树右子树根元素根元素T左子树左子树右子树右子树根元素根元素NEWT左子树左子树右子树右子树左子树左子树右子树右子树方法方法1 1.(.(后序遍历后序遍历)其基本操作为其基本操作为:生成一个结点生成一个结点数据结构-第六章 树和二叉树41BiTNode*GetTreeNode(TElemType item,BiTNode*lptr,BiTNode*rptr)/生成一个二叉树的结点:其数据域为item,/左指针域为lptr,右指针域为rptr.if(!(T=(BiT

32、Node*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=item;T-lchild=lptr;T-rchild=rptr;return T;BiTNode*CopyTree(BiTNode*T)if(!T)return NULL;if(T-lchild)newlptr=CopyTree(T-lchild);/复制左子树 else newlptr=NULL;if(T-rchild)newrptr=CopyTree(T-rchild);/复制右子树 else newrptr=NULL;newT=GetTreeNode(T-data,newlptr,new

33、rptr);return newT;/CopyTree数据结构-第六章 树和二叉树42ABCDEFGHK D C H K G A例如例如:下列二叉树的下列二叉树的复制过程如下复制过程如下:newT F B E 数据结构-第六章 树和二叉树43复制一棵二叉树复制一棵二叉树T2DL RStatus PreCopy(BiTree T1,BiTree&T2)if (T1)if(!(T2=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T2-data=T1-data;PreCopy(T1-lchild,T2-lchild);PreCopy(T1-rchild

34、,T2-rchild);else T2=NULL;return OK;/PreCopyT1DL R方法方法2 2.(.(先序遍历先序遍历)数据结构-第六章 树和二叉树446.4.1 引入线索二叉树的意义引入线索二叉树的意义 利用二叉链表的空指针域，建立指向该结点的前驱/后继(某种遍历方式下)结点的指针，方便二叉树的线性化使用。(n n个结点的二叉树含有个结点的二叉树含有n+1n+1空指针域空指针域)6.4.2 线索二叉树的存储结构线索二叉树的存储结构 lchild LTag data RTag rchild 左特征位 LTag=0 lchild域指示结点的左孩子 1 lchild域指示结点的前

35、驱结点 右特征位 RTag=0 rchild域指示结点的右孩子 1 rchild域指示结点的后继结点CABDET数据结构-第六章 树和二叉树45例例类型定义类型定义先序线索二叉树 ABDCE 0 A 0 1 B 0 0 C 1 1 D 1 1 E 1 bt 0 A 0 1 B 0 0 C 1 1 D 1 1 E 1bt中序线索二叉树 BDAEC 0 A 0 1 B 0 0 C 1 1 D 1 1 E 1T后序线索二叉树 DBECACABDECtypedef enum PointerTag Link,Thread;/Link=0:指针，Thread=1:线索typedef struct BiTh

36、rNode TElemType data;Struct BiThrNode *lchild,*rchild;PointerTag LTag,RTag;BiThrNode,*BiThrTree;数据结构-第六章 树和二叉树466.4.3 线索二叉树的操作线索二叉树的操作6.4.3.1 查找结点查找结点p的前驱的前驱/后继结点后继结点（1）中序线索二叉树）中序线索二叉树 p的后继 若p-RTag=1，则p-rchild即为所求；若p-RTag=0，则从其右子沿着左链走到LTag=1 的那个结点就是。p的前驱 若p-LTag=1，则p-lchild即为所求；若p-LTag=0，则从其左子沿着右链走到

37、RTag=1 的那个结点就是。pL D RLDRLDR数据结构-第六章 树和二叉树47（2）后序线索二叉树）后序线索二叉树 p的前驱 若p-LTag=1，则p-lchild即为所求；若p-LTag=0，则若p-RTag=0，则p-rchild即为所求 若p-RTag=1，则p-lchild即为所求 p的后继 与双亲结点有关，因二叉链表中没有指向双亲结点的指针，就可能需通过二叉树的后序遍历才可确定，因而后序线索二叉树在此问题上并不比普通二叉树有效。（3）先序线索二叉树）先序线索二叉树 与后序线索二叉树对偶p中序线索二叉树可以方便地查找一个结点的前驱中序线索二叉树可以方便地查找一个结点的前驱/后继

38、结点。后继结点。L R DLRD数据结构-第六章 树和二叉树486.4.3.2 二叉树中序线索化二叉树中序线索化ABCDEnullnull带头结点的中序线索二叉树带头结点的中序线索二叉树 （双向线索链表）算法思想算法思想 利用中序遍历算法算法步骤算法步骤 若二叉树p非空，1)左子树线索化；2)访问当前结点p：2.1)置 LTag和RTag；2.2)建立p的前趋线索；2.3)建立p的前趋pre的后继线索;2.4)将p作为下一个被访问结点的前趋结点 3)右子树线索化；算法描述参教材算法描述参教材P134-135 算法算法6.6、6.7pre p 0 A 0 1 B 0 0 D 1 1 C 1 1

39、E 1 thrt中序序列：thrt BCAED thrt 0 1T数据结构-第六章 树和二叉树49算法描述算法描述Status InOrderThreading(BiThrTree&Thrt,BiThrTree T)if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit(OVERFLOW);Thrt-LTag=Link;Thrt-Rtag=Thread;Thrt-rchild=Thrt;/初始化Thrt if(!T)Thrt-LTag=Thread;Thrt-lchild=Thrt;else Thrt-lchild=T;pre=Thrt InThre

40、ading(T);pre-RTag=Thread;/最后一个结点线索化 pre-rchild=Thrt;Thrt-rchild=pre;return OK;/InOrderThreading P134-6.6 ThrtTVoid 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);/InThreading P135-6.7

41、数据结构-第六章 树和二叉树506.4.3.3 中序线索二叉树的中序遍历中序线索二叉树的中序遍历 二叉线索树的遍历不需要递归，在先序/中序线索二叉树中，利用线索可方便地找到当前结点的后继结点。因此，对有 n个结点的二叉线索树，可以在 O(n)时间内遍历完该树。算法步骤算法步骤 若二叉树p非空，1)找到中序序列的第一个结点；2)访问当前结点；3)将当前结点的后继作为新的当前结点；4)当前结点存在，则转2)数据结构-第六章 树和二叉树51算法描述算法描述Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e)p=T-lch

42、ild;while(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);p=p-rchild;return OK;/InOrderTraverse_Thr P134-6.5数据结构-第六章 树和二叉树52*6.4.3.4 线索二叉树的更新操作线索二叉树的更新操作问题点问题点 在线索二叉树上插入或删除一棵子树或者结点时，指针和线索都需作相应的改动。解决方法解决方法1）还原为普通二叉树，再重新将其线索化。2）讨

43、论可能出现的各种情况，寻找规律。数据结构-第六章 树和二叉树536.5 赫夫曼树及其应用赫夫曼树及其应用6.5.1 赫夫曼树（最优二叉树）的概念赫夫曼树（最优二叉树）的概念例例 编制将百分制转换为五级分制的程序(10000数据)分数 059 6069 7079 8089 90100 比例 0.05 0.15 0.40 0.30 0.10 a60 a80 bad a70 a70 a90 pass a80 a60 general good excellent general a90 bad pass good excellentY NY N31500次22000次数据结构-第六章 树和二叉树54术

44、语术语树的路径长度树的路径长度 从树根到每一个结点的路径上的分支数。带权路径长度带权路径长度 结点的路径长度与该结点的权之积。树的带权路径长度树的带权路径长度 树中所有叶子结点的带权路径长度之和。最优二叉树最优二叉树(赫夫曼树赫夫曼树)带权路径长度WPL最小的二叉树。最优树最优树 由给定的n 个带权叶子结点所构成的所有 m 叉树中，必存在一棵其带权路径长度取最小值带权路径长度取最小值的树，称为“最优树最优树”。结点到根的路径长度权值其中：记作：kknkkklwlwwpl1数据结构-第六章 树和二叉树55例例 有4个结点，权值分别为7，5，2，4，构造有4个 叶子结点的二叉树。abcd7524d

45、cab2475abcd7524WPL=7*2+5*2+2*2+4*2=36WPL=7*3+5*3+2*1+4*2=46WPL=7*1+5*2+2*3+4*3=35数据结构-第六章 树和二叉树566.5.2 建立赫夫曼树（最优二叉树）的方法建立赫夫曼树（最优二叉树）的方法基本思想基本思想 使权大的结点靠近根。(1)将给定权值从小到大排序成w1,w2,wm，生成一个森林F=T1,T2,Tm，其中Ti是一个带权Wi的根结点，它的左右子树均空。(2)把F中根的权值最小的两棵二叉树T1和T2合并成一棵新的二叉树T：T的左子树是T1，右子树是T2，T的根的权值是T1、T2树根结点权值之和。(3)将T按权值

46、大小加入F中，同时从F中删去T1和T2(4)重复(2)和(3)，直到F中只含一棵树为止，该树即为所求。数据结构-第六章 树和二叉树57例例 w=5,29,7,8,14,23,3,1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295811358192342291487152958100数据结构-第六章 树和二叉树58例例 第一步：第二步：第三步：0.050.100.150.300.400.050.1

47、00.150.150.300.400.050.100.150.300.300.400.400.300.600.150.100.05数据结构-第六章 树和二叉树59第四步：0.400.300.150.050.101.00(a60)(60a70)(80a90)(70 a0)0)，构造赫夫曼树，构造赫夫曼树HTHT if (n=1)HT=NULL;return;m=2*n-1;/计算总结点个数计算总结点个数 HT=(HuffmanTree)malloc(m+1)sizeof(HTNode);for(p=HT+1,i=1;i=n;+i,+p,+w)*p=*w,0,0,0;/初始化初始化HTHT for

48、(;i=m;+i,+p)*p=0,0,0,0;for(i=n+1;i=m;+i)/建建赫夫曼树赫夫曼树 Select(HT,i-1,s1,s2);/在在HT1.i-1HT1.i-1中选择中选择parentparent为为0 0且权值最小的两个结点且权值最小的两个结点 HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/BuildHT数据结构-第六章 树和二叉树636.5.3 赫夫曼树的应用赫夫曼树的应用 最佳判定树 赫夫曼编码：用于通信和数据传送中字符的二进制编码

49、，可以使电文编码总长度最短。例例 对time tries truth赫夫曼编码 字符集 D=t,i,m,e,r,s,u,h 出现频次 W=4,2,1,2,2,1,1,1uhtierms01010101010101t 01i 100m 1110e 101r 110s 1111u 000h 001数据结构-第六章 树和二叉树64 赫夫曼编码是不等长编码 赫夫曼编码是前缀编码前缀编码，即任一字符的编码都不是另一字符编码的前缀 赫夫曼编码树中没有度为1的结点。若叶子结点的个数为n，则赫夫曼编码树的结点总数为 2n-1 发送过程：根据由赫夫曼树得到的编码表送出字符数据 接收过程：按左0、右1的规定，从根

50、结点走到一个叶结点，完成一个字符的译码。反复此过程，直到接收数据结束数据结构-第六章 树和二叉树65赫夫曼编码表的存储结构赫夫曼编码表的存储结构012nHCtypedef char*HuffmanCode;HuffmanCode HC;1 0 1 10 1 01 0 0 1 0 1 数据结构-第六章 树和二叉树66赫夫曼编码实现的算法步骤赫夫曼编码实现的算法步骤 主数据结构：赫夫曼树HT 赫夫曼编码表HC 辅助数据结构：cd 编码工作空间1)分配HC空间;2)分配cd空间，置cdn-1=“0”;3)依次求叶子HTi的编码HCi，i=1.n 3.1)置cd中记录编码位置的初值：start=n-1

51、;置上溯的起点：c=i;取c的父结点：f=HTc.parent;3.2)根据HT，c、f上溯直到根结点(f=0)，依次产生的编码(c是f的左 孩子编码为0；否则为1)置入cd的相应编码空间cdstart-1并调整 start(减1)3.3)为第i个字符编码申请（n-start）大小的字符空间HCi，cd复制 给HCi4）释放cd空间0 n-1 start0011001数据结构-第六章 树和二叉树67数据结构-第六章 树和二叉树67求赫夫曼编码的算法求赫夫曼编码的算法Void HuffmanCoding(HuffmanTree HT,int n,HuffmanCode&HC)/求求赫夫曼树赫夫曼

52、树HTHT的的n n个字符的赫夫曼编码个字符的赫夫曼编码HCHC HC=(HuffmanCode)malloc(n+1)sizeof(char*);cd=(char*)malloc(n*sizeof(char);/分配编码的工作空间分配编码的工作空间 cdn-1=“0”;for(i=1;idata!=fa)/查询双亲结点 DeQueue(Q,s);GetHead(Q,s);if(!(s-firstchild)s-firstchild=p;/链接第一个孩子结点点else r-nextsibling=p;/链接其它孩子结点EnQueue(Q,p);数据结构-第六章 树和二叉树816.7 二叉树和树

53、的应用示例二叉树和树的应用示例6.7.1 二叉树表示的表达式二叉树表示的表达式表达式表达式 =(操作数操作数1)()(运算符运算符)()(操作数操作数2)运算符运算符操作数1（表达式）（表达式）操作数2（表达式）（表达式）递归定义递归定义表达式为数或简单变量时，则相应的二叉树仅有一个根结点，其数据域存放该表达式信息。数据结构-第六章 树和二叉树82例例 a+b*(c-d)-e/f 先序序列 前缀表示（波兰式）-+a*b-cd/ef 中序序列 中缀表示 a+b*(c-d)-e/f 后序序列 后缀表示（逆波兰式）abcd-*+ef/-+/a*b-efcd思考：中序遍历如何得到正确的中缀表达式？数据

54、结构-第六章 树和二叉树836.7.2 回溯求解问题回溯求解问题回溯法求解步骤回溯法求解步骤 1）定义一个解空间（搜索树），它包含问题的解2）用适合于搜索的方式组织该空间3）在约束条件下先序遍历（深度优先）搜索该解空间，并在遍历过程中剪去那些不满足条件的分支。回溯法的一般形式回溯法的一般形式void trial(ElemType r,.)if (当前所得解r为所求)printf(r);else for(i=1;in)输出棋盘的当前布局;else for(j=1;jdata=ch;CreatBiTree(T-lchild);CreatBiTree(T-rchild);/CreatBiTree P131-6.4ABCDEFABDCEF