第六章 二叉树的应用(jian )

第六章二叉树的应用§6.1二叉搜索树(二叉排序树)定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值二叉排序树的运算概述二叉排序树的运算同一般二叉树,但由于它具有特殊性,它还经常需要有搜索、更新、插入和删除元素等运算。若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值它的左、右子树也分别为二叉排序树二叉排序树查找查找过程：若二叉排序树为空，则表明查找失败；否则，若x等于当前树根结点的值，则表明查找成功，应返回该结点值域的地址;若x小于根结点的值，则继续在根的左子树中查找;若x大于根结点的值，则继续在根的右子树中查找。显然这是一个递归查找过程。算法描述。ElemType*Find(structBTreeNode*BST,ElemTypex){if(BST==NULL)returnNULL;else{if(x==BST-data)return&(BST-data);elseif(xBST-data)returnFind(BST-left,x);elsereturnFind(BST-right,x);}}此算法属于末尾递归的调用，因此原先保存在数据堆栈中的信息都是没有用处的，为节省空间，可编写相应的非递归算法：ElemType*Find1(structBTreeNode*BST,ElemTypex){while(BST!=NULL){if(x==BST-data)return&(BST-data);elseif(xBST-data)BST=BST-left;elseBST=BST-right;}returnNULL;}二叉排序树插入插入原则：若二叉排序树为空，则插入结点应为新的根结点；否则，若x小于根结点,则将新结点插入到根的左子树上,若x大于等于(若不允许具有相同值的结点存在,则对等于情况应作单独处理)根结点,则将新结点插入到根的右子树上,显然插入过程是递归的,对应的递归算法描述:算法描述voidInsert(structBTreeNode**BST,ElemTypex){if(*BST==NULL){structBTreeNode*p=malloc(sizeof(structBTreeNode));p-data=x;p-left=p-right=NULL;*BST=p;}elseif(x(*BST)-data)Insert(&((*BST)-left),x);elseInsert(&((*BST)-right),x);}例{10，18，3，8，12，2，7，3}1010181018310183810183812101838122101838122710183812273中序遍历二叉排序树可得到一个关键字的有序序列二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树§6.2堆(Heap)定义分为小根堆和大根堆两种，对于一个小根堆，它是具有如下特性的一棵完全二叉树。(1)若树根结点存在左孩子，则根结点的值(或某个域的值)小于等于左孩子结点的值(或某个域的值)；(2)若树根结点存在右孩子，则根结点的值(或某个域的值)小于等于右孩子结点的值(或某个域的值)；(3)以左、右孩子为根的子树又各是一个堆。大根堆的定义与上述类似，只要把小于等于改为大于等于就可以了。图6-4小根堆和大根堆堆的存储结构堆是一棵完全二叉树,所以适宜采用顺序存储结构，这样能够充分利用存储空间。让堆中的结点从0开始编号后：编号为0至[n/2]-1的结点为分支结点，编号为[n/2]至n-1的结点为叶子结点；当n为奇数则每个分支结点既有左孩子又有右孩子，当n为偶数则每个分支结点只有左孩子没有右孩子；对于每个编号为i的分支结点，其左孩子结点的编号为2i+1,右孩子结点的编号为2i+2；除编号为0的堆顶结点外，对于其余编号为i的结点，其双亲结点的编号为[(i-1)/2]堆的顺序存储结构18263573486074534225363529182201234567890123456789structHeapSq{ElemType*heap;intlen;intMaxSize;};堆的运算—向堆中插入一个元素基本思想:将新元素写入到堆尾，即堆中最后一个元素的后面，即下标为len的位置上，调整为一个新堆。调整方法：若新元素小于双亲结点的值，就让它们互换位置，使得以该位置为根的子树成为堆；新元素可能还小于此位置的双亲结点的值，从而使以上一层的双亲结点为根的子树不为堆，还需要按上述方法继续调整；持续传递上去直到以新位置的双亲结点为根的子树仍为一个堆或者调整到堆顶为止，此时得到的整个树又成为了一个堆。351826607348012345678918263573486018263560157348插入15调整2调整118261560357348152618603573481515351518算法描述：voidInsertHeap(structHeapSq*HBT,ElemTypex){inti;if(HBT-len==HBT-MaxSize){ElemType*p;p=realloc(HBT-heap,2*HBT-MaxSize*sizeof(ElemType));if(!p){printf(neichunisusedup!\n);exit(1);}HBT-heap=p;HBT-MaxSize=2*HBT-MaxSize;}HBT-heap[HBT-len]=x;HBT-len++;i=HBT-len-1;while(i!=0){intj=(i-1)/2;if(x=HBT-heap[j])break;HBT-heap[i]=HBT-heap[j];i=j;}HBT-heap[i]=x;}从堆中删除一个元素基本思想:从堆中删除元素就是删除堆顶元素并使之返回；堆顶元素被删除后，留下的堆顶位置应由堆尾元素来填补；调整为一个新堆。调整过程若根结点的值大于两个孩子结点中的最小值，就将它与具有最小值的孩子结点互换位置；依此逐渐调整各子堆。351826607348删除18调整2调整1356026734835266073483526487360§6.3哈夫曼树(Huffman)——带权路径长度最短的树定义路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的~路径长度：路径上的分支数结点的权:在实际中，常将树中的结点赋予一个有着某种意义的实数，称此实数为该结点的权。结点的带权路径长度：从树根结点到该结点之间的路径长度与该结点上权的乘积。树的带权路径长度：树中所有叶子（带权）结点的路径长度之和—结点到根的路径长度——权值—其中：记作：kknkkklwlwwpl1Huffman树——设有n个权值{w1,w2,……wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫~例有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35nkKKLWWPL1构造Huffman树的方法——Huffman算法构造Huffman树步骤根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令其权值为wj在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和在森林中删除这两棵树，同时将新得到的二叉树加入森林中重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100Huffman树的应用——Huffman编码电报通信中，电文以二进制编码传送，编码方式：等长编码——简单，但会占用较多存储空间，不利于快速通信。不等长编码——根据字符出现频率的高低给出不同长度的编码，有利于提高通信效率，但注意编码应是无前缀编码，否则会造成译码出错。实现符合上述条件的不等长编码可采用Huffman。Huffman编码：以字符出现的频率为权值，构造Huffman树定义Huffman的左分支为0，右分支为1，将从根到叶子（字符）结点的分支码排列即成为该字符的编码。习题6.1