会计学双亲(shuāngqīn)表示法举例6.4.1树的存储结构(jiégòu)二、孩子表示法（顺序存储）孩子(háizi)表示法举例孩子链表存储(cúnchǔ)表示（链式存储(cúnchǔ)）孩子(háizi)链表存储表示举例例1:设树T以孩子(háizi)链表为存储结构,寻找值为x的双亲结点的算法如下:例2:删除值为x的结点的第i棵子树的算法(suànfǎ)delete如下：Statusdelete(Ctree&T,TElemTypex,inti){//当值为x的结点不存在时返回-2;当值为x的结点为//叶结点或无第i棵子树时返回-1,否则返回1.for(k=0;k<T.n;k++)if(T.nodes[k].data==x)break;//找到值为x的结点if(k>=T.n)return–2;//值为x的结点不存在p=T.nodes[k].firstchild;j=1;if(!p)return–1;//x结点为叶结点if(i==1){//删除长子时,特殊处理j=p->child;//记住要删除子树的下标T.nodes[k].firstchild=p->next;free(p);}else{while(p->next&&j<i-1){p=p->next;j++;}if(j>i-1||!p->next)return–1;//无第i棵子树//p指向(zhǐxiànɡ)第i-1个儿子j=p->next->child;//记住要删除子树的下标s=p->next;p->next=s->next;free(s);}deletej(T,j);//递归删除第j号结点及其子树return1;}三.孩子(háizi)兄弟表示法---树的二叉树表示法(二叉链表示法)6.4.2森林(sēnlín)与二叉树的转换一.森林(sēnlín)转换成二叉树二.二叉树转换成森林(sēnlín)6.4.3树和森林(sēnlín)的遍历森林的两种遍历(biànlì)方法：6.6赫夫曼树及其应用(yìngyòng)6.6.1最优二叉树(赫夫曼树)最优二叉树或赫夫曼(Huffman)树的定义(dìngyì)例1：下面(xiàmian)三棵二叉树的四个叶子结点a,b,c,d的权值为7、5、2、4例2最佳(zuìjiā)判定方法(p.144)(a)WPL=10x4+30x4+40x3+15x2+5x1=315(b)WPL=5x3+15x3+40x2+30x2+10x2=220构造赫夫曼树的算法(suànfǎ)思想构造(gòuzào)赫夫曼树举例6.6.2赫夫曼编码赫夫曼树中没有度为1的结点(jiédiǎn)---严格的二叉树求赫夫曼编码的算法(suànfǎ)如下:求赫夫曼编码(biānmǎ)的算法（续一）:求赫夫曼编码(biānmǎ)的算法（续二）:求赫夫曼编码(biānmǎ)的算法如下:无栈非递归遍历(biànlì)赫夫曼树,求赫夫曼编码例6-2八种字符,其频率(pínlǜ)分别为:0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.116.8树的计数(jìshù)例6-5已知结点(jiédiǎn)的前序序列和中序序列，求整棵二叉树。实验(shíyàn)与习题