二叉搜索树（查找，插入，删除）

喜欢ヅ旅行 2023-07-03 02:47 14阅读 0赞

一.  
二叉搜索树也称为二叉排序树或二叉查找树，简称为BST。  
其可以为空，也可以不为空，但满足以下的条件。  
1 非空左子树的所有键值小于其根节点的键值。  
2 非空右子树的所有键值大于其根节点的键值。  
3 左右子树都是二叉搜索树。

二.  
二叉搜索树的特殊操作函数：  
position find(elementtype x,bintree BST)从二叉树中寻找元素x，并返回元素的地址。  
position findmin（bintree BST）从二叉树中找到最小的元素所在节点的地址。  
position findmax（bintree BST）从二叉树中找到最大的元素所在的地址。

三.二叉树的搜索操作过程：

从根节点开始，若为空，则返回NULL，
    若不为空，则比较要寻找的值与当前节点，若比当前节点小，则继续递归判断左子树，若比当前节点大，则继续递归判断右子树，相等则return此节点的指针。

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
            return BST;     //查找成功，返回节点地址。
    }

向上述这种递归语句都在程序运行的结尾处，叫做尾递归，都可以改成非递归的循环写法。

Position Find(elementtype X,BinTree BST)
    {
        
        while(BST)
        {
        
            if(X>BST->Data)
            {
        
                BST=BST->Right;
            }
            else if(X<BST->Data)
            {
        
                BST=BST->Left;
            }
            else break;
        }
        return BST;
    }

这种查找方法的效率取决于树的高度。

四.查找树中最大和最小的元素

原理：  
1 最大的元素一定在树的最右端点上。  
2 最小的元素一定在树的最左端点上。  
二者均可使用递归或者迭代。

Position Findmin(BinTree BST)
    {
        
        if(BST=NULL) return NULL;
        else if(!BST->Left)
        {
        
            return BST;
        }
        else 
            return Findmin(BST->Left);    //用了递归找最小值。
    }

Position Findmax(BinTree BST)
    {
        
        while(BST->Right)
        {
        
            BST=BST->Right;
        }
        return BST;              //用迭代法找最大值
    }

三.二叉搜索树的插入

分成原树为空，和原来的树非空两种情况，若原树为空，则生成一个只有一个节点，即插入的元素的树；  
若原树非空，则从根节点出发，比较大小，若比当前节点小，则继续递归插入左子树。

BinTree Insert(ElementType X,BinTree BTS)
    {
        
        if(BTS==NULL)
        {
        
            malloc(sizeof(struct Treenode));     //申请一个空间
            BST->Data=X;                         //将数据存入
            BST->Right=BST->Left=NULL;           //将左右指针指向空
        }
        else
        {
        if(X>BTS->left)
        {
        
            BST->left=Insert(X,BTS->left);       //继续插入左子树
        }
        else if(X<BTS->Right)
            BST->right=Insert(X,BTS->Right);       //继续插入右子树
        }
        return BST;
    }

四.二叉搜索树的删除

删除要考虑三种情况  
1 .删除的是叶节点，直接将元素删除，并将其父的指针指向NULL。  
2 .要删除的节点只有一个儿子的时候，将要删除的节点的父的指针指向要删除节点的孩子。  
3. 若要删除的元素有左右两颗子树，应用另一节点替代被删除的节点，可以是左子树中的最大元素，也可以是右子树中的最小元素。

BinTree delete(ElementType X,BinTree BTS)
    {
        
        if(!BTS) printf("要删除的元素未找到");
        else if(X>BTS->Data)
            BTS->right=delete(X,BTS->right);             //继续在其右子树中删除
        else if(X<BTS->Data)
            BTS->left=delete(X,BTS->left);           //继续在其左子树中删除
        else
        {
        
            if(BTS->left&&BTS->right)                             //左右节点都存在的情况
            {
        
                BinTree tmp=Findmin(BTS->right);                          //找到右子树中的最小元素
                BTS->data=tmp->data;                                    
                BTS->right=delete(tmp->Data,BTS->right);       //在从右子树中删掉该最小元素
            }
            else
            {
        
                BinTree tmp=BTS;
                if(!BTS->left)
                  BTS=BTS->right;            //将指针指向其右子树，从而达到删除的目的。若左右都为空，则BTS=NULL，达到删除的目的。
                else if(!BTS->right)
                  BTS=BTS->left;
                free(tmp);       
            }
        }
        return BTS;
    }