数据结构教案第八章.

案例分析： 复习思考题 对于一个学生信息表，我们 可以查找学生的姓名，年龄，作 业 成绩等等。我们可以用上面介绍的折半查找和分块查找方法。 上机任务 参考文献 本次课程就介绍这里结束，总结本次的内容；课后学生要好好把课后记 这次上的内容好好复习一下，然后预习下一次的内容，下一次我（或归纳小们介绍以上所述关系的具体描述 结）

安徽新华电脑专修学院课堂教学教案

（电脑应用课使用）

课程名称 教 材 授课内容 数据结构 教学对象 数据结构（C语言） 新华软工专业 第八章 查找 课 时 2 教学目的 本节主要介绍了二叉排序树和平衡二叉树 与要求 重点： 二叉排序树 重点、难点 难点：平衡二叉树 课 型 教学过程 设计 （包括讲授知识、演示内容及案例、提问及学生演示内容） 电脑＋理论 教学方法 投影、讨论、版书 复习上一次的内容： 4、折半查找： 5、分块查找： 6、折半查找的思想和算法：要求学生回答 （接上一次课的序号） 任务三：树表的查找 二叉排序树查找 1．什么是二叉排序树 二叉排序树（Binary Sorting Tree），它或者是一棵空树，或者是一棵具有如下特征的非空二叉树： (1)若它的左子树非空，则左子树上所有结点的关键字均小于根结点的关键字； (2)若它的右子树非空，则右子树上所有结点的关键字均大于等于根结点的关键字； (3)左、右子树本身又都是一棵二叉排序树。 教 学 过 程 设 计 (续表) 2．二叉排序树的数据类型描述 和第六章类似，可以用一个二叉链表来描述一棵二叉排序树，具体为： struct node { int key; //代表关键字 … struct node *lch,*rch; //代表左、右孩子 }; 4．二叉排序 树上的查找 （1）二叉排序 树的查找思想 若二叉排树为空，则查找 失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成功。 （2）二叉排序树查找的算法实现 NODE * search(int k, NODE *root) //在以root为根指针的二叉排序树中查找关键值为x的结点 {NODE *p; p=root; while(p!= =NULL) { if (p->key= =k) return(p); //查找成功 else if (p->key>k) p=p->lch ; //进入左子树查找 else p=p->rch ; //进入右子树查找 } return(NULL); } 5．二叉排序树查找的性能分析 在二叉排序树查找中，成功的查找次数不会超过二叉树的深度，而具有n个结点的二叉排序树的深度，最好为log2n，最坏为n。因此，二叉排序树查找的最好时间复杂度为O(log2n)，最坏的时间复杂度为O(n)，一般情形下，其时间复杂度大致可看成O(log2n)，比顺序查找效率要好，但比二分查找要差。 任务四：平衡二叉树查找 1．平衡二叉树的概念 平衡二叉树(balanced binary tree)是由阿德尔森一维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。 若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二叉树为平衡二叉树。将该结点的左子树深度减去右子树深度的值，称为该结点的平衡因子(balance factor)。也就是说，一棵二叉排序树中，所有结点的平衡因子只能为0、1、-1时，则该二叉排序树就是一棵平衡二叉树，否则就不是一棵平衡二叉树。如图8-8所示二叉排序树，是一棵平衡二叉树，而如图8-9所示二叉 排序树，就不是一棵平衡二叉树。 教 学 过 程 设 计 (续表) 4 5 3 2 6 8 12 3 7 5 4 1 7 图8-8 一棵平衡二叉树 6 图8-9 一棵非平衡二叉树 2.非平衡二叉树的平衡处理 若一棵二叉排序树是平衡二叉树，插入某个结点后，可能会变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成一棵平衡二叉树。处理的原则应该是处理与插入点最近的、而平衡因子又比1大或比-1小的结点。下面将分四种情况讨论平衡处理。 （1）LL型 的处理(左左型) 如图8-10所示，在A的左孩子B上插入一个左孩子结点C，使A的平衡因子由1变成了2，成为不平衡的二叉树序树。这时的平衡处理为：将A顺时针旋转，成为B的右子树，而原来B的右子树则变成A的左子树，待插入结点C作为B的左子树。(注：图中结点旁边的数字表示该 结点的平衡因子) 2 A 0 B 1 B 平衡外理 0 C 0 C 0 A 图 8-10 LL 型平衡外理 （2）LR型的处理(左右型) 如图8-11所示，在A的左孩子B上插入一个右孩子C，使的A的平衡因子由1变成了2，成为不平衡的二叉排序树。这是的平衡处理为：将C变到 B与A 之间，使之成为LL型，然后按第(1)种情形LL型处理。 2 A 2 A 0 C 旋转 平衡处理 -1 B 1 C 0 B 0 A 0 C 0 B 图 8-11 LR 型平衡处理 （3）RR型的处理(右右型) 如图8-12所示，在A的右孩子B上插入一个右孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将A逆时针旋转，成为B的左子树，而原来B的左子树则变成A的右子树，待插入结点。