数据结构(C描述)电子教案第8章.ppt

（2）二叉排序树的建立 只要反复调用二叉排序树的扦入算法即可，算法描述为： Btreenode *Creat (int n) //建立含有n个结点的二叉排序树 { Btreenode *BST= NULL; for ( int i=1; i=n; i++) { cinx; //输入关键字序列 Insert ( BST,x); } return BST ;} 例如，结定关键字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序树过程如图8-6所示。（注：二叉排序树与关键字排列顺序有关，排列顺序不一样，得到的二叉排序树也不一样） 4．二叉排序 树上的查找 （1）二叉排序 树的查找思想 若二叉排树为空，则查找 失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成功。 （2）二叉排序树查找的算法实现 Btreenode * find( Btreenode *BST,elentype x) //在以BST为根指针的二叉排队 树中查找值为x的结点 { if ( BST= =NULL) return NULL; //查找失败 else { if (BST-data= =x) //查找成功 return BST; else if (BST-datax) //进入左子树查找 return find ( BST-left,x); else //进入右子树查找 return find (BST-right,x);} } 5．二叉排序树查找的性能分析 在二叉排序树查找中，成功的查找次数不会超过二叉树的深度，而具有n个结点的二叉排序树的深度，最好为log2n，最坏为n。因此，二叉排序树查找的最好时间复杂度为O(log2n)，最坏的时间复杂度为O(n)，一般情形下，其时间复杂度大致可看成O(log2n)，比顺序查找效率要好，但比二分查找要差。 8.3.2平衡二叉树查找 1．平衡二叉树的概念 平衡二叉树(balanced binary tree)是由阿德尔森一维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。 若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二叉树为平衡二叉树。将该结点的左子树深度减去右子树深度的值，称为该结点的平衡因子(balance factor)。也就是说，一棵二叉排序树中，所有结点的平衡因子只能为0、1、-1时，则该二叉排序树就是一棵平衡二叉树，否则就不是一棵平衡二叉树。如图8-8所示二叉排序树，是一棵平衡二叉树，而如图8-9所示二叉 排序树，就不是一棵平衡二叉树。 2.非平衡二叉树的平衡处理 若一棵二叉排序树是平衡二叉树，扦入某个结点后，可能会变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成一棵平衡二叉树。处理的原则应该是处理与扦入点最近的、而平衡因子又比1大或比-1小的结点。下面将分四种情况讨论平衡处理。 （1）LL型 的处理(左左型) 如图8-10所示，在C的左孩子B上扦入一个左孩子结点A，使C的平衡因子由1变成了2，成为不平衡的二叉树序树。这时的平衡处理为：将C顺时针旋转，成为B的右子树，而原来B的右子树则变成C的左子树，待扦入结点A作为B的左子树。(注：图中结点旁边的数字表示该 结点的平衡因子) （2）LR型的处理(左右型) 如图8-11所示，在C的左孩子A上扦入一个右孩子B，使的C的平衡因子由1变成了2，成为不平衡的二叉排序树。这是的平衡处理为：将B变到A与C 之间，使之成为LL型，然后按第(1)种情形LL型处理。 （3）RR型的处理(右右型) 如图8-12所示，在A的右孩子B上扦入一个右孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将A逆时针旋转，成为B的左