《大学数据结构课件树和二叉树》由会员分享，可在线阅读，更多相关《大学数据结构课件树和二叉树（54页珍藏版）》请在金锄头文库上搜索。
1、内容提要n6.1 树的定义及基本术语树的定义及基本术语n6.2 二叉树二叉树n6.3 编历二叉树编历二叉树n6.4 线索二叉树线索二叉树n6.5 二叉排序树二叉排序树n6.6 平衡二叉树平衡二叉树n6.7 树和森林树和森林n6.8 哈夫曼树及应用哈夫曼树及应用1 16.1 树的定义及基本术语1、树的定义、树的定义(1)树的一般定义树的一般定义 树树是包含n个结点的有限集合，在这个集合上定义了一个唯一的关系，这个关系满足下面的条件： I. 存在唯一的一个结点，它没有前驱，称为根 II. 除了根结点外，其它结点有且仅有一个前驱 III. 除了根结点外，任何结点ai(0 im)，都存在唯一 的一个从
2、根到ai的结点序列a0, a1, a2,., am ，其中， a0是根。这个序列称为从根到ai的路径。 a0a1a2a3a4a52 2树的定义及基本术语(contd)(2)树的递归定义树的递归定义树树是包含n个结点的有限集，在这个集合上定义了唯一的关系，它满足下面的条件：I. 有个特定的称为根的结点；II. 当n1时，除了根以外的其余结点根据它们之间 的关系可分为m个不相交的有限集T1,T2,.,Tm，其中，每个有限集都是一棵树。这些树称为根的子树。abcdefT1=b,e,f;T2=c;T3=d3 3树的定义及基本术语(contd)(3)树的基本术语树的基本术语1. 根根,唯一没有前驱的结点
3、2. 度度,结点的度结点的度是结点的子树数目,树的度树的度是指结点度的最大值3. 叶子叶子，度为0的结点，也称终端结点终端结点4. 分枝结点分枝结点，叶子之外的结点，也称非终端结点。除了根以外的分枝结点又称内部结点。5. 双亲双亲、子女子女、祖先祖先、子孙子孙，结点子树的根称为结点的子女，该结点就是它子女的双亲；某结点的祖先是指从根到该结点的路径上的全部结点；结点的子树中全部结点都是该结点的子孙。abcdef4 4树的定义及基本术语(contd)(3)树的基本术语树的基本术语6. 兄弟、堂兄弟兄弟、堂兄弟，同一个结点的子女互为兄弟，双亲为兄弟的结点互称堂兄弟。7. 结点的层次层次、树的深度树的
4、深度(高度)，根为第1层，结点的层次是其双亲层次加1。树的深度是指结点的最大层数。8. 有序树、无序树有序树、无序树，如果结点的各子树自左向右是有次序的，则称有序树，否则称无序树9. 森林森林，m棵互不相交的树就构成了森林。abcdefg第1层第2层第3层5 56.2 二叉树1. 二叉树的概念二叉树的概念每个结点最多有2棵子树，并且子树有左右之分，不能任意颠倒。二叉树有5种形态：空树 只有一个根 只有左子树 只有右子树 有两个子树2. 二叉树的性质二叉树的性质在二叉树的第i层上至多有2i1个结点(i=1)深度为k的二叉树至多有2k-1个结点。1234567896 6二叉树(contd)2. 二
5、叉树的性质二叉树的性质 设二叉树中，叶结点数为n0,度为1的结点数为n1,度为2的结点数为n2,则有： n0 = n2 + 1 因为 N=n0+n1+n2=1+n1*1+n2*2 具有n个结点的完全二叉树的深度为 log2n +1log2n 表示 log2n取整满二叉树满二叉树：具有最多结点数的二叉树（即一棵深度为k且有2k-1 个结点的二叉树）完全二叉树完全二叉树：将满二叉树从右向左删除叶子的结果，因此 ,结点数 n2k-1-11234567897 7二叉树(contd)3. 二叉树的存储结构二叉树的存储结构 (1) 顺序存储顺序存储，利用数组按照完全二叉树的方式对结点编号，根据编号将结点存
6、放在数组中相应的位置中。#define N 50 /二叉树的最大结点数typedef elemtype SQTREEN; /顺序存储的二叉树SQTREE bt;ABCEF123456A B C E F0 1 2 3 4 5 6 7 8 99 9二叉树(contd)3. 二叉树的存储结构二叉树的存储结构(2)链式存储链式存储，利用二叉链表或三叉链表typedef struct treenodeelemtype data; /结点数据 /指向左右孩子的指针 struct treenode *lchild,*rchild /*,*parent*/; TREENODE,*TREENODEPTR,*BT
7、REEABCEF DATAPARENTLCHILDRCHILDlchilddatarchildlcjilddataparentrchild1010define N 50 /定义二叉树最大结点数void createtree(BTREE *root)int value,front,rear; TREENODEPTR t,qN; /q是队列，front,rear是队头队尾下标。 scanf(%d,&value); /开始创建根结点 if(value=0)*root=NULL; return;/输入0，表示空结点 *root=(TREENODEPTR)malloc(sizeof(TREENODE);
8、 (*root)data=value; rear=front=1; qfront=*root;/根指针入队二叉树(contd)4. 二叉树的建立二叉树的建立 (1) 按层序遍历顺序为输入顺序按层序遍历顺序为输入顺序 while(front=n) p=sm; m-; /出栈一结点 if(plchild!=NULL)/自左向右入栈 top+; stop=plchild; if(prchild!=NULL) top+; stop=prchild; /while(m if(top=bottom-1)break;/如果这层没有结点,表明遍历结束遍历二叉树(contd)(2)二叉树的遍历算法二叉树的遍历算
9、法 (6) 层序遍历层序遍历 n=bottom; m=top; /准备下一层处理 bottom=top+1; while(m=n) p=sm; m-;/出栈一结点 if(prchild!=NULL)/自右向左栈 top+; stop=prchild; if(plchild!=NULL) top+; stop=plchild; /while(m if(top=bottom-1)break; /while while(top=1) printf(%d ,stopdata);top-; printf(n); 4567321bottom(旧旧)topbottom2222遍历二叉树(contd)3. 二
10、叉树遍历算法的应用二叉树遍历算法的应用 (1)求树的深度求树的深度int depth(BTREE root) int hr,hl; /记录左右子树的深度 if(!root) return 0;/空树深度为0 else hl=depth(rootlchild); hr=depth(rootrchild); if(hl=hr) return hl+1; else return lr+1; 2323void inorder(PTREENODEPTR root)/root是三叉链表的二叉树 PTREENODEPTR p; int n=0; p=root; /记录叶子数量while(1) while(p
11、lchild) p=plchild; /一直向左递归 while(1)/循环返回 if(prchild!=NULL) p=prchild; break;/进入右子树，继续递归 if(prchild=NULL&plchild=NULL) n+; while(pparent!=NULL&(p=pparentrchild|pparentrchild=NULL) p=pparent; if(pparent=NULL) /返回到了根 printf(the tree has %d leafsn,n); return; p=pparentrchild;break; /while(1)/while(1) 遍历
12、二叉树(contd)3. 二叉树遍历算法的应用二叉树遍历算法的应用 (2)求二叉树叶子结点的个数求二叉树叶子结点的个数24246.4 线索化二叉树1.线索化线索化遍历二叉树的结果是将二叉树的结点排列成某种顺序，使这些结点形成线性关系。但这种线性关系只能在重新遍历二叉树时才会重新获得。如果在第一次遍历二叉树时就将这种线性关系保存下来，这种操作称为“线线索化索化”。为了将二叉树线索化，需要重新定义二叉树结点的数据类型。中序线索化结果中序线索化结果ABCDENULLNULLtypedef struct treenode elemtype data; struct treenode *lchild,*
13、rchild; int ltag,rtag; /*ltag为0,lchild指向左孩子，否则指向线索化序列中的前驱；rtag为0, rchild指向右孩子，否则指向线索化序列中的后继*/ TREENODE, *TREENODEPTR;2525线索化二叉树(contd) 0 lchild域指示结点的左孩子ltag = 1 lchild域指示结点的前驱 0 rchild域指示结点的右孩子rtag = 1 rchild域指示结点的后继以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表线索链表，其中指向结点前驱和后继的指针，叫做线索线索。加上线索的二叉树称之为线索二叉树线索二叉树。对二叉树
14、以某种次序遍历使其变为线索二叉树的过程叫做线线索化索化。中序线索化结果中序线索化结果ABCDENULLNULLlchild ltagdata rtagrchild2626TREENODEPTR pre;void inordthread(TREENODEPTR *thrt,TREENODEPTR t)/为线索化后的树增加一个头结点thrt，便于操作 (*thrt)=(TREENODEPTR)malloc(sizeof(TREENODE); (*thrt)ltag=0; (*thrt)ltag=1; (*thrt)rchild=(*thrt);/开始右线索指向自身 if(t=NULL) /如果树t
15、为空，左指针也指向自己 (*thrt)lchild=(*thrt); else /前驱指针指向线索头结点 (*thrt)lchild=t; pre=(*thrt); inthreading(t);/开始线索化 /线索化后,pre为最右端结点,它的后继指向头结点 prerchild=(*thrt); prertag=1; (*thrt)rchild=pre;/头结点右线索指向最右结点 线索化二叉树(contd)2. 线索化算法线索化算法(以中序线索为例以中序线索为例)：void inthreading(TREENODEPTR p)/*对以p为根的二叉树进行中序线索化*/ if(p) /在线索化过
16、程中，pre一直是当前访问结点的前驱结点 inthreading(plchild); /p的左孩子为空, 则指向前驱 if(plchild=NULL) pltag=1; plchild=pre; /访问p时，并不知道p的后继 if(prerchild=NULL) prertag=1; prerchild=p; /将pre的右孩子指向后继 pre=p; /进入右子树前，将前驱指针指向当前结点 inthreading(prchild); ABCDE2727void tinorder(TREENODEPTR thrt)/thrt是线索二叉树的头结点指针 TREENODEPTR p; p=thrtlc
17、hild; /p指向根 while(p!=thrt) /当遍历到最后有p=thrt while(pltag=0) p=plchild; /寻找最左端结点 printf(%d,pdata); while(prtag=1&prchild!=thrt) /顺着后继链，访问后继，直到后继链断掉 p=prchild; printf(%d,pdata); p=prchild; /转到上面寻找后继,p的后继就是p的右子树最左端结点 线索化二叉树(contd)3. 利用线索遍历二叉树利用线索遍历二叉树(以中序为例以中序为例)：ABCDE28286.5 二叉排序树1.二叉排序树二叉排序树：又称二叉查找树二叉查找
18、树。二叉排序树或者是棵空树，或者是棵具有下面特征的二叉树：(1) 若它的左子树不空，左子树上的所有结点值都小于(大于)根结点值(2) 若它的右子树不空，右子树上的所有结点值都大于(小于)根结点值(3) 左右子树也都是二叉排序树20164011364381425382929BTREE insert(BTREE root,int value)/将value插入到二叉排序树root中，将新的树返回 TREENODEPTR p,q,r; r=(TREENODEPTR)mallloc(sizeof(TREENODE); rdata=value; rlchild=rrchild=NULL; if(root
19、=NULL) return r; p=root; while(p) q=p; /记下插入的位置 if(pdata value) p=plchild; /向左子树方向插 else p=prchild; /向右子树方向插 /while if(qdata value) qlchild=r; else qrchild=r; return root;二叉排序树(contd)2、二叉排序树的建立算法、二叉排序树的建立算法BTREE creattree(BTREE root) int value; scanf(%d,&value); while(value)/输入0表示结束 root=insert(root
20、,value); scanf(%d,&value); return root; 3030TREENODEPTR search(TREENODE root,TREENODEPTR *f, int value)/*在二叉排序树root中查找值是value的结点，返回结点指针，并用f返回该结点双亲结点*/ TREENODEPTR p,q,r; q=NULL; p=root; while(p&pdata!=value) q=p; if(pdatavalue) p=plchild; else p=prchild; *f=q; return p;二叉排序树(contd)3、二叉排序树的查找算法、二叉排序树
21、的查找算法3131算法思想算法思想：由于删除结点后，二叉排序树仍必须是二叉排序树，并且最好不增加树的深度，因此应该区分三种情况(假设P是要删除的结点)：(1) 如果P是叶子结点，直接删除即可(2) 如果P是单枝结点，可以直接用子树的根 代替P做P双亲的孩子(3) 如果P是双枝结点，则可以用P的前驱或后继结点H替换P，然后在删除H，对H的删除必然属于(1)(2)两种情况。二叉排序树(contd)4、二叉排序树的删除算法、二叉排序树的删除算法FP+FP+H+FP+H+FPHSC3232BTREE delete(BTREE root, int value)/在二叉排序树中删除值是value的结点，返
22、回删除后的树 TREENODEPTR f,p,q,h; p=search(root,&f,value); /f将是p的双亲结点指针 if(p=NULL)return root; if(plchild=NULL|p rchild=NULL) /p是叶子 h=NULL; /h将替代p else if(plchild=NULL) h=prchild; else if(prchild=NULL) h=plchild;二叉排序树(contd)4、二叉排序树的删除算法、二叉排序树的删除算法else /p是双枝结点 f=p; q=p rchild; /开始寻找p的后继q,f将是q的双亲 while(qlch
23、ild!=NULL) f=q; q=qlchild; pdata=qdata; /将q的数据复制到p中，开始删除q if(qlchild=NULL|qrchild=NULL)h=NULL; else if(qlchild=NULL)h=qrchild; else h=qlchild; p=q; /p成为f的子女 /else if(f=NULL) root=h; else if(flchild=p) flchild=h; else frchild=h; free(p); return root; 33336.6 平衡二叉树1、平衡二叉树、平衡二叉树：AVL树树，左右子树的深度差的绝对值不超过1的
24、二叉排序树，并且左右子树也是平衡二叉树。平衡二叉树的查找效率最高，因为n个结点的二叉树中，平衡二叉树的深度最低。二叉排序树的深度决定了查找比较的次数。平衡二叉树非平衡二叉树3434平衡二叉树(contd)2、平衡二叉树的平衡调整、平衡二叉树的平衡调整当向平衡二叉树插入结点或删除结点时，会导致某棵子树深度的变化，在某些情况下，就会导致平衡二叉树失去平衡。这时就需要对二叉树进行平衡调整。下面以插入结点为例，平衡调整需要两种旋转操作：单旋单旋和双旋双旋。当插入新节点时，AVL树的根与插入位置之间路径上的节点的平衡状态可能会变化。因此，插入完一个新节点后，要沿着通向根的路径回溯，检查各节点的平衡状态，
25、一旦发现不平衡节点，就进行平衡化旋转。这样会将不平衡限制最小范围内，并且通常每插入一个节点最多需要一次调整。3535平衡二叉树(contd)从发生不平衡的节点开始，沿回溯路径向下取两层节点。(1) 如果这三个节点成一条直线，则需要采用单旋进行平衡化。左旋是指将线上最左端节点向下旋转，右旋左旋是指将线上最左端节点向下旋转，右旋是指将线上最右端节点向下旋转。是指将线上最右端节点向下旋转。(2) 如果这三个节点成一条折线，则需要采用双旋进行平衡化。为了判断旋转的情况，我们将结点的左右子树的深度差定义为“平衡因子”。当平衡因子是正负2时，该结点失去平衡。3636平衡二叉树(contd)(1) 左单旋的
26、情况左单旋的情况原来的AVL树插入一结点，A点不平衡左单旋的结果void LeftRotate(TREENODEPTR * Ptr) /Ptr是发生不平衡的结点 TREENODEPTR *tmp=(*Ptr)rchild; (*Ptr)rchild=tmplchild;tmplchild=*Ptr;*Ptr=tmp;3737平衡二叉树(contd)(2) 右单旋的情况右单旋的情况void RightRotate(TREENODEPTR * Ptr) TREENODEPTR tmp=(*Ptr)lchild; (*Ptr)lchild=tmprchild;tmprchild=*Ptr;*Ptr=
27、tmp;原来的AVL树 插入一结点，A点不平衡右单旋的结果3838平衡二叉树(contd)(3) 先左后右双旋的情况先左后右双旋的情况void LeftRightRotate(TREENODEPTR * Ptr) LeftRotate(&(*Ptr)lchild);RightRotate(Ptr); 原来的AVL树插入一结点，A点不平衡先左旋再右旋3939平衡二叉树(contd)(4) 先右后左双旋的情况先右后左双旋的情况void RightLeftRotate(TREENODEPTR * Ptr) RightRotate(&(*Ptr)rchild); LeftRotate(Ptr); 原来
28、的AVL树插入一结点，A点不平衡先右旋再左旋4040typedef struct nodeint data; struct node *lchild,*rchild; int balance; /平衡因子TREENODE,*TREENODEPTR;int Insert(TREENODEPTR * root,int x) /返回值表明树是否长高 int taller; if(*root=NULL) *root=(TREENODEPTR)malloc(sizeof(TREENODE); (*root)data=x; (*root)balance=0; return 1; 6 .向向AVL树树 插入
29、结点插入结点else if(x(*root)data) taller=Insert(&(*root)rchild,x); if(taller=1) /右子树长高了 switch(*root)balance) case 0:(*root)balance=1;break; case -1:(*root)balance=0;taller=0;break; case 1: /应该左旋或者先右后左双旋 if(*root)rchildbalance=1) /应该左旋，并调整平衡因子 LeftRotate(root);(*root)balance=0; (*root)lchildbalance=0; els
30、e if(*root)rchildbalance=-1) /应该双旋，并调整平衡因子 if(*root)rchildlchildbalance=1) (*root)balance=-1; (*root)rchildbalance=0; else (*root)balance=0; (*root)rchildbalance=1; (*root)rchildlchildbalance=0; RightLeftRotate(root); taller=0;break; /平衡了,没长高 /switch return taller; /else if else if(x(*root)data) tal
31、ler=Insert(&(*root)lchild,x); if(taller=1)/左子树长高了 switch(*root) balance) case 0:(*root)balance=-1;break; case 1:(*root)balance=0;taller=0;break; case -1: /应该右旋或者先左后右双旋 if(*root)lchildbalance= -1) /右旋 RightRotate(root);(*root)balance=0; (*root)rchildbalance=0; else if(*root)lchildbalance=1) /双旋 if(*r
32、oot)lchildrchildbalance=1) (*root)balance=0; (*root)lchildbalance=-1; else (*root)balance=1; (*root)lchildbalance=0; (*root)lchildrchildbalance=0; LeftRightRotate(root); taller=0;break; /平衡了，没长高 /switch return taller; return 0;41416.7 树和森林1、树的存储结构、树的存储结构(1) 孩子表示法(2) 孩子双亲表示法(3) 双亲表示法(4) 二叉链表法4242树和森林
33、(contd)(1) 树的孩子表示法和孩子树的孩子表示法和孩子-双亲表示法双亲表示法树结点中存放有孩子结点的指针的线性表以及双亲指针。孩子指针线性表可以是顺序表或者链表。typedef struct CTNode/孩子结点 int child; struct CTNode *next; *ChildPtr;Typedef struct elemtype data; ChildPtr firstchild;/孩子链表头指针CTBox;Typedef struct CTBox nodesN; int n,r; /结点数和根的位置； Ctree;RBCAFHDEGK4343树和森林(contd)(1
34、) 树的孩子表示法和孩子树的孩子表示法和孩子-双亲表示法双亲表示法KHGFERDCBA356001234567891289701234567894A4B4C0D-1R0E2F6G6H6K35 012 6 789 (a) 孩子链表(b) 带双亲的孩子链表4444树和森林(contd)(2) 树的双亲表示法树的双亲表示法树结点数据存放到一个静态链表中，每个结点都保存有双亲结点的下标。#define N 100typedef struct PTNode elemtype data; int parent;/ 双亲位置域PTNode;typedef struct PTNode nodesN; int
35、n; /结点数Ptree;R-1A0B0C0D1E1F3G6H6K60123456789数组下标RBCAFHDEGKdataparent以上存储结构大多情况下都使用静态链表存放结点4545树和森林(contd)(3) 树的二叉链表树的二叉链表(孩子兄弟孩子兄弟)表示法表示法与二叉树链式存储结构相同，只不过含义不同：左指针指向第一个孩子，右指针指向下一个兄弟typedef struct CSNode int data; struct CSNode *firstchild; struct CSNode *nextsibling;CSNode,*CSTree; R A D B E C F G H K
36、二叉链表表示法4646树和森林(contd)2、树和二叉树的转换规则、树和二叉树的转换规则将树按照层序遍历，对于兄弟结点，第一个兄弟结点作为双亲的左子树，其他兄弟结点作为前面兄弟结点的右子树。3、森林和二叉树的转换规则、森林和二叉树的转换规则首先将森林的每棵树都转化为二叉树然后将每棵二叉树的根看作是兄弟，根结点作为前面兄弟结点的右子树。由二叉树向树和森林转化是上述过程的逆过程4747树和森林(contd)4、树和森林的遍历、树和森林的遍历(1) 树的层序遍历，从根开始，自上而下自左向右遍树的层序遍历，从根开始，自上而下自左向右遍历每个结点。历每个结点。(2) 树的前序遍历，先访问根，然后自左向
37、右依次前序树的前序遍历，先访问根，然后自左向右依次前序遍历每棵子树。遍历每棵子树。(3) 树的后序遍历，首先后序遍历每棵子树，最后访问树的后序遍历，首先后序遍历每棵子树，最后访问根根森林的遍历就是依次遍历每棵树的过程48486.8 哈夫曼树及其应用1、基本概念、基本概念哈夫曼树哈夫曼树：最优树最优树，分为二叉哈夫曼树和多叉哈夫曼树。哈夫曼树是指树的带权路径长度最小的树。路径长度路径长度：结点间路径上经过的分枝数目树的路径长度树的路径长度：从根到其他结点路径长度总和结点带权路径长度结点带权路径长度：结点的路径长度乘以结点的权值设n个结点的二叉树，结点权值是W1,W2,.,Wn，每个结点的路径长度
38、是Li(i=1,2,n)，那么这棵二叉树的带权路径长度是：当WPL值最小时，就是最优二叉树最优二叉树，也就是二叉哈夫曼树二叉哈夫曼树。4949哈夫曼树及其应用(contd)2、哈夫曼树的应用实例：、哈夫曼树的应用实例：假设我们需要通过网络传送字符串“ABACCDA”，就需要对ABCD四个字符进行编码，当然不能用ASCII码，那需要7个字节56位数据。因为只有4个值需要传送，因此只需要2位数据就可以了，比如将ABCD分别表示为00、01、10、11，这样只需要14位数据。但如果将ABCD作为结点构建一棵下面的二叉树，将ABCD结点路径上的0、1序列作为ABCD的编码：我们只需要9位数据便可以了。
39、根据定义，上面这棵二叉树如果是哈夫曼树，整个编码长度将是最短的。DABC0001115050哈夫曼树及其应用(contd)3、哈夫曼树的建立算法、哈夫曼树的建立算法算法思想算法思想：1）根据给定的权值w1,w2,wn构造n个二叉树F=T1,T2,Tn每个Ti只有一个根结点，权为wi。2）在F中选取两棵根结点的权值最小的树构成一棵新的二叉树，其根的权值为左 右子树根的权值的和。3）F中删去这两棵树，加上新得的树。4）重复2）3）直到只剩一棵树。 5151哈夫曼树及其应用(contd)3、哈夫曼树的建立算法、哈夫曼树的建立算法5364ABCDC756ABDCDBA117CDBA185252#def
40、ine N 20 /叶子结点编码的最大长度typedef struct char ch; int weight; int lchild,rchild,parent;HTNODE; /哈夫曼树结点类型typedef struct char *code; char leaf; CODE; /叶编码类型void hufcoding(HTNODE huftree, CODE cd, int w,int n) /*哈夫曼树存放在静态链表huftree中,w存放结点权重， 按升序排列,n是叶子个数 */ int i,j,k,s1,s2,s,m,f,c,sum; char tempN; /存放叶子编码字符串
41、 m=2*n-1; /计算哈夫曼树的结点总数 for(i=1;i=n;i+) /初始化静态链表，每个结点自成一棵树 huftreei.weight=wi-1; huftreei.lchild=huftreei.rchild=huftreei.parent=0; huftreei.ch=getch(); /for哈夫曼树及其应用(contd)4、哈夫曼树的建立、哈夫曼树的建立(及编码及编码)算法算法for(;i=m;i+) huftreei.weight=0; huftreei.lchild=huftreei.rchild=huftreei.parent=0; k=0; for(i=n+1;i=
42、s2+1&sumhuftreej.weight) /将新生成的结点按照权重有序插入静态链表 huftreej+1=huftreej; j-; huftreej+1.weight=sum; huftrees1.parent=huftrees2.parent=j+1; huftreej+1.lchild=s1; huftreej+1.rchild=s2; /for s=0; /开始求每个叶子结点的编码 for(i=1;i=0) cds.codec=tempc-; cds.leaf=huftreej.ch; s+; if(s=n)break; /找到了所有的叶子结点了，结束 /if /for5353数据结构第六章 树和二叉树作业：1、p233 一、复习 做书上2、P234二、应用 4. 5. 6.做在作业本上 3、周四上机内容：串（简单文本编辑器的制作，具体实习内容见周四的上机要求）5454
