数据结构树和二叉树图文.pptx

6.1 树的类型定义树的类型定义6.2 6.2 二叉树的类型定义二叉树的类型定义6.3 二叉树的存储结构二叉树的存储结构6.4 二叉树的遍历二叉树的遍历6.5 线索二叉树线索二叉树6.6 树和森林的表示方法树和森林的表示方法6.8 二叉排序树及其平衡化二叉排序树及其平衡化6.7 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码第1页/共180页6.1 树的类型定义树的类型定义第2页/共180页数据对象数据对象 D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。若若D为空集，则称为空树为空集，则称为空树。否则否则:(1)在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root；(2)当当n1时，其余结点可分为时，其余结点可分为m(m0)个互个互 不相交的有限集不相交的有限集T1,T2,Tm，其中每一，其中每一 棵子集本身又是一棵符合本定义的树，棵子集本身又是一棵符合本定义的树，称为根称为根root的子树。的子树。数据关系数据关系 R：第3页/共180页 基本操作：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类第4页/共180页 Root(T)/求树的根结点求树的根结点 查找类：查找类：Value(T,cur_e)/求当前结点的元素值求当前结点的元素值 Parent(T,cur_e)/求当前结点的双亲结点求当前结点的双亲结点LeftChild(T,cur_e)/求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T,cur_e)/求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树判定树是否为空树 TreeDepth(T)/求树的深度求树的深度TraverseTree(T,Visit()/遍历遍历第5页/共180页InitTree(&T)/初始化置空树初始化置空树 插入类：插入类：CreateTree(&T,definition)/按定义构造树按定义构造树Assign(T,cur_e,value)/给当前结点赋值给当前结点赋值InsertChild(&T,&p,i,c)/将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树第6页/共180页 ClearTree(&T)/将树清空将树清空 删除类：删除类：DestroyTree(&T)/销毁树的结构销毁树的结构DeleteChild(&T,&p,i)/删除结点删除结点p的第的第i棵子树棵子树第7页/共180页ABCDEFGHIJMKLA(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根例如例如:第8页/共180页()有确定的根；()树根和子树根之间为有向关系。有向树：有向树：有序树：有序树：子树之间存在确定的次序关系。无序树：无序树：子树之间不存在确定的次序关系。第9页/共180页对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点第10页/共180页线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)第11页/共180页基基 本本 术术 语语第12页/共180页结点结点:结点的度结点的度:树的度树的度:叶子结点叶子结点:分支结点分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM第13页/共180页(从根到结点的)路径路径：孩子孩子结点、双亲双亲结点兄弟兄弟结点、堂兄弟祖先祖先结点、子孙子孙结点结点的层次结点的层次:树的深度：树的深度：由从根根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次第14页/共180页任何一棵非空树是一个二元组 Tree=（root，F）其中：root 被称为根结点 F 被称为子树森林森林：森林：是m（m0）棵互不相交的树的集合ArootBCDEFGHIJMKLF第15页/共180页6.2 二叉树的类型定义二叉树的类型定义第16页/共180页 二叉树或为空树空树，或是由一个根结根结点点加上两棵两棵分别称为左子树左子树和右子树的、互不交的互不交的二叉树二叉树组成。ABCDEFGHK根结点左子树右子树第17页/共180页二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树第18页/共180页 二叉树的主要基本操作二叉树的主要基本操作：查查 找找 类类插插 入入 类类删删 除除 类类第19页/共180页 Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit();InOrderTraverse(T,Visit();PostOrderTraverse(T,Visit();LevelOrderTraverse(T,Visit();第20页/共180页 InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);第21页/共180页ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);第22页/共180页二叉树二叉树的重要特性的重要特性第23页/共180页 性性质质 1：在二叉树的第 i 层 上 至 多 有2i-1 个 结 点。(i1)用归纳法证明用归纳法证明：归纳基归纳基：归纳假设：归纳假设：归纳证明：归纳证明：i=1 层时，只有一个根结点：2i-1=20=1；假设对所有的 j，1 j i，命题成立；二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2i-2 2=2i-1。第24页/共180页性质性质 2：深度为 k 的二叉树上至多含 2k-1 个结点（k1）。证明：证明：基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+2k-1=2k-1。第25页/共180页 性质性质 3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1。证明：证明：设设 二叉树上结点总数 n=n0+n1+n2又又 二叉树上分支总数 b=n1+2n2 而 b=n-1=n0+n1+n2-1由此，由此，n0=n2+1。第26页/共180页两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号编号为为 1 至至 n 的结点的结点一一对应。123456789 10 11 12 13 14 15abcdefghij第27页/共180页 性性质质 4：具有 n 个结点的完全二叉树的深度深度为 log2n +1。证明：证明：设设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子右孩子结点。第29页/共180页6.3 二叉树的存储结构二叉树的存储结构二、二叉树的链式二、二叉树的链式 存储表示存储表示一、一、二叉树的顺序二叉树的顺序 存储表示存储表示第30页/共180页#define MAX_TREE_SIZE 100 /二叉树的最大结点数typedef TElemType SqBiTreeMAX_ TREE_SIZE;/0号单元存储根结点SqBiTree bt;一、一、二叉树的顺序存储表示二叉树的顺序存储表示第31页/共180页例如例如:ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 131401326第32页/共180页二、二叉树的链式存储表示二、二叉树的链式存储表示1.1.二叉链表二叉链表2三叉链表三叉链表3 3双亲链表双亲链表4线索链表线索链表第33页/共180页ADEBCF rootlchild data rchild结点结构结点结构:1.1.二叉链表二叉链表第34页/共180页typedef struct BiTNode /结点结构结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下:第35页/共180页ADEBCF root 2三叉链表三叉链表parent lchild data rchild结点结构结点结构:第36页/共180页 typedef struct TriTNode /结点结构结点结构 TElemType data;struct TriTNode *lchild,*rchild;/左右孩子指针 struct TriTNode *parent;/双亲指针 TriTNode,*TriTree;parent lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下:第37页/共180页0123456 data parent结点结构结点结构:3 3双亲链表双亲链表LRTagLRRRL第38页/共180页 typedef struct BPTNode /结点结构结点结构 TElemType data;int *parent;/指向双亲的指针 char LRTag;/左、右孩子标志域 BPTNode typedef struct BPTree/树结构树结构 BPTNode nodesMAX_TREE_SIZE;int num_node;/结点数目 int root;/根结点的位置 BPTree第39页/共180页6.4二叉树的遍历二叉树的遍历第40页/共180页一、问题的提出一、问题的提出二、先左后右的遍历算法二、先左后右的遍历算法三、算法的递归描述三、算法的递归描述四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述五五、遍历算法的应用举例遍历算法的应用举例第41页/共180页 顺着某一条搜索路径巡访巡访二叉树中的结点，使得每个结点均被访问一均被访问一次次，而且仅被访问一次仅被访问一次。一、问题的提出一、问题的提出“访问访问”的含义可以很广，如：输出结点的信息等。第42页/共180页 “遍历遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继每个结点有两个后继，则存在如何遍历存在如何遍历即按什么样的搜索搜索路径路径遍历的问题。第43页/共180页 对对“二叉树二叉树”而言，可以有三条搜索路径：而言，可以有三条搜索路径：1先上后下先上后下的按层次遍历；2先先左左（子树）后后右右（子树）的遍历；3先先右右（子树）后后左左（子树）的遍历。第44页/共180页二、先左后右的遍历算法二、先左后右的遍历算法先先（根）序的遍历算法中中（根）序的遍历算法后后（根）序的遍历算法第45页/共180页 若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：先（根）序的遍历算法：第46页/共180页 若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：中（根）序的遍历算法：第47页/共180页 若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：后（根）序的遍历算法：第48页/共180页三、算法的递归描述三、算法的递归描述void Preorder(BiTree T,void(*visit)(TElemType&e)/先序遍历二叉树 if(T)visit(T-data);/访问结点 Preorder(T-lchild,visit);/遍历左子树 Preorder(T-rchild,visit);/遍历右子树 第49页/共180页四、算法的非递归描述四、算法的非递归描述ABCDEF第50页/共180页中序遍历算法的非递归描述中序遍历算法的非递归描述BiTNode*GoFarLeft(BiTree T,Stack*S)if(!T)return NULL;while(T-lchild)Push(S,T);T=T-lchild;return T;第51页/共180页void Inorder_I(BiTree T,void(*visit)(TelemType&e)Stack*S;t=GoFarLeft(T,S);/找到最左下的结点 while(t)visit(t-data);if(t-rchild)t=GoFarLeft(t-rchild,S);else if(!StackEmpty(S)/栈不空时退栈 t=Pop(S);else t=NULL;/栈空表明遍历结束 /while/Inorder_I 第52页/共180页层次遍历二叉树层次遍历二叉树 层次遍历二叉树，是从根结点开始遍历，按层次次序“自上而下，从左至右”访问树中的各结点。为保证是按层次遍历，必须设置一个队列，初始化时为空。设T是指向根结点的指针变量，层次遍历非递归算法是：若二叉树为空，则返回；否则，令p=T，p入队；队首元素出队到p；访问p所指向的结点；将p所指向的结点的左、右子结点依次入队。直到队空为止。第53页/共180页#define MAX_NODE 50void LevelorderTraverse(BTNode *T)BTNode *QueueMAX_NODE,*p=T;int front=0,rear=0;if (p!=NULL)Queue+rear=p;/*根结点入队根结点入队 */while(frontdata);if(p-Lchild!=NULL)Queue+rear=p;/*左结点入队左结点入队 */if(p-Rchild!=NULL)Queue+rear=p;/*左结点入队左结点入队 */第54页/共180页6.5线索二叉树线索二叉树 何谓线索二叉树？何谓线索二叉树？线索链表的遍历算法线索链表的遍历算法 如何建立线索链表？如何建立线索链表？第55页/共180页一、一、何谓线索二叉树何谓线索二叉树？遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如:先序先序序列:A B C D E F G H K中序中序序列:B D C A H G K F E后序后序序列:D C B H K G F E A第56页/共180页指向该线性序列中的“前驱”和“后继”的指针指针，称作“线线索索”与其相应的二叉树，称作“线索二叉树线索二叉树”包含“线索”的存储结构，称作“线索链线索链表表”A B C D E F G H K D C B E 第57页/共180页对对线索链表线索链表中结点的约定：中结点的约定：在二叉链表的结点中增加两个标志域增加两个标志域，并作如下规定：若该结点的左子树不空，若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域的值为“指针 Link”；否则，Lchild域的指针指向其“前驱”，且左标志的值为“线索 Thread”。第58页/共180页若该结点的右子树不空，若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为“指针 Link”；否则，rchild域的指针指向其“后继”，且右标志的值为“线索 Thread”。如此定义的二叉树的存储结构称作如此定义的二叉树的存储结构称作“线索链表线索链表”。第59页/共180页typedef struct BiThrNod TElemType data;struct BiThrNode *lchild,*rchild;/左右指针 PointerThr LTag,RTag;/左右标志 BiThrNode,*BiThrTree;线索链表的类型描述：typedef enum Link,Thread PointerThr;/Link=0:指针，Thread=1:线索第60页/共180页二、线索链表的遍历算法二、线索链表的遍历算法:for(p=firstNode(T);p;p=Succ(p)Visit(p);由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。第61页/共180页例如例如:对中序线索化链表的遍历算法对中序线索化链表的遍历算法 中序遍历的第一个结点中序遍历的第一个结点？在中序线索化链表中结点的后继在中序线索化链表中结点的后继？左子树上处于“最左下最左下”（没有左子树）的结点。若若无右子树，则为则为后继线索后继线索所指结点；否则为否则为对其右子树右子树进行中序遍历遍历时访问的第一个结点。第一个结点。中序线索链表查找前驱中序线索链表查找前驱中序线索链表查找后继中序线索链表查找后继第62页/共180页void InOrderTraverse_Thr(BiThrTree T,void(*Visit)(TElemType e)p=T-lchild;/p指向根结点 while(p!=T)/空树或遍历结束时，p=T while(p-LTag=Link)p=p-lchild;/第一个结点 while(p-RTag=Thread&p-rchild!=T)p=p-rchild;Visit(p-data);/访问后继结点 p=p-rchild;/p进至其右子树根 /InOrderTraverse_Thr中序线索链表的遍历算法中序线索链表的遍历算法第63页/共180页 在中序遍历过程中修改结点的在中序遍历过程中修改结点的左、右指针域，以保存当前访问结左、右指针域，以保存当前访问结点的点的“前驱前驱”和和“后继后继”信息。遍信息。遍历过程中，附设指针历过程中，附设指针pre,并始终保并始终保持指针持指针pre指向当前访问的、指针指向当前访问的、指针p所指结点的前驱。所指结点的前驱。三、如何建立线索链表？三、如何建立线索链表？中序线索树创建中序线索树创建1中序线索树创建中序线索树创建2第64页/共180页void InThreading(BiThrTree p)if(p)/对以p为根的非空二叉树进行线索化 InThreading(p-lchild);/左子树线索化 if(!p-lchild)/建前驱线索 p-LTag=Thread;p-lchild=pre;if(!pre-rchild)/建后继线索 pre-RTag=Thread;pre-rchild=p;pre=p;/保持 pre 指向 p 的前驱 InThreading(p-rchild);/右子树线索化 /if/InThreading第65页/共180页Status InOrderThreading(BiThrTree&Thrt,BiThrTree T)/构建中序线索链表 if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit(OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thread;Thrt-rchild=Thrt;/添加头结点 return OK;/InOrderThreading 第66页/共180页if(!T)Thrt-lchild=Thrt;else Thrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt;/处理最后一个结点 pre-RTag=Thread;Thrt-rchild=pre;第67页/共180页先左后右的遍历算法演示先左后右的遍历算法演示先先（根）序的遍历算法中中（根）序的遍历算法后后（根）序的遍历算法第68页/共180页中序线索链表中序线索链表演示演示如何遍历中序线索链表如何遍历中序线索链表如何建立中序线索链表如何建立中序线索链表第69页/共180页 6.6 树和森林树和森林 的表示方法的表示方法第70页/共180页树的三种存储结构树的三种存储结构一、一、双亲表示法双亲表示法二、二、孩子链表表示法孩子链表表示法三、三、树的二叉链表树的二叉链表(孩子孩子-兄弟）兄弟）存储表示法存储表示法第71页/共180页ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5r=0n=6data parent一、双亲表示法一、双亲表示法:第72页/共180页 typedef struct PTNode Elem data;int parent;/双亲位置域 PTNode;data parent#define MAX_TREE_SIZE 100结点结构结点结构:C语言的类型描述语言的类型描述:第73页/共180页typedef struct PTNode nodes MAX_TREE_SIZE;int r,n;/根结点的位置和结点个数 PTree;树结构树结构:第74页/共180页ABCDEFG0 A -11 B 02 C 03 D 04 E 25 F 26 G 5r=0n=6 data firstchild 1 2 34 56二、孩子链表表示法二、孩子链表表示法:-1000224第75页/共180页typedef struct CTNode int child;struct CTNode*next;*ChildPtr;孩子结点结构孩子结点结构:child nextC语言的类型描述语言的类型描述:第76页/共180页 typedef struct Elem data;ChildPtr firstchild;/孩子链的头指针 CTBox;双亲结点结构双亲结点结构 data firstchild第77页/共180页typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTree;树结构树结构:第78页/共180页ABCDEFG AB C E D F Groot AB C E D F G 三、树的二叉链表三、树的二叉链表(孩子孩子-兄弟）存储表示法兄弟）存储表示法第79页/共180页typedef struct CSNode Elem data;struct CSNode *firstchild,*nextsibling;CSNode,*CSTree;C语言的类型描述语言的类型描述:结点结构结点结构:firstchild data nextsibling第80页/共180页 森林和二叉树的对应关系森林和二叉树的对应关系设设森林森林 F=(T1,T2,Tn);T1=(root，t11,t12,t1m);二叉树二叉树 B=(LBT,Node(root),RBT);第81页/共180页由森林转换成二叉树由森林转换成二叉树的转换规则为:若 F=，则 B=；否则，由 ROOT(T1)对应得到 Node(root)；由(t11,t12,t1m)对应得到 LBT；由(T2,T3,Tn)对应得到 RBT。第82页/共180页由二叉树转换为森林由二叉树转换为森林的转换规则为：若 B=，则 F=；否则，由 Node(root)对应得到 ROOT(T1)；由LBT 对应得到(t11,t12,，t1m)；由RBT 对应得到(T2,T3,Tn)。第83页/共180页 由此，树的各种操作均可对应二叉树的操作来完成。应当注意的是，应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟。左是孩子，右是兄弟。第84页/共180页6.7树和森林的遍历树和森林的遍历第85页/共180页一、树的遍历一、树的遍历二、森林的遍历二、森林的遍历三、树的遍历的应用三、树的遍历的应用第86页/共180页树的遍历可有三条搜索路径树的遍历可有三条搜索路径:按层次遍历按层次遍历:先根先根(次序次序)遍历遍历:后根后根(次序次序)遍历遍历:若树不空，则先访问根结点，然后若树不空，则先访问根结点，然后依次先根遍历各棵子树。依次先根遍历各棵子树。若树不空，则先依次后根遍历各棵若树不空，则先依次后根遍历各棵子树，然后访问根结点。子树，然后访问根结点。若树不空，则自上而下自左至右若树不空，则自上而下自左至右访问树中每个结点。访问树中每个结点。第87页/共180页 A B C DE F G H I J K 先根遍历时顶点先根遍历时顶点的访问次序：的访问次序：A B E F C D G H I J K 后根遍历时顶点后根遍历时顶点的访问次序：的访问次序：E F B C I J K H G D A 层次遍历时顶点层次遍历时顶点的访问次序：的访问次序：A B C D E F G H I J K第88页/共180页 B C DE F G H I J K1森林中第一棵树的根结点；2森林中第一棵树的子树森林；3森林中其它树构成的森林。森林由三部分构成：第89页/共180页1.先序遍历先序遍历森林的遍历森林的遍历 若森林不空，则访问访问森林中第一棵树的根结点；先序遍历先序遍历森林中第一棵树的子树森林；先序遍历先序遍历森林中(除第一棵树之外)其 余树构成的森林。即：依次从左至右依次从左至右对森林中的每一棵树树进行先根遍历先根遍历。第90页/共180页中序遍历中序遍历 若森林不空，则中序遍历中序遍历森林中第一棵树的子树森林；访问访问森林中第一棵树的根结点；中序遍历中序遍历森林中(除第一棵树之外)其 余树构成的森林。即：依次从左至右依次从左至右对森林中的每一棵树树进行后根遍历后根遍历。第91页/共180页 树的遍历和二叉树遍历树的遍历和二叉树遍历的对应关系的对应关系？先根遍历先根遍历后根遍历后根遍历树树二叉树二叉树森林森林先序遍历先序遍历先序遍历先序遍历中序遍历中序遍历中序遍历中序遍历第92页/共180页设树的存储结构为孩子兄弟链表设树的存储结构为孩子兄弟链表typedef struct CSNode Elem data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;第93页/共180页6.8 哈哈 夫夫 曼曼 树树 与与 哈哈 夫夫 曼曼 编编 码码 最优树的定义最优树的定义 如何构造最优树如何构造最优树 前缀编码前缀编码 第94页/共180页 一、最优树的定义一、最优树的定义树的路径长度树的路径长度定义为：树中每个结点的路径长度之和。结点的路径长度结点的路径长度定义为：从根结点到该结点的路径上 分支的数目。第95页/共180页 树的带权路径长度树的带权路径长度定义为：树中所有叶子结点的带权路径长度结点的带权路径长度之和 WPL(T)=wklk(对所有叶子结点)。在所有含 n 个叶子结点、并带相同权值的 m 叉树中，必存在一棵其带权带权路径长度取最小值路径长度取最小值的树，称为“最优最优树树”。第96页/共180页27 9 75492WPL(T)=72+52+23+43+92 =60WPL(T)=74+94+53+42+21 =89 54第97页/共180页 根据给定的 n 个权值 w1,w2,wn，构造 n 棵二叉树的集合 F=T1,T2,Tn，其中每棵二叉树中均只含一个带权值 为 wi 的根结点，其左、右子树为空树；二、如何构造最优树二、如何构造最优树(1)(赫夫曼算法)以二叉树为例：第98页/共180页 在 F 中选取其根结点的权值为最 小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之 和；(2)第99页/共180页 从F中删去这两棵树，同时加入 刚生成的新树；重复(2)和(3)两步，直至 F 中只 含一棵树为止。(3)(4)第100页/共180页9例如:已知权值 W=5,6,2,9,7 562752769767139527第101页/共180页6713952795271667132900001111000110110111第102页/共180页 指的是，任何一个字符的编码都任何一个字符的编码都不是同一字符集中另一个字符的编码不是同一字符集中另一个字符的编码的前缀的前缀。三、前缀编码三、前缀编码 利用赫夫曼树可以构造一种不等长利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的的二进制编码，并且构造所得的赫夫赫夫曼编码曼编码是一种是一种最优前缀编码最优前缀编码，即使所，即使所传传电文的总长度最短电文的总长度最短。第103页/共180页5 5 哈夫曼树哈夫曼树哈夫曼编码算法void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,int n)/w存放n个字符的权值(均0),构造哈夫曼树HT,/并求出n个字符的哈夫曼编码HC HuffmanTree p;char*cd;if(n=1)return;m=2*n-1;第104页/共180页5 5 哈夫曼树哈夫曼树 HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0号单元未用 for(p=HT+1,i=1;i=n;+i,+p,+w)/初始化 哈夫曼树 (*p).weight=*w;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;第105页/共180页5 5 哈夫曼树哈夫曼树 for(;i=m;+i,+p)(*p).parent=0;for(i=n+1;i=m;+i)/建哈夫曼树 select(HT,i-1,s1,s2);/在HT1i-1中选择parent为0且weight /最小的两个结点,其序号分别为s1和s2第106页/共180页5 5 哈夫曼树哈夫曼树 HTs1.parent=HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/for /从叶子到根逆向求每个字符的哈夫曼编码 HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/分配n个字符编码的头指针向量(0不用)第107页/共180页5 5 哈夫曼树哈夫曼树cd=(char*)malloc(n*sizeof(char);/分配求编码的工作空间 cdn-1=0;/编码结束符 for(i=1;i=n;i+)/逐个字符求赫夫曼编码 start=n-1;/编码结束符位置第108页/共180页5 5 哈夫曼树哈夫曼树for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码 if(HTf.lchild=c)cd-start=0;else cd-start=1;第109页/共180页5 5 哈夫曼树哈夫曼树 HCi=(char*)malloc(n-start)*sizeof(char);/为第i个字符编码分配空间 strcpy(HCi,&cdstart);/从cd复制编码(串)到HC free(cd);/释放工作空间 /HuffmanCoding第110页/共180页5 5 哈夫曼树哈夫曼树求最小值函数int min(HuffmanTree t,int i)/函数void select()调用 int j,flag;unsigned int k=UINT_MAX;/取k为不小于可能的值第111页/共180页5 5 哈夫曼树哈夫曼树 for(j=1;j=i;j+)if(tj.weights2)j=s1;s1=s2;s2=j;/select 第113页/共180页5 5 哈夫曼树哈夫曼树 哈夫曼树的初始化哈夫曼树的初始化 weightparentlchildrchild7000500020004000000第114页/共180页5 5 哈夫曼树哈夫曼树 建哈夫曼树后的状态建哈夫曼树后的状态 weightParentlchildrchild770056002500450066341172518016第115页/共180页5 5 哈夫曼树哈夫曼树void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,int n)/同前/无栈非递归遍历哈夫曼树,求哈夫曼编码 HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/分配n个字符编码的头指针向量(0不用)cd=(char*)malloc(n*sizeof(char);/分配求编码的工作空间 c=m;cdlen=0;第116页/共180页5 5 哈夫曼树哈夫曼树 for(i=1;idata.key)else if(LT(key,T-data.key)else p=f;return FALSE;/查找不成功 p=T;return TRUE;/查找成功SearchBST(T-lchild,key,T,p);/在左子树中继续查找SearchBST(T-rchild,key,T,p);/在右子树中继续查找第130页/共180页30201040352523fT设 key=48fTfT22pfTfTTTTfffp第131页/共180页根据动态查找表的定义，“插入”操作在查找不成功时才进行；3二叉排序树的插入算法二叉排序树的插入算法若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。第132页/共180页Status Insert BST(BiTree&T,ElemType e)/当二叉排序树中不存在关键字等于当二叉排序树中不存在关键字等于 e.key 的的 /数据元素时，插入元素值为数据元素时，插入元素值为 e 的结点，并返的结点，并返 /回回 TRUE;否则，不进行插入并返回否则，不进行插入并返回FALSE if(!SearchBST(T,e.key,NULL,p)else return FALSE;/Insert BST 第133页/共180页s=(BiTree)malloc(sizeof(BiTNode);/为新结点分配空间s-data=e;s-lchild=s-rchild=NULL;if (!p)T=s;/插入 s 为新的根结点else if(LT(e.key,p-data.key)p-lchild=s;/插入*s 为*p 的左孩子else p-rchild=s;/插入*s 为*p 的右孩子return TRUE;/插入成功第134页/共180页（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（3）被删除的结点既有左子树，也有右子树。4二叉排序树的删除算法二叉排序树的删除算法可分三种情况讨论：和插入相反，删除在查找成功查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍仍然保持二叉排序树的特性然保持二叉排序树的特性。第135页/共180页50308020908540358832（1）被删除的结点是叶子结点叶子结点例如例如:被删关键字被删关键字=2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”第136页/共180页50308020908540358832（2）被删除的结点只有左子树只有左子树或者只有右子树只有右子树 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树指向被删除结点的左子树或右子树”。被删关键字被删关键字=4080第137页/共1