第6章 树和二叉树的应用(已修改).ppt

6 二叉树应用 6.1二叉排序树和平衡二叉树 6.2 堆和堆排序 6.3 赫(哈)夫曼树及其应用 6.4 B-树和B+树 同学录管理系统 6.1二叉排序树和平衡二叉树 二叉排序树 平衡二叉排序树(AVL树) 平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树： （1）它的左子树和右子树都是平衡二叉树； （2）左子树和右子树高度之差的绝对值不超过1。 不平衡而察排序树只能由如下的4种情况： 6.2 堆和堆排序 堆是每个非终端结点的关键字均不大（小）于它的孩子结点的关键字的完全二叉树。 可以描述为：把n个元素的序列k1，k2，…，kn，存储到一棵完全二叉树中，且使所有非叶结点的值均不大于(或不小于)其子女的值，根结点的值是最小(或最大)的。 设有n个元素，将其按关键码排序。首先将这n个元素按关键码建成堆，将堆顶元素输出，得到n个元素中关键码最小(或最大)的元素。然后，再对剩下的n-1个元素建成堆，输出堆顶元素，得到n个元素中关键码次小(或次大)的元素。如此反复，便得到一个按关键码有序的序列。称这个过程为堆排序。 堆排序的基本思想： （1）首先把待排序的顺序表(R1，R2，…，Rn)依次填入一棵有n个结点的完全二叉树，并将它转换成一个堆。 （2）这时，根结点具有最大（小）值。把根结点与最后一个结点对调，删去最后一个结点，输出；然后将剩下的结点重新调整为一个堆。 反复进行（2），直到只剩下一个结点为止。 一、 Huffman树（最优二叉树） 如何构建一棵赫夫曼树？ 按左“0”右“1” 对Huffman树的所有分支编号 如何编程实现Huffman编码？ Huffman编码举例 w={ 7, 19, 2, 6, 32, 3, 21, 10 }在机内存储形式为: 小结：赫夫曼树及其应用 本章小结 * * 二叉排序树也称二叉查找树或二叉有哪些信誉好的足球投注网站树。它或者是一棵空树，或者有性质： （1）若其左子树不空，则左子树上所有结点的值均小于根结点的值。 （2）若其右子树不空，则右子树上所有结点的值均大于根结点的值。 （3）左右子树也为二叉排序树。 二叉排序树的基本运算如下： 1.BSTSearch(bt,k)在二叉排序树bt中，查找值为k的结点 2.BSTInsert(bt,k)在二叉排序树bt中，插入值为k的结点 3.CreateBST(bt,str,n)创建二叉排序树 4.输出二叉排序树DispBST(bt) 5.删除结点BSTDelete(bt,k) BSTNode*BSTSearch(BSTNode*bt,KeyType k) { BSTNode*p=bt; while(p!=NULLp-data!=k) {if(kp-data) p=p-lchild;/*沿左子树查找*/ else p=p-rchild;/*沿右子树查找*/ } return（p）; } 1、查找结点BSTSearch(bt,k) 方法：将给定值k与查找树的根结点关键码比较。若相等，查找成功，结束查找过程。否则， a．当给k小于根结点关键码，查找将在以左子女为根的子树上继续进行； b．当给k大于根结点关键码，查找将在以右子女为根的子树上继续进行； c．若K等于当前结点的关键字，则返回；如此反复，直至找到或子树为空，查找失败时为止。 2、二叉排序树的插入 向二叉排序树中插入一个结点的过程：设待插入结点的关键码为kx，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，待插入结点已存在，不用插入；查找不成功时，则插入之。因此，新插入结点一定是作为叶子结点添加上去的。 insertbst(BiTree t, int k) { BiTree p; p=(BiTree)malloc(sizeof(BiNode)); p-data=k; p-lchild=NULL; p-rchild=NULL; if(t==NULL) t=p; else { if(t-data=k) if(t-lchild==NULL) t-lchild=p; else insertbst(t-lchild, k); else if(t-rchild==NULL) t-rchild=p;