第6章树和二叉树.ppt

1,第6章 树和二叉树,2,主要内容,§6.1 树的定义和基本术语 §6.2 二叉树 §6.3 遍历二叉树 §6.4 线索二叉树 §6.5 树和森林 §6.6 赫夫曼树及其应用,3,§6.1 树的定义和基本术语(1),树（Tree）是n(n 0)个结点的有限集。在任意一棵非空树中: A、有且仅有一个称为根的结点； B、当n 2时，其余结点分为m(m 0) 个互不相交的子集，每个子集本身又是一棵树，称为根的子树。,以上是一个递归的定义在树的定义中又用到了树的概念，由此可见递归是树的固有特性。,4,§6.1 树的定义和基本术语(2),每个子集都是满足树的定义的树，称为A的子树B子树、C子树、D子树。,树根A没有直接前驱；其余结点有且仅有一个直接前驱有，有0个或多个直接后继。,三个互不相交的子集： B, E, F, K, L C ,G D, H, I, J, M ,树的特征：层次性和分支性,5,§6.1 树的定义和基本术语(3),结点的度：结点的非空子树个数 树的度：树内各结点度的最大值 分支结点(非终端结点) ：度非0的结点 叶子结点(终端结点)：度为0的结点 孩子：结点的子树的根 双亲：孩子的直接前驱结点 兄弟：同一个双亲的孩子结点互称为兄弟 子孙：以某结点为根的子树中的任一结点 祖先：从根到该结点所分支上的所有结点 堂兄:双亲在同一层的结点,6,结点的层次：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第L层，则其子树的根在第L+1层。 树的深度（高度）：结点层次的最大值 有序树和无序树：若树中所有结点的的各子树看成是从从至右是有次序的（即不能置换），称为有序树，否则称为无序树。 森林：m（m0）个树的集合,Tree = (A ( B ( E ( K , L ), F ), C ( G ), D ( G, H ( M ), I, J ) ) ),§6.1 树的定义和基本术语(4),7,树的基本操作： 构造空树 InitTree(,§6.1 树的定义和基本术语(5),8,§6.2 二叉树,二叉树的定义 二叉树的性质 二叉树的存储结构,9,§6.2.1 二叉树的定义(1),二叉树是另一种树型结构，它的特点是每个结点至多只有两 棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。 二叉树可以为空，称为空二叉树; 非空二叉树一定有两个子树； 左、右子树有次序关系，不能互换； 二叉树可以有5种基本形态： 二叉树不是结点的度都不超过2的有序树.,§6.2 二叉树,左子树,右子树,Ø,10,§6.2.1 二叉树的定义(2),具有三个结点的树与二叉树,§6.2 二叉树,A、三个结点的树有两种不同的形态,B、三个结点的二叉树有五种不同的形态,树型结构的共同特征：层次性、分支性,11,§6.2.1 二叉树的定义(3),二叉树的基本操作 初始化空二叉树 InitBiTree(&T) 销毁二叉树 DestroyBiTree(&T) 创建二叉树 CreateBiTree(&T, definition) 清空二叉树 ClearBiTree(&T) 判断空二叉树 BiTreeEmpty(T) 求二叉树深度 BiTreeDepth(T) 求双亲 parent(T, e) 求左孩子 LeftChild(T, e) 求右孩子 RightChild(T, e) 求左兄弟 LeftSibling(T, e) 求右兄弟 RightSibling(T, e) 插入子树 InsertChild(T, p, LR, c) 删除子树 DeleteChild(T, p, LR) 先序遍历二叉树 PreOrderTraverse(T,visite() 中序遍历二叉树 InOrderTraverse(T,visite() 后序遍历二叉树 PostOrderTraverse(T,visite() 按层次遍历 levelTraverse(T, visite(),§6.2 二叉树,12,§6.2 二叉树,二叉树的定义 二叉树的性质 二叉树的存储结构,13,§6.2.2 二叉树的性质(1),性质1 在二叉树的第i层上至多有2i-1个结点(i 1 )； 性质2 深度为k的二叉树上至多有2k-1个结点(k 1 ) ； 性质3 设任意一棵二叉树中有n0个度为0的结点，n2个度为2个结点，则有：n0 = n2+1；,§6.2 二叉树,满二叉树：一棵深度为k且有 2k1个结点的二叉树。即：所有非终端结点的度都等于2，且所有树叶都分布在同一个层次上。,完全二叉树：将深度为k，有n个结点的二叉树自上而下，自左向右进行编号，当且仅当编号与深度为k的满二叉树中前n个结点一一对应。,14,§6.2.2 二叉树的性质(2),性质4 完全二叉树的深度为 k log2n +1 或 k= log2(n+1) ； 性质5 将完全二叉树自上而下，自左向右地编号，对任意一结点i（1 i n）的结点X有： A、若i1，则X是根；若i1, 则X的PARENT(i)=i/2; B、若X有左孩子，则X左孩子LCHILD(i)=2i； C、若X有右孩子，则X右孩子RCHILD(i)=2i1； D、若i为奇数且i1，则X的左兄弟为i1； E、若i为偶数且in，则X的右兄弟为i1；,§6.2 二叉树,i 为偶数,i 为奇数,15,§6.2 二叉树,二叉树的定义 二叉树的性质 二叉树的存储结构,16,§6.2.3 二叉树的存储结构(1),设计存储结构的一般原则: 保存所有的数据元素 正确地表达出数据元素之间的逻辑关系 便于对数据进行操作和运算 节省空间 二叉树的存储结构： 顺序存储结构 链式存储结构,§6.2 二叉树,17,§6.2.3 二叉树的存储结构(2),顺序存储结构 根据二叉树性质5，则可以利用一数组存放一棵完全二叉树.,§6.2 二叉树,A,C,B,E,D,F,.,结点在完全二叉树中的编号与数组下标一致，可利用性质5来计算结点的双亲、孩子、兄弟的下标。,18,§6.2.3 二叉树的存储结构(3),对于普通二叉树，可以将其补足成完全二叉树后再进行编号，存储。,§6.2 二叉树,?,基本数据结构： #define MAX_TREE_SIZE 100 typedef TElemType SqBiTreeMAX_TREE_SIZE; SqBiTree bt;,19,§6.2.3 二叉树的存储结构(4),链式存储结构,§6.2 二叉树,左孩子指针,二叉链表,右孩子指针,结点值,三叉链表,亲代指针,20,§6.2.2 二叉树的存储结构(5),§6.2 二叉树,二叉树,三叉链表表示,二叉链表表示,基本数据结构： typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;,21,§6.3 遍历二叉树,遍历二叉树 遍历二叉树的递归与非递归算法 表达式求值 二叉树的运算举例 层序遍历二叉树,22,§6.3.1 遍历二叉树(1),遍历：按某种次序访问二叉树的所有结点，且每个结点仅访问一次。 “访问”的含义非常的广泛，可以是对结点作各种处理，如输出结点的信息等。 根据二叉树的结构：左子树_根_右子树，可以把对二叉树的遍历分解为三项子任务： 访问根 D 遍历左子树 L 遍历右子树 R 根据这三项任务的执行次序的不同，有六种可能的遍历方案： DLR、LDR、LRD 先左后右 DRL、RDL、RLD 先右后左 如果约定先左后右，则取前三种方案,§6.3 遍历二叉树,23,§6.3.1 遍历二叉树(2),根据访问根的时机不同，将这三种遍历方案分别称为: 先根遍历（先序遍历）DLR 中根遍历（中序遍历）LDR 后根遍历（后序遍历）LRD,§6.3 遍历二叉树,24,§6.3 遍历二叉树,遍历二叉树 遍历二叉树的递归与非递归算法 表达式求值 二叉树的运算举例 层序遍历二叉树,25,§6.3.2 遍历二叉树的递归与非递归算法(1),先序遍历二叉树 若二叉树为空，则空操作；否则 访问根； 先序遍历左子树； 先序遍历右子树；,§6.3 遍历二叉树,void PreOrderTraverse (BiTree T) if (!T) return; visit(T-data);/访根 PreOrderTraverse (T-lchild); PreOrderTraverse (T-rchild); ,26,§6.3.2 遍历二叉树的递归与非递归算法(2),先序遍历二叉树,§6.3 遍历二叉树,A,C,B,E,D,L,F,K,G,J,I,H,27,§6.3.2 遍历二叉树的递归与非递归算法(3),中序遍历二叉树 若二叉树为空，则空操作；否则 中序遍历左子树； 访问根； 中序遍历右子树；,§6.3 遍历二叉树,void InOrderTraverse (BiTree T) if (!T) return; InOrderTraverse (T-lchild); visit(T-data);/访根 InOrderTraverse (T-rchild); ,28,§6.3.2 遍历二叉树的递归与非递归算法(4),中序遍历二叉树,§6.3 遍历二叉树,A,C,B,E,D,L,F,K,G,J,I,H,29,§6.3.2 遍历二叉树的递归与非递归算法(5),后序遍历二叉树 若二叉树为空，则空操作；否则 后序遍历左子树； 后序遍历右子树； 访问根；,§6.3 遍历二叉树,void PostOrderTraverse (BiTree T) if (!T) return; PostOrderTraverse (T-lchild); PostOrderTraverse (T-rchild); visit(T-data);/访根 ,30,§6.3.2 遍历二叉树的递归与非递归算法(6),先序遍历二叉树,§6.3 遍历二叉树,A,C,B,E,D,L,F,K,G,J,I,H,31,§6.3.2 遍历二叉树递归与非递归算法(7),中序遍历的非递归算法(借助堆栈实现) void InOrderTraverse ( BiTree bt, void(*visit)(BiTree) /中序遍历的非递归算法 InitStack(S); Push(S,T); While (!StackEmpty(S) /栈非空时 While (GetTop(S,p) /将结点p的右子树入栈 /if /while /InOrderTraverse,§6.3 遍历二叉树,32,例 已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，.， Nm个度为m的结点，试问该树中有多少个叶子结点。,§6.3 遍历二叉树,33,解答:解决此类问题的关键是要把树的结点个数和树中各结点的度联系起来。 设该树中叶子结点个数为N0。 则该树结点个数为N0+N1+.+Nm= ，又该树的结点个数也为1+ 所以,§6.3 遍历二叉树,34,例 用一维数组存放的一棵二叉树如下图所示。写出后序遍历该二叉树时访问结点的序列。 解答：GHDBEFCA,§6.3 遍历二叉树,35,例 设m和n分别为二叉树中的两个结点，问： （1）当n在m的左方，先序遍历时n在m的前面吗？中序遍历时n在m的前面吗？ （2）当n在m的右方，中序遍历时n在m的前面吗？ （3）当n是m的祖先，先序遍历时n在m的前面吗？后序遍历时n在m的前面吗？ （4）当n是m的子孙，中序遍历时n在m的前面吗？后序遍历时n在m的前面吗？,§6.3 遍历二叉树,36,（1）当n在m的左方，先序遍历时n在m的前面吗？中序遍历时n在m的前面吗？,§6.3 遍历二叉树,解答：（1）n在m的左方可以有上图所示的两种情况。因为先序遍历为“根左右”，因此由上图可知，先序遍历中， n可以在m的前面，也可以在m的后面；中序遍历为“左根右”，由上图可知，中序遍历中n必在m的前面。,37,（2）当n在m的右方，中序遍历时n在m的前面吗？,§6.3 遍历二叉树,解答：（2）中序遍历序列中，n必在m的后面。,38,（3）当n是m的祖先，先序遍历时n在m的前面吗？后序遍历时n在m的前面吗？,§6.3 遍历二叉树,解答：（3）先序遍历时，祖先必定在子孙的前面；后序遍历时，祖先必在子孙的后面。（对于中序遍历，左孩子及其子孙必定在祖先的前面，而右孩子及其子孙必定在祖先的后面。） （4） 当n是m的子孙，中序遍历时n在m的前面吗？后序遍历时n在m的前面吗？ 解答：由（3）可知，中序遍历时，n可能在m之前，也可能在m之后。而后序遍历时，n必定在m的前面。,39,例 给定一棵用二叉链表表示的二叉树，每个结点都有2个指针（lchild,rchild)，分别用来表示指向其左、右子女，该树的根结点指针为t，试编写一个非递归求二叉树的叶子结点数目的算法函数。,§6.3 遍历二叉树,40,解析：本题是要求编写算法求出二叉链表表示二叉树的叶子结点的个数，并且已经给出了该二叉树的基本存储结构，注意这里要求用非递归的方法进行求解。其实求解二叉树中叶子结点的个数，可以采用非递归的方法进行二叉树的遍历。在遍历的过程中如果遇到了叶子结点，则将其统计到叶子结点的个数里面。当遍历完整个二叉树时，也就求出了叶子结点的个数。算法的思想是首先定义二叉树的二叉链表的存储结构，采用中序遍历二叉树的方法。这里用到辅助栈S，先将根结点入栈，当栈非空时，让指针一直向左走到尽到，并将所经历的结点入栈。再将空指针退栈，弹出栈顶结点。若该结点是叶子结点，则叶子数目变量count加1。然后再将该结点的右子树入栈，中序遍历完整个二叉树后，函数返回叶子总数count。,§6.3 遍历二叉树,41,答案：二叉树的二叉链表的存储结构： typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /左右孩子指针 BiTNode,*BiTree; int CountLeaf(BiTree t) BiTree p; /定义工作指针p int count=0; /初始化叶子数目变量count InitStack(S); /建立空栈,§6.3 遍历二叉树,42,Push(S,t); /将二叉树的根结点入栈 while(!StackEmpty(S) /栈非空时 while(GetTop(S,p) /函数返回叶子结点的数目 /CountLeaf,§6.3 遍历二叉树,43,§6.3.2 遍历二叉树递归与非递归算法(8),先序遍历的非递归算法(借助堆栈实现) void PreOrderTraverse (BiTree bt) if (!bt) return; InitStack(S); push(S, bt); /树根的指针进栈 while (!EmptyStack(S) pop(S, p); while(p) /沿着左链一路向下 visit(p-data); /访问 if(p-rchild) push(S,p-rchild); /右孩子进栈 p=p-lchild; ,§6.3 遍历二叉树,44,§6.3 遍历二叉树,遍历二叉树 遍历二叉树的递归与非递归算法 表达式求值 二叉树的运算举例 层序遍历二叉树,45,§6.3.3 表达式求值,表达式求值,§6.3 遍历二叉树,算术表达式中的二叉树表示,Model ：a+b*(c-d)-e/f,a,b,c,d,e,f,+,*,-,-,/,先序遍历得到前缀表达式： - + a * b c d / e f 中序遍历得到中缀表达式： a + b * ( c d ) e / f 后序遍历得到后缀表达式： a b c d - * + e f / -,46,§6.3 遍历二叉树,遍历二叉树 遍历二叉树的递归与非递归算法 表达式求值 二叉树的运算举例 层序遍历二叉树,47,§6.3.4 二叉树的运算举例(1),计算二叉树中的结点数 Number() 思路：二叉树结点数1+左子树结点数+右子树结点数,§6.3 遍历二叉树,int Number(BiTree bt) if(!bt) return 0; /空二叉树 else nl=Number(bt-lchild); nr=Number(bt-rchild); return 1+nl+nr; ,void Number(BiTree bt, int ,48,计算二叉树中叶子结点的数目 Leafs() 思路：叶子数左子树叶子数+右子树叶子数,§6.3.4 二叉树的运算举例(2),§6.3 遍历二叉树,int Leafs(BiTree bt) if(!bt) return 0; /空二叉树 if(！bt-lchild ,void Leafs(BiTree bt，int ,49,例 已知深度为h的二叉树以一维数组BT(1:2h-1)作为其存储结构，请写一算法，求该二叉树中叶结点的个数。,§6.3 遍历二叉树,50,§6.3 遍历二叉树,int Leafs(BiTree bt,int h) /层序遍历二叉树，统计叶子结点的个数 len=2h-1; count=0; for(i=1;ilen) count+; /i结点没有孩子，i结点就是叶子结点 else if(bt2*i+1=0 ,51,§6.3.4 二叉树的运算举例(3),计算二叉树的深度 Depth() 思路： 深度 = max(左子树深度，右子树深度) + 1,§6.3 遍历二叉树,int Depth(BiTree bt) if(!bt) return 0; hl=Depth(bt-lchild); /计算bt的左子树深度 hr=Depth(bt-rchild); /计算bt的右子树深度 return (hlhr ? (h1+1):(hr+1) ,52,§6.3 遍历二叉树,遍历二叉树 遍历二叉树的递归与非递归算法 表达式求值 二叉树的运算举例 层序遍历二叉树,53,§6.3.5 层序遍历二叉树(1),自上而下、自左向右地遍历二叉树，先被访问结点的孩子先被访问。遍历思想为： 空树, 结束。 初始化一个空队列Q, 树根入队; 队头e元素出队, 访问e; 如果e有左孩子, 则左孩子入队; 如果e有右孩子, 则右孩子入队; 如果队列不空转3; 否则结束,§6.3 遍历二叉树,54,§6.3.5 层序遍历二叉树(2),算法 LevelTraverse() void LevelTraverse(BiTree bt) /按层次遍历二叉树算法 if( !bt ) return ; /空树 InitQueue(Q); /初始化空队列Q EnQueue(Q, bt); /根入队 while( !EmptyQueue(Q) ) DeQueue(Q, p); /队头p出队 visit(p-data); /访问p if(p-lchild) EnQueue(Q，p-lchild); /p的左孩子入队 if(p-rchild) EnQueue(Q,p-rchild); /p的右孩子入队 ,§6.3 遍历二叉树,55,§6.4 线索二叉树(1),二叉树的遍历序列是线性序列。在二叉树上找某个结点在某种遍历序列中的直接前驱或直接后继，只能在对二叉树遍历时动态求得。 如何在遍历过程中保留下结点的前驱和后继的信息呢？最直接的办法也许就是给每个结点增加两个指针。这样做会使得结构的存储密度大大降低。 做如下规定： 若结点有左子树，则其lchild域指向其左孩子，否则指向其前驱；若结点有右子树，则其rchild域指向其右孩子，否则指向其后继。 其中：,§6.4 线索二叉树,56,§6.4 线索二叉树(2),二叉树的二叉线索存储表示：,§6.4 线索二叉树,typedef enum PointerTagLink, Thread; typedef struct BiThrNode TElemType data; struct BiThrNode *lchild, *rchild; PointerTag Ltag, Rtag; /左右标志 BiThrNode, * BiThrTree;,中序线索二叉树：,57,§6.4 线索二叉树(3),二叉树的二叉线索存储：,§6.4 线索二叉树,?,58,§6.4 线索二叉树(4),线索化，就是在已知二叉链的前提下，填写每个结点左线索LTag域和右线索RTag域。 若要建立中(先、后）序线索，则在中(先、后）序遍历过程中完成线索化操作。 通过中序遍历建立中序线索化链表的算法在教材P.134,135中。 遍历线索二叉树 在线索二叉树中，由于可以直接找到每个结点的后继或前驱，所以遍历可以用非递归的方法实现，而且不必借助栈.(算法 P.134),§6.4 线索二叉树,59,以双向线索链表为二叉树的存储结构时的中序遍历算法（6.5）： Status InorderTraverse_Thr(BiThree T, Status (*Visit)(TElemType e) /T为头结点指针,中序遍历带头结点的线索二叉树T p=T-lchild; /p指向根结点 while(p!=T) /空树或遍历结束时，p=T while(p-LTag=link) p=p-lchild; /沿左指针找中序序列第一个结点 if(!Visit(p-data) return ERROR; /访问左子树为空的结点 while(p-RTag=Thread /InorderTraverse_Thr,§6.4 线索二叉树,60,中序遍历建立中序线索化二叉链表的算法（6.6）： Status InorderThreading(BiThrTree /InorderThreading,§6.4 线索二叉树,61,递归中序线索化二叉树的算法（6.7）： void InThreading(BiThrTree /右子树线索化 /InThreading /递归函数最底层首先找到中序序列的第一个结点p，对其前驱线索，对pre(此时为头结点指针Thrt）进行后继线索，再继续,§6.4 线索二叉树,62,§6.5 树和森林,树的存储结构 森林与二叉树的转换 树和森林的遍历,63,§6.5.1 树的存储结构(1),双亲表示法,§6.5 树和森林,#define MAX_TREE_SIZE 100 typedef struct PTNode TElemType data; int parent; PTNode; typedef struct PTNode nodesMAX_TREE_SIZE; int r,n; /根位置和结点数目 Ptree;,64,§6.5.1 树的存储结构(2),孩子表示法,§6.5 树和森林,typedef struct CTNode int child; struct CTNode *next; *ChildPtr; typedef struct TElemType data; ChildPtr firstchild; CTBox; typedef struct CTBox nodesMAX_TREE_SIZE; int r,n; /根位置和结点数目 CTree;,65,§6.5.1 树的存储结构(1),孩子-兄弟表示法,§6.5 树和森林,typedef struct CSNode TElemType data; struct CSNode *firstchild, *nextsibling; CSNode, CSTree;,树的孩子兄弟表示可以将树转化为二叉树,66,§6.5 树和森林,树的存储结构 森林与二叉树之间的转换 树和森林的遍历,67,§6.5.2 森林和二叉树之间的转换(1),树用孩子兄弟链表表示时，就已转化成二叉树了。一棵树可以唯一地转换成一棵右子树为空的二叉树。,§6.5 树和森林,森林转化为二叉树： 把森林中的每一棵树转换成二叉树； 将所有二叉树的树根用线相连； 以第一棵二叉树的树根为圆心，顺时针转45度。,68,§6.5.2 森林和二叉树之间的转换(2),§6.5 树和森林,69,§6.5 树和森林,树的存储结构 森林与二叉树之间的转换 树和森林的遍历,70,§6.5.3 树和森林的遍历(1),先序遍历树：若树不空，则 访问根； 从左至右先序遍历根的各个子树。,§6.5 树和森林,后序遍历树：若树不空，则 从左至右后序遍历根的各个子树。 访问根。,先根序列：RADEBCFGHK 后根序列：DEABGHKFCR,先序序列：RADEBCFGHK 中序序列：DEABGHKFCR 后序序列：EDKHGFCBAR,等价,71,§6.5.3 树和森林的遍历(2),先序遍历树，等价于先序遍历由这棵树转换而成的二叉树； 后序遍历树，等价于中序遍历由这棵树转换而成的二叉树；,§6.5 树和森林,先序遍历森林：若森林不空，则 访问第一棵树的根结点； 先序遍历第一棵树根结点的子树森林； 先序遍历森林中去掉第一棵树后剩下的树构成的森林 中序遍历森林：若森林不空，则 中序遍历第一棵树根结点的子树森林； 访问第一棵树的根结点； 中序遍历森林中去掉第一棵树后剩下的树构成的森林,72,§6.5.3 树和森林的遍历(3),§6.5 树和森林,等价,先序序列：ABCDEFGHIJ 中序序列：BCDAFEHJIG,先序序列：ABCDEFGHIJ 中序序列：BCDAFEHJIG 后序序列：DCBFJIHGEA,73,§6.6 赫夫曼树及其应用,最优二叉树（赫夫曼树） 赫夫曼树的构造 赫夫曼编码,74,补充-树的应用：等价类问题（简介）,等价关系和等价类的定义 等价类的划分算法,75,补充-树的应用：等价类问题（简介）,等价关系的定义：,设R为定义在集合S上的一个关系，若R是自反的，对称的和传递的，则R称为等价关系。,76,补充-树的应用：等价类问题（简介）,对称的。从T的序偶表示式中可以看出T是传递的，逐个检查序偶，如T, T,有T;同理， T, T,有T。故T是R上的等价关系。同样地，从关系矩阵亦可验证T是等价关系。,77,补充-树的应用：等价类问题（简介）,78,补充-树的应用：等价类问题（简介）,等价类的定义： 设X为集合S上的等价关系，对任何xS，由 xR = y| ys xRy 给出的集合 xR S 称为由x S生成的一个R等价类。 若R是集合S上的一个等价关系，则由这个等价关系可产生这个集合的唯一划分。即可以按R将S划分为若干不相交的子集S1,S2,.,它们的并即为S，则这些子集Si便称为S的R等价类。,79,补充-树的应用：等价类问题（简介）,等价问题是现实世界中广泛存在的一种关系，许多应用问题可以归结为按给定的等价关系划分某集合为等价类，通常称这类问题为等价问题。,80,补充-树的应用：等价类问题（简介）,81,补充-树的应用：等价类问题（简介）,82,补充-树的应用：等价类问题（简介）,等价关系和等价类的定义 等价类的划分算法,83,补充-树的应用：等价类问题（简介）,划分等价类的算法（P140): 假设集合S有n个元素，m个形如(x,y)(x,yS）的等价偶对确定了等价关系R，现求S的划分。确定等价类的算法如下： （1）令S中每个元素各自形成一个只含单个成员的子集，记着S1,S2,.,Sn。 （2）重复读入m个偶对，对每个偶对（x,y),判定x和y所属子集。不失一般性，假设xSi,ySj,若SiSj,则将Si并入Sj,并置Si为空（或将Sj并入Si,并置Sj为空)。则当m个偶对都被处理过后，S1,S2,.,Sn中所有非空子集即为S的R等价类。,84,补充-树的应用：等价类问题（简介）,等价类的划分算法，需要对集合进行的操作有3个： （1）是构造只含单个成员的集合； （2）是判定某个单元素所在的子集； （3）归并两个互不相交的集合为一个集合。 由此，我们需要一个包含这3种操作的抽象数据类型MFSet。 ADT MFSet 数据对象：若设S是MFSet型的集合，则它由n(n0)个子集Si(i=1,2,.,n)构成，每个子集的成员都是子界-maxnumbermaxnumber内的整数；,85,补充-树的应用：等价类问题（简介）,数据关系：S1S2. Sn=S Si S(i=1,2,.,n) 基本操作： Initial(,86,补充-树的应用：等价类问题（简介）,ADT MFSet用什么实现？该抽象数据类型以集合为基础，需要实现3种基本操作，我们可利用树型结构表示MFSet。 如何表示呢？ 约定：以森林F=(T1,T2,.,Tn)表示MFSet型的集合S,森林中的每一棵树Ti(i=1,2,.,n)表示S中的一个元素子集Si(Si S,i=1,2,.,n),树中每个结点表示子集中的一个成员x,为操作方便，令每个结点中含有一个指向其双亲的指针，并约定根结点的成员兼作子集的名称。,87,补充-树的应用：等价类问题（简介）,如：子集S1=1,3,6,9和S2=(2,8,10)可以用树型结构分别表示如下：,88,补充-树的应用：等价类问题（简介）,由于各子集的成员均不相同，这种树型结构易于实现查找和合并操作。,合并,89,补充-树的应用：等价类问题（简介）,为便于操作的实现，我们采用双亲表示法作为树的存储结构。 typedef PTree MFSet; /MFSet采用树的双亲存储表示,90,补充-树的应用：等价类问题（简介）,查找操作的实现（算法6.8）： int find_mfset(MFSet S,int i) /查找成员i所属子集Si的根 /（根结点成员兼作子集的称） if(iS.n) return -1; /i不属于S中任一子集 for(j=i;S.nodesj.parent0;j=S.nodesj.parent) ; return j; /find_mfset 算法的时间复杂度为O(h)，h为树的深度。,91,补充-树的应用：等价类问题（简介）,集合合并操作的实现（算法6.9）： Status merge_mfset(MFSet /merge_mfset,算法的时间复杂度为O(1) 。,92,补充-树的应用：等价类问题（简介）,集合合并操作的实现（算法6.9）所形成的树的深度与树的形成过程有关。一个极端的例子P142-图6.19 树的深度影响了查找操作的复杂度。 为了使生成的树的深度下降，改进的方法： 在“并”操作之前，先判断子集中所含成员的数目，然后将成员少的子集根结点指向含成员多的子集的根。 为此，相应的存储结构修改为：令根结点的parent存储子集中所含成员数目的负值。,93,补充-树的应用：等价类问题（简介）,修改后的合并算法如下(算法6.10)： Status merge_mfset(MFSet /将Si并入Sj中去 /if,94,补充-树的应用：等价类问题（简介）,else/将Sj并入Si中去 S.nodesi.parent+= S.nodesj.parent ; S.nodesj.parent=i; /else return OK; /mix_mfset 可以证明，按算法6.10进行“并”操作得到的集合树，其深度不超过 log2n+1 ，n为集合S中所有子集所含成员的总和。,95,例6-1 假设集合S=x|1x n是正整数,R是S上的一个等价关系。 R=(1,2),(3,4),(5,6),(7,8),(1,3),(5,7),(1,5),.，现求S的等价类。,96,分别处理各个等价偶对(1,2),(3,4),(5,6),(7,8):,.,处理偶对(1,3) (合并s1和S3)=,s1,s3,97,处理偶对(5,7)(合并s5和s7)=,98,处理偶对(1,5)(合并s1和s5)=,9,n,s9,sn,.,随着子集的合并，树的深度也越来越大，为了进一步确定元素所在集合的时间，还可以进一步将算法6.8改进=算法6.11。当所查元素i不在树的第二层时，在算法中增加一个“压缩路径”的功能，即将所有从根到元素i路径上的元素都变成树根的孩子。,99,§6.6.1 最优二叉树（赫夫曼树）(1),路径：从一个结点到另一个结点所经过的分支。 路径长度L：路径上分支的数目。 树的路径长度：从树根到每一个结点的路径产度之和。 树的带权路径长度：树中所有的叶子结点的带权路径长度之和，通常记作：,§6.6 赫夫曼树及其应用,WPL=7*2+5*2+2*2+4*2=36,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,100,§6.6.1 最优二叉树（赫夫曼树）(2),哈夫曼树：由权值为w1,w2,.,wn)的n片叶子构成的所有二叉树中，WPL值最小的二叉树。,§6.6 赫夫曼树及其应用,WPL=7*1+5*2+2*3+4*3=35,WPL=7*1+5*2+2*3+4*3=35,哈夫曼树不一定是最矮的树 哈夫曼树形态可能不唯一,101,§6.6 赫夫曼树及其应用,最优二叉树（赫夫曼树） 赫夫曼树的构造 赫夫曼编码,102,§6.6.2 赫夫曼树的构造(1),1952年，Huffman提出了一个构造最优二叉树的一个精巧算法，被人们称为Huffman算法 。 算法的思想： 将权值为w1, w2, ., wn的n个叶子构成一个具有n棵树的森林F； 从森林F中选取根权值最小的两棵树，分别作为左子树和右子树，再新添一个结点做为根，合并成一棵新的二叉树，新二叉树根的权值等于左、右子树根权值之和； 重复2，直到F中只剩下一棵树为止，这棵树就是所求的Huffman树。,§6.6 赫夫曼树及其应用,103,§6.6.2 赫夫曼树的构造(2),构造n个叶子的哈夫曼树需要经过n-1次合并，每次合并都要增加一个新结点。所以n个叶子的哈夫曼树上有且仅有2n-1个结点。 哈夫曼树上不存在度为1的结点。我们把这种不存在度为1的结点的二叉树称为严格二叉树或正则二叉树。,§6.6 赫夫曼树及其应用,存储表示： typedef struct unsigned int child; unsigned int parent, lchild,rchild; HTNode, *HuffmanTree; 构造算法参见教材（P.147）,104,§6.6 赫夫曼树及其应用,最优二叉树（赫夫曼树） 赫夫曼树的构造 赫夫曼编码,105,§6.6.3 赫夫曼编码(1),§6.6 赫夫曼树及其应用,编码 发送 ： 电文 0,1 序列 (比特流) 接收： 0, 1序列 电文 解码 例如： 电文“abcdedacafcfadcacfdaef” 字符集 a, b, c, d, e, f 字符出现次数 6, 1, 5, 4, 2, 4 ,106,§6.6.3 赫夫曼编码(2),§6.6 赫夫曼树及其应用,电文“abcdedacafcfadcacfdaef” 字符集 a, b, c, d, e, f 编码方案：,前缀码：任何字符的编码都不是其他字符编码的前缀,107,§6.6.3 赫夫曼编码(3),§6.6 赫夫曼树及其应