二叉搜索树(BST)

港控/mmm° 2022-12-16 09:08 169阅读 0赞

# 二叉搜索树 Binary Search Tree #

> 也称二叉查找树或二叉排序树

## 性质 ##

非空二叉搜索树的**性质**：

*  非空左子树的值都比根节点小（**左小**）
 *  非空右子树的值都比根结点大（**右大**）
 *  每一棵子树都是二叉搜索树

## 操作 ##

*  插入：  
    除了普通的增加元素外，也是通过此操作建立整个二叉排序树
 *  查找：
    
     *  查找目标值
     *  查找最大值
     *  查找最小值
 *  删除：  
    此操作相对其他操作更加复杂。  
    可以分为三种情况：
    
     *  删除的是叶子结点：**直接删除即可**
     *  删除的结点只有一颗子树：**用儿子结点替换需要删除的结点**
     *  删除的结点有左右两颗子树：**用左子树最小或右子树最大替换删除的结点**（这两个点一定不是有两个子树的结点，从而可以转换为前两种情况进行删除）

## 代码 ##

> 参考自浙大数据结构

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    typedef int ElementType;
    /*
    * 二叉搜索树：
    * 左子树元素都比根元素小，
    * 右子树元素都比根节点大，
    * 左右子树都是二叉搜索树
    * 操作：
    * 查找，插入，删除
    */
    typedef struct TreeNode *Position;
    typedef Position BinTree;
    struct TreeNode
    {
        
        ElementType Data;
        TreeNode *Right,*Left;
    };
    
    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 IterFind(ElementType X,BinTree BST)
    {
        
        /*
        * 非递归实现查找
        */
        while(BST)
        {
        
            if(X > BST->Data)
                BST = BST->Right;
            else if(X < BST->Data)
                BST = BST->Left;
            else return BST;
        }
        return NULL;
    }
    
    Position FindMin(BinTree BST)
    {
        
        if(!BST) return NULL;
        while(BST->Left) BST = BST->Left;
        return BST;
    }
    
    Position FindMax(BinTree BST)
    {
        
        if(!BST) return NULL;
        while(BST->Right) BST = BST->Right;
        return BST;
    }
    
    BinTree Insert(ElementType X,BinTree BST)
    {
        
        if(!BST)
        {
        
            BST = (TreeNode*)malloc(sizeof(struct TreeNode));
            BST->Data = X;
            BST->Right = BST->Left = NULL;
        }
        if(X > BST->Data)
        {
        
            BST->Right = Insert(X,BST->Right);
        }
        else if(X < BST->Data)
        {
        
            BST->Left = Insert(X,BST->Left);
        }
        return BST;
    }
    
    BinTree Delete(ElementType X,BinTree BST)
    {
        
        Position temp;
        if(!BST)
        {
        
            printf("找不到需要删除的值\n");
            return NULL;
        }
        else
        {
        
            if(X > BST->Data)
                BST->Right = Delete(X,BST->Right);
            else if(X < BST->Data)
                BST->Left = Delete(X,BST->Left);
            else
            {
        
                /*BST->Data == X*/
                if(BST->Left && BST->Right)
                {
        
                    /*采用找左最大或右最小替换*/
                    temp = FindMax(BST->Left);
                    BST->Data = temp->Data;
                    BST->Left = Delete(temp->Data,BST);
                }
                else
                {
        
                    temp = BST; /*之后要回收的空间*/
                    if(!BST->Left) /*没有左子树*/
                        BST = BST->Right;
                    if(!BST->Right) /*没有右子树*/
                        BST = BST->Left;
                    free(temp);
                }
            }
            return BST;
        }
    
    }
    
    void postorder(BinTree BST)
    {
        
        /* 后序遍历*/
        if(BST)
        {
        
            postorder(BST->Left);
            postorder(BST->Right);
            printf("%d ",BST->Data);
        }
    }
    
    int main()
    {
        
        int data [7] = {
        5,1,3,2,4,6,7};
        BinTree BST = NULL;
        for(int i = 0; i < 7; ++i)
        {
        
            BST = Insert(data[i],BST);
        }
        postorder(BST);
        Delete(1,BST);
        puts("");
        postorder(BST);
        
        return 0;
    }