数据结构——C语言描述第4章-树及二叉树.pptx

《数据结构——C语言描述第4章-树及二叉树.pptx》由会员分享，可在线阅读，更多相关《数据结构——C语言描述第4章-树及二叉树.pptx（136页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构C语言描述（慕课版）第4章树及二叉树编著：张同珍&学校：上海交通大学树及二叉树1.树的定义和术语3.二叉树的遍历和实现4.最优二叉树及其应用2.二叉树5.等价类问题6.树和森林树在一个元素集合中，如果每个元素都有唯一的前驱，但可以有多个后继，这样的结构就叫树结构。树是有限个(n0)元素组成的集合，在这个集合中，有一个结点称为根，如果有其他的结点，这些结点又被分为若干个互不相交的非空子集，每个子集又是一棵树，称为根的子树，每个子树都有自己的根，子树的根为根结点的孩子结点。在这个示例中，A是根，其余结点分成了3个互不相交的非空子集，3个子集是分别以B、C、D为根的子树。术语：父结点的父结点

2、称祖父结点，从根到树中某个结点的路径上经过的所有结点，包括根结点，都称为这个结点的祖先结点，相对的，这些结点称为祖先结点的子孙结点。一个结点的子树的根称为该结点的孩子结点或儿子结点，反之，相对于孩子结点，该结点称为父结点。同一个父结点的结点互为兄弟结点，同一个祖父但不同父亲的结点互称为堂兄弟结点。A为B、C、D的父结点；B、C、D为A的孩子结点；除了A自身，树中所有其余结点都称为A的子孙结点；G、I、H是D的子孙结点；对结点G来说，D是它的父结点，A是它的祖父结点，而A和D都是G的祖先结点；E、F互为兄弟结点；F和G互为堂兄弟结点。0102030405术语：树结构中每个结点拥有的孩子结点的个数

3、称为该结点的度，度为0的结点称叶子结点或终端结点，度不为0的结点称非叶子结点或中间结点或非终端结点。树的度是树中每个结点的度的最大值。A的度为3，G的度为1，树的度为3，A、G是中间结点，H是叶子结点。术语：根的层次数通常规定为1，其余结点的层次数是其父结点的层次数加1。树中结点实际上是具有一种层次关系。树中所有结点的层次数的最大值就是树的高度。A的层次数为1；F、I的层次数为3；H的层次数为4；树的高度为4。术语：如果其孩子结点都被规定了一定的顺序，如谁是第一个孩子、谁是第二个孩子等，这棵树就称有序树。如果这是一棵有序树，D有两个孩子，其中G就是D的第一个孩子、I是D的第二个孩子。术语：有限

4、棵互不相交的树(0)构成的集合称为森林(Forest)。森林在形式上和树有很大的关系：如果删除一棵树的根结点，就得到了该树的所有子树构成的森林。如果将构成森林的各棵树之上增加一个根结点，使得这些树的根结点都作为新增根结点的孩子结点，那么就得到了一棵树。树的ADT：数据及关系:有限(n0)个相同类型的元素组成的集合，其中一个元素称为根，如果还有其余元素，则这些元素被分为若干个互不相交的非空子集，每个子集又是一棵树，每个子树又有自己的根，子树的根是根的孩子结点。树的ADT：操作:Constructor：Getroot:前提：已知树中的某一结点p。结果：得到结点p的第一个儿子结点。FirstChil

5、d：前提：已知根结点的数据元素值。结果：创建一棵树。前提：已知一棵树。结果：得到树的根结点。前提：已知树中的某一结点p和它的一个儿子结点u。结果：得到结点p的挨着儿子结点u的下一个儿子结点v。NextChild：前提：已知某一关键字key。结果：检索具有关键字key的结点v。Retrieve:前提：已知某结点p及新结点的数据值value。结果：根据value值创建一个新结点q,并将其插入作为结点p的儿子结点。InsertChild:前提：已知某结点p及它的儿子结点的序号k。结果：删除结点p的第k个儿子结点。DeleteChild:结果：若树未创建，返回True，否则返回False。IsEmpt

6、y:物理结构：遇到的问题:顺序结构：元素易存，关系难存。链式结构：每个结点孩子个数不同，故结构不统一。树及二叉树1.树的定义和术语3.二叉树的遍历和实现4.最优二叉树及其应用2.二叉树5.等价类问题6.树和森林二叉树二叉树的定义二叉树的存储二叉树的操作及实现二叉树的性质二叉树二叉树是有限个(n0)结点的集合。它或者为空，或者有一个结点作为根结点，如果有其余结点，其余结点分成左右两个互不相交的子集作为根结点的左右子树，每个子树又都是一棵二叉树。01OPTION二叉树不是一棵特殊的树。树是生活中实际存在的结构类型，而二叉树更多地是作为一种工具。02OPTION二叉树中结点个数可以为0，允许一棵空二

7、叉树存在，树中结点个数不能为0，必须至少是1。03OPTION二叉树中左右孩子要明确指出是左还是右，即便只有一个孩子，也要指明它是左子还是右子。有序树中孩子只是进行了排序，没有左右之分。有2个结点的二叉树和树的示例：二叉树的各种形态：（a）（b)是二叉树（c）是树如果一个二叉树中的每一层结点数量都达到了最大值，则该二叉树称为满二叉树或丰满树。如果一个二叉树有k层，其中k-1层都是满的，第k层可能缺少一些结点，但缺少的结点是自右向左的，则这样的二叉树称为完全二叉树。满二叉树是完全二叉树，完全二叉树不一定是满二叉树。满二叉树中的叶子结点都分布在最后一层，完全二叉树的叶子可能分布在倒数两层上。二叉树

8、二叉树的定义二叉树的存储二叉树的操作及实现二叉树的性质二叉树的性质：性质2：一棵高度为k的二叉树，最多具有2k1个结点。性质3：对于一棵非空二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有:n0n21。性质4：具有n个结点的完全二叉树的高度k=log2n +1。性质1：一棵非空二叉树的第i层上最多有2i-1个结点（i1）。性质5：如果对一棵有n个结点的完全二叉树中的所有结点按层次自上而下、每一层自左而右依次对其编号。若设根结点的编号为1，则对编号为i的结点（1in)，有:二叉树的性质：010302如果i1，则该结点是二叉树的根结点；如果i1，则其父亲结点的编号为。如果2in，则编号为

9、i的结点无左儿子；否则，其左儿子的编号为2i。如果2i+1n，则编号为i的结点无右儿子；否则，其右儿子的编号为2i+1。证明：性质3：又因二叉树中除了根结点，每个结点都可以视作是由其父结点的一条分支引出的，所以二叉树中共有n-1条分支，这些分支又是由度为1和度为2的结点发出的，所以有：n-11*n12*n2（2）在一棵二叉树中，设结点总数为n、度为0的结点有n0个、度为1的结点为n1个、度为2的结点为n2个。则有：nn0n1n2（1）对于一棵非空二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有:n0n21。结合（1）（2）得:n0n21（3）二叉树二叉树的定义二叉树的存储二叉树的操作

10、及实现二叉树的性质二叉树的存储用一组连续的空间即数组来存储二叉树中的结点。每个结点除了包括元素值，还包括表达二叉树父子关系的字段。顺序存储：如果是一棵完全二叉树，用顺序结构存储可以更加简单。完全二叉树可以省去left、right字段，从下标关系中直接反映父子关系。父下标为i，左子下标2i+1,右子下标2i+2。顺序存储方式的好处是数组访问简单，不利之处是它需要事先预估出数据的最大规模。二叉树的链式存储有两种形式，一种是标准形式，一种是广义标准形式。链式存储：标准形式：链式存储:二叉树的链式存储有两种形式，一种是标准形式，一种是广义标准形式。广义标准形式:LeftDataRightParent用

11、广义标准形式存储找父结点容易，但找父结点的频率不高，因此标准形式才是二叉树最常用的存储结构。二叉树二叉树的定义二叉树的存储二叉树的操作及实现二叉树的性质二叉树的操作-在内存中创建一棵二叉树；-属性类操作如判二叉树空、获取根结点、求以某结点为根的二叉树中的结点个数和高度；-二叉树的整体删除；-按前序、后序和中序遍历二叉树的操作；二叉树结点的插入、删除操作，因不知其具体意义和要求，放到后序有实际插入、删除意义的章节中讲解。二叉树的操作voidcreateTree(BTree*tree,Typeflag);/创建一棵二叉树intSize(Node*T);/以T为根的二叉树的结点个数。intHeigh

12、t(Node*T);/以T为根的二叉树的高度。intIsEmpty(BTree*tree)return(tree-root=NULL);/二叉树为空返回非0，否则为0structNode*GetRoot(BTree*tree)returntree-root;voidMakeEmpty(BTree*tree);DelTree(tree-root);tree-root=NULL;/使二叉树为空voidPrintPreOrder(Node*T);/按前序遍历打印以T为根的二叉树的结点的数据值二叉树的操作voidPrintInOrder(Node*T);/按中序遍历打印以T为根的二叉树的结点的数据值v

13、oidPrintPostOrder(Node*T);/按后序遍历打印以T为根的二叉树的结点的数据值voidLevelOrder(Node*T);/按层次遍历打印以T为根的二叉树的结点的数据值voidDelTree(BTree*tree);/删除以T为根的二叉树，并释放所有相关结点操作算法思路借助一个队列来管理结点，先将根结点的值读入，在内存中创建根结点并主动将根结点地址进队，从队列中逐个将结点出队、提醒用户输入出队结点左右孩子信息、为孩子创建结点空间，并将孩子结点链到父结点左右孩子字段，并将孩子结点地址进队，让它们在队中等候出队、进而再生它们自己的孩子。反复循环，直到队空。二叉树的建立：函数S

14、ize和Height。如Size操作，如果二叉树为空，返回0，否则就返回根的个数1加上根的左、右子树中的结点个数；如Height操作，如果二叉树为空，返回0，否则就返回根的高度1加上根的左、右子树高度中的最大值。求属性的两个操作：必须先删除它的左、右子树，才能删除这棵二叉树的根结点，如果先删除根结点，左右子树信息就会找不到了，而删除左右子树可以用递归来实现。删除一棵二叉树：部分操作实现typedefstructTypedata;structNode*left;structNode*right;Node;typedefstructstructNode*root;TypestopFlag;BTre

15、e;部分操作实现voidcreateTree(BTree*tree,Typeflag)/创建一棵二叉树Typee,el,er;Typex;Queueque;Node*p,*pl,*pr;initialize(&que,30);tree-stopFlag=flag;printf(Pleaseinputtheroot:);scanf(%c,&e);if(e=flag)tree-root=NULL;return;部分操作实现scanf(%c,&x);/去除输入中的回车符p=(Node*)malloc(sizeof(Node);p-data=e;p-left=NULL;p-right=NULL;tre

16、e-root=p;/根结点为该新创建结点enQueue(&que,p);部分操作实现while(!isEmpty(&que)p=front(&que);/获得队首元素并出队deQueue(&que);printf(Pleaseinputtheleftchildandtherightof%crespectly,using%casnochild:,p-data,flag);scanf(%c%c,&el,&er);scanf(%c,&x);/去除输入中的回车部分操作实现if(el!=flag)/该结点有左孩子pl=(Node*)malloc(sizeof(Node);pl-data=el;pl-le

17、ft=NULL;pl-right=NULL;p-left=pl;enQueue(&que,pl);部分操作实现if(er!=flag)/该结点有右孩子pr=(Node*)malloc(sizeof(Node);pr-data=er;pr-left=NULL;pr-right=NULL;p-right=pr;enQueue(&que,pr);部分操作实现intSize(Node*T)/得到以t为根二叉树结点个数。if(!T)return0;return1+Size(T-left)+Size(T-right);intHeight(Node*T)/得到以T为根二叉树的高度。intmaxl,maxr;

18、if(!T)return0;maxl=Height(T-left);maxr=Height(T-right);if(maxlmaxr)return1+maxl;elsereturn1+maxr;部分操作实现voidDelTree(BTree*tree)/删除以二叉树tree,并释放所有相关结点Queueque;Node*p;p=GetRoot(tree);if(!p)return;/二叉树为空initialize(&que,30);enQueue(&que,p);部分操作实现while(!isEmpty(&que)p=front(&que);deQueue(&que);if(p-left)en

19、Queue(&que,p-left);if(p-right)enQueue(&que,p-right);free(p);tree-root=NULL;树及二叉树1.树的定义和术语3.二叉树的遍历和实现4.最优二叉树及其应用2.二叉树5.等价类问题6.树和森林二叉树的遍历：遍历即对结构中每个数据元素进行访问且每个元素只访问一次。010203层次遍历：如果二叉树为空，遍历操作为空。否则，从第一层开始，从上至下，逐层访问每一层结点。当访问某一层时，从左到右逐个访问每一个结点。前序遍历：如果二叉树为空，遍历操作为空。否则，先访问根结点，然后前序遍历根的左子树，再前序遍历根的右子树。可简记为：“根左右”

20、。中序遍历：如果二叉树为空，遍历操作为空。否则，先中序遍历根的左子树，然后访问根结点，最后中序遍历根的右子树。可简记为：“左根右”。对于一个二叉树，可以按照以下几种策略进行遍历：04后序遍历：如果二叉树为空，遍历操作为空。否则，先后序遍历根的左子树，然后后序遍历根的右子树，最后访问根结点。可简记为：“左右根”。从前序、中序、后序遍历的定义可以看出，它是以根相对于左右子树的访问顺序来决定的：前序根在前、中序根在中、后序根在后。至于左右子树，总是按照先左后右，因为先右后左和先左后右的操作处理是类似的。二叉树的遍历：二叉树的遍历：层次遍历：B、L、C、S、F、D、G、I、H前序遍历：B、L、S、C、

21、F、D、G、I、H中序遍历：L、S、B、F、C、I、G、H、D后序遍历：S、L、F、I、H、G、D、C、B二叉树的遍历实现层次遍历中序遍历后序遍历前序遍历两个遍历序列确定二叉树二叉树的层次遍历：二叉树的层次遍历为从上到下逐层访问，每一层从左到右逐个访问每个结点。下图中二叉树的层次遍历序列为B、L、C、S、F、D：层次遍历算法如果二叉树为空，遍历操作为空，结束。否则，首先将根结点进队，然后反复循环进行以下操作：用一个队列管理二叉树中的结点，算法思想如下：0102队首结点出队、访问，如果该结点有左子，左子进队；如果该结点有右子，右子进队。继续判队空与否，如果不空则进入下一轮循环；如果空则遍历结束。

22、voidLevelOrder(Node*T)/按层次遍历顺序打印以T为根的二叉树的结点的数据值。Queueque;Node*p;if(!T)return;initialize(&que,30);enQueue(&que,T);while(!isEmpty(&que)p=front(&que);deQueue(&que);printf(%c,p-data);if(p-left)enQueue(&que,p-left);if(p-right)enQueue(&que,p-right);二叉树的遍历实现层次遍历中序遍历后序遍历前序遍历两个遍历序列确定二叉树二叉树的前序遍历如果二叉树为空，遍历操作为空

23、。否则，先访问根结点，然后前序遍历根的左子树，再前序遍历根的右子树。可简记为：“根左右”。右图的前序遍历序列：B、L、S、C、F、D前序遍历的递归算法voidPrintPreOrder(Node*T)/按前序遍历顺序打印以T为根的二叉树的结点的数据值。if(!T)return;printf(%c,T-data);PrintPreOrder(T-left);PrintPreOrder(T-right);前序遍历的非递归算法用一个栈辅助前序遍历的非递归算法实现：如果二叉树为空，遍历结束。将根结点压栈。如果栈不空，重复以下操作，直到栈空。弹栈得到栈顶元素并访问它的值。如果该出栈元素右子不为空，右子进

24、栈。如果该出栈元素左子不为空，左子进栈。前序遍历的非递归算法前序遍历的非递归算法实现voidPrintPreOrder(Node*T)/按前序遍历顺序打印以T为根的二叉树的结点的数据值。stacks;Node*p;if(!T)return;Initialize(&s);push(&s,T);while(!isempty(&s)p=top(&s);pop(&s);printf(%c,p-data);if(p-right)push(&s,p-right);if(p-left)push(&s,p-left);非递归算法的时间复杂度分析：时间由程序中的循环决定，每次循环访问一个结点，共n个结点，需要循

25、环n次，故时间复杂度为O(n)。二叉树的遍历实现层次遍历中序遍历后序遍历前序遍历两个遍历序列确定二叉树二叉树的后序遍历：如果二叉树为空，遍历操作为空。否则，先后序遍历根的左子树，然后后序遍历根的右子树，最后访问根结点。可简记为：“左右根”。下图的后序遍历序列：S、L、F、D、C、B后序遍历的递归算法voidPrintPostOrder(Node*T)/按后序打印以T为根的二叉树的结点的数据值。if(!T)return;PrintPostOrder(T-left);PrintPostOrder(T-right);printf(%c,T-data);将根结点压栈，状态0压栈。如果二叉树为空，遍历结

26、束。如果栈不空，反复做以下操作，直到栈空。1号栈保存结点的地址，2号栈保存结点的访问状态：状态为0，表明未考虑过其左子；状态为1，表示已考虑过其左子但未考虑过其右子；状态为2，表示已经考虑过其两子。后序遍历的非递归算法：后序遍历的l非递归算法：如果状态为0，将状态改为1后压入2号栈，并将1号栈顶结点的非空左子及状态0压栈；如果状态为1，将状态改为2后压入2号栈，并将1号栈顶结点的非空右子及状态0压栈；如果状态为2，直接访问1号栈顶结点，1号栈弹栈。获取1号栈栈顶结点，2号栈弹栈得到结点的访问状态：voidPrintPostOrder(Node*T)/按后序打印以T为根的二叉树的结点的数据值。i

27、ntflag100;stacks;inti;Node*p;if(!T)return;i=-1;Initialize(&s);push(&s,T);flag+i=0;后序遍历的非递归算法实现while(!isempty(&s)p=top(&s);switch(flagi)case0:flagi=1;if(p-left)push(&s,p-left);flag+i=0;break;后序遍历的非递归算法实现case1:flagi=2;if(p-right)push(&s,p-right);flag+i=0;break;case2:printf(%c,p-data);pop(&s);i-;break;

28、后序遍历的非递归算法实现非递归算法的时间复杂度分析：时间由程序中的循环决定，每次循环弹栈一个结点，结点状态由0变1一次，结点状态由1变2一次，由2输出一次，共n个结点，需要循环3n次，故时间复杂度为O(n)。二叉树的遍历实现层次遍历中序遍历后序遍历前序遍历两个遍历序列确定二叉树二叉树的后序遍历：如果二叉树为空，遍历操作为空。否则，先后序遍历根的左子树，然后后序遍历根的右子树，最后访问根结点。可简记为：“左右根”。下图的后序遍历序列：S、L、F、D、C、B后序遍历的递归算法voidPrintPostOrder(Node*T)/按后序打印以T为根的二叉树的结点的数据值。if(!T)return;P

29、rintPostOrder(T-left);PrintPostOrder(T-right);printf(%c,T-data);将根结点压栈，状态0压栈。如果二叉树为空，遍历结束。如果栈不空，反复做以下操作，直到栈空。1号栈保存结点的地址，2号栈保存结点的访问状态：状态为0，表明未考虑过其左子；状态为1，表示已考虑过其左子但未考虑过其右子；状态为2，表示已经考虑过其两子。后序遍历的非递归算法：后序遍历的l非递归算法：如果状态为0，将状态改为1后压入2号栈，并将1号栈顶结点的非空左子及状态0压栈；如果状态为1，将状态改为2后压入2号栈，并将1号栈顶结点的非空右子及状态0压栈；如果状态为2，直接访

30、问1号栈顶结点，1号栈弹栈。获取1号栈栈顶结点，2号栈弹栈得到结点的访问状态：voidPrintPostOrder(Node*T)/按后序打印以T为根的二叉树的结点的数据值。intflag100;stacks;inti;Node*p;if(!T)return;i=-1;Initialize(&s);push(&s,T);flag+i=0;后序遍历的非递归算法实现while(!isempty(&s)p=top(&s);switch(flagi)case0:flagi=1;if(p-left)push(&s,p-left);flag+i=0;break;后序遍历的非递归算法实现case1:flag

31、i=2;if(p-right)push(&s,p-right);flag+i=0;break;case2:printf(%c,p-data);pop(&s);i-;break;后序遍历的非递归算法实现非递归算法的时间复杂度分析：时间由程序中的循环决定，每次循环弹栈一个结点，结点状态由0变1一次，结点状态由1变2一次，由2输出一次，共n个结点，需要循环3n次，故时间复杂度为O(n)。二叉树的遍历实现层次遍历中序遍历后序遍历前序遍历两个遍历序列确定二叉树两个遍历序列唯一确定一棵二叉树010302已知一个二叉树的前序遍历、中序遍历能唯一确定一棵二叉树。已知一个二叉树的后序遍历、中序遍历能唯一确定一棵

32、二叉树。已知一个二叉树的前序遍历、后序遍历不能唯一确定一棵二叉树。对于两个由数组存储的前序遍历和中序遍历：算法思想由前序遍历序列中的第一个元素确定二叉树的根。在中序遍历中找到此根，数组中根之前的元素为左子树的中序遍历序列；数组中根之后的元素为右子树的中序遍历序列。根据步骤2确定的此根左子树中元素的个数，确定前序遍历中根的左子树的前序遍历序列；确定前序遍历中根的右子树的前序遍历序列。01OPTION02OPTION03OPTION利用递归，对左子树的前序遍历、中序遍历同上确定左子树的根；对右子树的前序遍历、中序遍历同上确定右子树的根；直到遍历序列为空。04OPTION已知一个二叉树的前序和中序序

33、列为：前序序列：B、L、S、C、F、D、G、I、H中序序列：L、S、B、F、C、I、G、H、D已知一个二叉树的前序遍历、中序遍历能唯一确定一棵二叉树。对于两个由数组存储的后序遍历和中序遍历：算法思想由后序遍历序列中的最后一个元素确定二叉树的根。在中序遍历中找到此根，数组中根之前的元素为左子树的中序遍历序列；数组中根之后的元素为右子树的中序遍历序列。根据步骤2确定的此根左子树中元素的个数，确定后序遍历中根的左子树的后序遍历序列；确定后序遍历中根的右子树的后序遍历序列。利用递归，对左子树的后序遍历、中序遍历同上确定左子树的根；对右子树的后序遍历、中序遍历同上确定右子树的根；直到遍历序列为空。010

34、20304已知一个二叉树的后序和中序序列为：后序序列：S、L、F、I、H、G、D、C、B中序序列：L、S、B、F、C、I、G、H、D已知一个二叉树的后序遍历、中序遍历能唯一确定一棵二叉树如：前序序列：A、B后序序列：B、A已知一个二叉树的前序遍历、后序遍历不能唯一确定一棵二叉树树及二叉树1.树的定义和术语3.二叉树的遍历和实现4.最优二叉树及其应用2.二叉树5.等价类问题6.树和森林最优二叉树及其应用最优二叉树的定义哈夫曼编码哈夫曼算法最优二叉树二叉树中任意两个结点间的路径长度为其路径上的分支总数。二叉树的路径长度为根到树中各个结点的路径长度之和。二叉树的加权路径长度指从根结点到各个叶子结点路

35、径上的分支数乘以该叶子的权值之和。能使达到最小的二叉树，称为最优二叉树。最优二叉树：对同一组带权的叶子结点(A，10)，(B，20)，(C，30)：图（a）二叉树形态中，=101+202+302=110；图（b）二叉树形态中，=301+202+102=90。即不同的二叉树的形态会使得其带权路径长度不同。最优二叉树及其应用最优二叉树的定义哈夫曼编码哈夫曼算法哈夫曼算法构造思路：最优二叉树中，尽量让权值越大的结点离根结点越近。构造最优二叉树的哈夫曼算法：对于给定的一个带权结点集合U。A.如果U中只有一个结点，操作结束，否则转向B。B.在集合中选取两个权值最小的结点x、y，构造一个新的结点z，新结点

36、z的权值为结点x、y的权值之和，在集合U中删除结点x和y并加入新结点z，然后转向A。由哈夫曼算法构造出的最优二叉树称哈夫曼树。对一组带权结点：U=(A，3)，(B，8)，(C，10)，(D，12)，(E，50)，(F，4)，按照哈夫曼算法构造一棵最优二叉树。哈夫曼算法实现213定义结点结构Node，Node包含三个字段：-data为结点的权值、-parent为结点的父结点地址、-left和right为结点的左右孩子的地址。用一个数组来存储结点，结点地址用数组下标值表示。0下标分量不用，从下标为1的数组分量开始存储数据。假定树中叶子结点有n个，构造的中间结点因度都为2，故有n-1个。因此最优二叉

37、树中结点总数为n+n-1=2n-1个。typedefintType;typedefstruct1Typedata;intparent;intleft,right;Node;/在所有父亲为0的元素中找最小值的下标intminIndex(Nodea,intn,intm)inti,min;min=m;for(i=n;i=m;i-)if(ai.parent=0)&(ai.dataamin.data)min=i;returnmin;Node*BestBinaryTree(Typea,intn)Node*BBTree;intmin,minor,i,j;intm=n*2;/共2n-1个结点，下标为0处不放结

38、点BBTree=(Node*)malloc(sizeof(Node)*m);for(i=m-1,j=0;jn;i-,j+)BBTreei.data=aj;BBTreei.parent=0;BBTreei.left=0;BBTreei.right=0;/positioniisreadyforthenextnewnodewhile(i!=0)/数组左侧尚有未用空间，即新创建的结点个数还不足min=minIndex(BBTree,m-1,i+1);BBTreemin.parent=i;minor=minIndex(BBTree,m-1,i+1);BBTreeminor.parent=i;BBTree

39、i.data=BBTreemin.data+BBTreeminor.data;BBTreei.parent=0;BBTreei.left=min;BBTreei.right=minor;i-;returnBBTree;对右侧一组数据元素构造哈夫曼树后结果：123456789101187372215745012108301224513345249511000000738106000000indexdataparentleftright算法时间复杂度分析：最优二叉树及其应用最优二叉树的定义哈夫曼编码哈夫曼算法哈夫曼编码：02OPTION一般字符编码采用等长策略，即每个字符的二进制编码长度一样。如A

40、SCII码。03OPTION通讯中，希望传送的编码越短越好，尤其高频传送的字符，希望其编码尽可能短，而低频字，可以比较长些。04OPTION哈夫曼树就可以用来构造这样的不等长编码。通讯业务中，字符通常需要通过传送其二进制编码来完成。01OPTION哈夫曼编码：左分支标上0、右分支标上1，从根到每个叶子结点的路径上获得的0、1序列就作为该叶子结点的编码，这个编码就称为哈夫曼编码。对哈夫曼树从根开始做如下操作：哈夫曼编码：哈夫曼编码是一组不等长编码，编码间须满足互不为前缀的要求。如对于编码110来说，1、11都是它的前缀，而110又是110X的前缀。码表中的不等长编码有如下两个要求：对于任何一个编

41、码，它的前缀码不得同时出现。对于任何一个编码，以它为前缀的编码也不得同时出现。哈夫曼树，任何叶子结点的编码都不会出现在根到其他叶子的路径上，即不会成为其他叶子结点编码的前缀。哈夫曼编码：已构造出哈夫曼树，计算哈夫曼编码的算法：01020304将某叶子结点设为当前结点，顺着当前结点往上追溯到父亲结点如果当前结点是父亲的左子则输出一个0如果当前结点是父亲的右子则输出一个1之后设父亲为当前结点，反复以上操作，直到当前结点为根结点。从以上过程中输出的0、1序列的逆序即其哈夫曼编码。哈夫曼编码的算法实现：函数的参数BBTree数组，保存了哈夫曼树的结构。函数用了一个栈保存输出的0、1序列，对一个叶子，在

42、其每一步向上追溯父结点的过程中，将输出的0或1进栈，当追溯工作因达到根结点而结束时，将栈中元素弹栈，即得到哈夫曼编码。数组HFCode用来存储获得的所有哈夫曼编码，数组的每个分量指向了一个字符串，它是某个叶子结点的哈夫曼编码。哈夫曼编码的算法实现：算法实现首先从数组尾部开始，逐步为每一个叶子求其哈夫曼编码，共有n个叶子。首先以该叶子为当前结点，观察当前结点的父结点，如果父结点的左子为当前结点，将一个0压入栈中，如果父结点的右子为当前结点，将一个1压入栈中，然后将父结点再设置为当前结点，反复继续如上操作，直到当前结点为根结点。哈夫曼编码的算法实现：voidHuffmanCode(NodeBBTr

43、ee,intm,char*HFCode,intn)/m=2*n-1,m为BBTree数组中元素的个数，n为待编码元素的个数inti,j,k,parent;stacks;Initialize(&s);for(i=0;in;i+)HFCodei=(char*)malloc(sizeof(char)*n);for(i=0,j=m;in;i+,j-)k=j;parent=BBTreek.parent;while(parent!=0)哈夫曼编码的算法实现：if(BBTreeparent.left=k)push(&s,0);elsepush(&s,1);k=parent;parent=BBTreek.pa

44、rent;k=0;while(!isEmpty(&s)HFCodeik=top(&s);pop(&s);k+;HFCodeik=0;算法时间复杂度分析：算法包含了两重循环，外循环次数为叶子结点的个数n；内循环串行地做了两件事：一个是从叶子逐步追溯到根获取哈夫曼编码的逆序；一个是逐步弹栈获取哈夫曼编码。树及二叉树1.树的定义和术语3.二叉树的遍历和实现4.最优二叉树及其应用2.二叉树5.等价类问题6.树和森林等价类问题假设有一个集合S上的关系R，x1,x2S，有x1Rx2为真或者假，则称R是集合S上的等价关系。010203等价关系满足自反性：x1S,x1Rx1为真。对称性：x1,x2,如果x1R

45、x2为真，必有x2Rx1为真。传递性：x1,x2,x3,如果x1Rx2为真且x2Rx3为真，则x1Rx3为真。例二：一个装满彩色球的盒子，里面有红、黄、绿、蓝、紫、黑、白7中颜色的小球，盒中任意两个小球之间的同色关系R就满足等价关系。例一：班级作为一个集合，其中R是同性别关系。等价类问题例一中，男生集合和女生集合各是一个等价类；例二中，同种颜色的球构成的子集是一个等价类，7中颜色共有7个等价类。x1S，其所属等价类是集合S的一个子集S1，这个子集有这样的特点：x2S1,有x1Rx2为真。等价类问题01030204对于单个的不相交集来说，集合中所有元素地位平等，任意两个元素之间有着等价关系。划分

46、中的每个子集即集合A中的各个元素称为不相交集。表示时，对属于同一不相交集的元素只要打上相同标志即可，对属于不同不相交集的元素，需要打上不同标志。等价类问题合并、查找，不相交集又称为并查集(union-findssets)。不相交集的基本操作：是对两个不相交集进行合并，使之成为一个新的、更大的不相交集。也可以说当对分属于两个不相交集的元素，添加了等价关系，则根据传递性，也要合并这两个不相交集。合并union(si,sj)：当有元素x插入时，可以通过把单个元素x视作由它自己构成了一个新的不相交集，让该新的不相交集和某个已有的不相交集合并，就完成了插入任务。特别地：是对集合S中的元素x找到它所属的不

47、相交集，即给出不相交集的标志。查找find(x)：不相交集的存储：线性表存储、树形存储。线性表存储：将集合S中的所有元素放置在同一个数组中，而数组中的每个分量除了存储元素还要存储元素所属的不相交集的标志。abcde f ghkt0122010222flagdata将集合S中的所有元素放置在同一个数组中，而数组中的每个分量除了存储元素，还要存储元素的父结点下标。特殊地，当某个元素的父结点下标为-1，这个元素就是树根。01OPTION树形存储：02OPTION每个不相交集用一棵树来表示，然后用树根下标表示所属不相交集的标志。集合中的任何一个元素沿着父结点字段都可以追溯到根，找到所属的不相交集合的标

48、志。代表不同的不相交集的树组成了一个森林。03OPTION双亲表示法的树形结构如何实现合并、查找：合并：当a，b两个不相交集要合并时，可以将b中所有元素都当作a的根结点的儿子，但时间花费是b的所有元素个数的线性阶，存储退化为线性表存储法。如果简单地把b的根作为a的根结点的儿子，时间花费是常量阶的。查找：对于一个元素只需要沿着这棵树找到树根，得到树根的下标标志，就完成了查找任务，因此时间花费是这棵树的高度。显然树的高度越低越好，最低时一个不相交集可以退化为两层，一个元素作为树根，其余元素作为树根的儿子结点。两种存储方法比较：如果采用线性表存储法，则查找是常量阶、合并是线性阶；如果采用树形存储方法

49、，则查找是对数阶（确切说，是树的高度）、合并是常量阶。树形存储法是不相交集的常用物理结构。树形存储法的两个不相交集，可以通过两个方面进行算法优化：合并操作：按照两个树的高度来判别。将高度小的树并入高度大的树，以高度大的树的根结点作为合并后的树根。这样可以尽量阻止合并后树的高度的增加，查找就会因树的高度不增而提高效率。特别地：当两棵树等高时，合并后的树高度增加1.树形存储法的两个不相交集，可以通过两个方面进行算法优化：采取越近期查过的结点越往根结点靠近的原则，将查找结点及其到根结点路径上所有的结点（不含根结点）全部改为根结点的儿子结点，此方法也称为路径压缩法。查找：好处是：查找频率高的结点会集中

50、分布在根部附近，但如果每个元素具有平均查找概率，反而会因为查找后多出来的移动操作，多耗费了时间。如查找1后：树及二叉树1.树的定义和术语3.二叉树的遍历和实现4.最优二叉树及其应用2.二叉树5.等价类问题6.树和森林树和森林存储结构：用双亲法表示树和森林。用二叉树表示树和森林。当使用二叉树来表示树和森林时，不仅能存储结点、结点间关系，树和森林的基本操作也可以方便地通过二叉树的基本操作来实现。树和森林存储问题树和森林的遍历树、森林和二叉树转换用二叉树表示树和森林孩子兄弟表示法：每个结点除了保存数据，还保存了该结点的最大孩子的结点地址和最大弟弟的结点地址。树和森林存储问题树和森林的遍历树、森林和二