DS06数据结构树-二叉排序树.pptVIP

* * * 平衡二叉排序树(Balanced Binary Tree或Height-Balanced Tree)是在1962年由俄罗斯数学家Adelson-Velskii和Landis提出的，又称AVL树。 回顾：二分查找 ? 当线性表中数据元素是按大小顺序排列存放时，可以采用二分法 (折半查找)。 二分查找是每次在要查找的数据集合中取出中间元素关键字Kmid与要查找的关键字K进行比较，根据比较结果确定是否要进一步查找。 当 Kmid=K ，查找成功； 当 K Kmid ，将在Kmid的左半部分继续下一步查找 当 K Kmid，将在Kmid右半部分继续下一步查找 以此类推，每步的查找范围都将是上一次的一半。 优点：查找效率高 缺点：要求线性表有序，如果是进行动态查找，即需要对线性表进行插入、删除或排序操作，就必须移动大量的记录，当记录数很多时，这种移动的代价很大。 第4章 树 §4.4二叉有哪些信誉好的足球投注网站树 6 3 1 4 7 9 5 10 2 11 8 11个元素的判定树 第4章 树 判定树的特点： 左子树的值都比根结点小 右子树的值都比根结点大 中序遍历判定树得到的是一组有序的序列 ? 11个元素的二分查找判定树 §4.4二叉有哪些信誉好的足球投注网站树 能否根据以上特点，利用树型结构来动态创建查找表呢？ 第4章 树 §4.4二叉有哪些信誉好的足球投注网站树 【定义】一个二叉有哪些信誉好的足球投注网站树是一棵二叉树，它可以为空。如果不为空，它将满足以下性质： 非空左子树的所有键值小于其根结点的键值。 非空右子树的所有键值大于其根结点的键值。 左、右子树都是二叉有哪些信誉好的足球投注网站树。 ?二叉有哪些信誉好的足球投注网站树 “二叉有哪些信誉好的足球投注网站树（BST，Binary Search Tree）”也称二叉排序树或二叉查找树，它是一种对排序和查找都很有用的特殊二叉树。 18 10 5 20 7 22 30 15 41 33 50 6 3 1 4 7 9 5 10 2 11 8 11个元素二分查找的判定树 ? 二叉有哪些信誉好的足球投注网站树的动态查找 ? 二叉有哪些信誉好的足球投注网站树作为抽象数据结构的定义与普通二叉树相同，但操作集中多了下列几个特别的函数： ? Position Find( ElementType X, BinTree BST )：从二叉有哪些信誉好的足球投注网站树BST中查找元素X，返回其所在结点的地址； ? Position FindMin( BinTree BST )：从二叉有哪些信誉好的足球投注网站树BST中查找并返回最小元素所在结点的地址； ? Position FindMax( BinTree BST ) ：从二叉有哪些信誉好的足球投注网站树BST中查找并返回最大元素所在结点的地址。 第4章 树 §4.4二叉有哪些信誉好的足球投注网站树 ? BinTree Insert( ElementType X, BinTree BST ) ? BinTree Delete( ElementType X, BinTree BST ) typedef Position BinTree ? 二叉有哪些信誉好的足球投注网站树的查找操作Find 第4章 树 §4.4二叉有哪些信誉好的足球投注网站树 查找从根结点开始，如果树为空，返回NULL，表示未找到关键字为X的结点。 若有哪些信誉好的足球投注网站树非空，则根结点关键字和X进行比较，依据比较结果，需要进行不同的处理： ? 若根结点键值小于X，满足条件的结点将不会出现在它的左子树，接下来的有哪些信誉好的足球投注网站只需在右子树中进行； ? 如果根结点的键值大于X，接下来的有哪些信誉好的足球投注网站将在左子树中进行； ? 若两者比较结果是相等，有哪些信誉好的足球投注网站完成，返回指向此结点的指针。 ? 二叉有哪些信誉好的足球投注网站树的查找操作Find 第4章 树 §4.4二叉有哪些信誉好的足球投注网站树 Position Find( ElementType X, BinTree BST ) { if( !BST ) return NULL; //查找失败 if( X BST-Data ) return Find( X, BST-Right ); //在右子树中继续查找 else if( X BST-Data ) return Find( X, BST-Left ); //在左子树中继续查找 else //X == BST-Data return BST; //查找成功，返回找到结点的地址 } Position IterFind( ElementType X, BinTree BST ) { while( BST ) { if( X BST-Data ) BST = BST-Right; //向右子树中移动，继续查找 else if( X BST-Data ) BST = BST-Left; //向左子树中移动，继续查找 else // X == BST-Data return BST; //查找成功