BST二叉搜索树

BST的查找算法

//递归查找 struct node *Find(ElementType key,struct node *BST){ if(!BST) return NULL;//查找失败 if(key > BST->data){ return Find(key,BST->right); }else if(key < BST->data){ return Find(key,BST->left); }else{//key == BST->data return BST;//返回查找成功的结点的地址 } }

由于非递归函数的执行效率高，一般采用非递归的迭代方式来实现查找。

//迭代查找 struct node *IterFind(ElementType key,struct node *BST){ while(BST){ if(key > BST->data){ BST = BST->right; }else if(key < BST->data){ BST = BST->left; }else{//key == BST->data return BST;//返回查找成功的结点的地址 } } return NULL;//查找失败 }

查找最小元素

根据二叉搜索树的性质，最小元素一定在二叉树的最左分支的叶子结点上。同理，最大元素一定在二叉树的最右分支的叶子节点上。

//递归查找最小元素 struct node *FindMin(struct node *BST){ if(!BST) return NULL;//空的二叉树返回NULL if(!BST->left) return BST;//找到最左边结点 else return FindMin(BST->left);//沿着左分支继续查找 } //迭代查找最小元素 struct node *IterFindMin(struct node *BST){ if(BST){ while(BST->left){ BST = BST->left;//沿着左分支继续查找 } } return BST; }

BST的插入

//插入 struct node *Insert(ElementType key,struct node *BST){ //若原二叉树为空，则生成并返回一个结点的二叉搜索树 if(!BST){ BST = (struct node *)malloc(sizeof(struct node)); BST->data = key; BST->left = BST->right = NULL; }else if(key < BST->data){ BST->left = Insert(key,BST->left);//递归插入左子树 }else if(key > BST->data){ BST->right = Insert(key,BST->right);//递归插入右子树 } return BST; }

BST的删除

BST的删除分为三种情况： 1.待删除的结点是叶子结点： 直接删除，将指向该结点的指针置空即可 2.待删除的结点只有一个分支： 修改该结点的指针，将其指向为其孩子的结点。即上移子树。 3.待删除结点有左右两个分支： 这时有两种情况可以选择：用删除节点的直接前驱或者直接后继来替换当前结点，再递归删除直接前驱或者直接后继的结点位置。 （可能，十分绕口） 简而言之：一种就是选择其左子树的最大元素，另一种就是选择右子树的最小元素。 （注：用中序遍历一下上图的二叉树，你就知道为什么叫前驱元素和后继元素了。）

//删除 struct node *Delete(ElementType key,struct node *BST){ struct node *temp = NULL; if(!BST){ printf("要删除的元素未找到"); }else if(key < BST->data){ BST->left = Delete(key,BST->left); }else if(key > BST->data){ BST->right = Delete(key,BST->right);//找到要删除的结点 }else if(BST->left && BST->right){//被删除的结点有左右两个子结点 temp = FindMin(BST->right);//在右子树中找到最小的元素填充删除的结点 BST->data = temp->data; BST->right = Delete(BST->data,BST->right); }else if(BST->left){//被删除的结点只有左分支 BST = BST->left; }else if(BST->right){//被删除的结点只有右分支 BST = BST->right; }else{//被删除的结点无左右分支 BST = NULL; } return BST; }

缺陷

最好的情况是二叉排序树的形态和二分查找的判定树相同，其平均查找长度和log 2 (n)成正比。 最坏情况下，当先后插入的关键字有序时，构成的二叉排序树退化为单支树，树的深度为其平均查找长度(n+1)/2(和顺序查找相同）

优化

为了避免二叉搜索树退化为单支树的情况，可以自平衡成为AVL树或红黑树，使查找树的高度为O(logn)