数据结构MOOC|二叉搜索树BST

柔情只为你懂 2022-05-24 13:22 210阅读 0赞

课程内容来自：[http://www.icourse163.org/learn/ZJU-93001?tid=1002654021\#/learn/content?type=detail&id=1003620986][http_www.icourse163.org_learn_ZJU-93001_tid_1002654021_learn_content_type_detail_id_1003620986]

## 二叉搜索树（BST，Binary Search Tree） ##

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

是一棵二叉树，可以为空；若不为空，则满足以下性质：

1.  非空左子树的所有键值小于其根结点的键值；
2.  非空右子树的所有键值大于其根结点的键值；
3.  左、右子树都是二叉搜索树。

### 【涉及函数】 ###

*  Position Find( ElementType X, BinTree BST)：从BST中查找元素X，返回其所在结点的地址；
 *  Position FindMin( BinTree BST)：从BST中查找并返回最小元素所在结点的地址；
 *  Position FindMax BinTree BST)：从BST中查找并返回最大元素所在结点的地址；
 *  BinTree Insert( ElementType X, BinTree BST )
 *  BinTree Delete( ElementType X, BinTree BST )

#### 查找： ####

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 return BST;
        }
        return NULL;
    }

查找的效率取决于树的高度。

Position FindMax( BinTree BST )
    {
        if( BST )
            while( BST->Right ) BST = BST->Right;
        return BST;
    }

Position FindMin( BinTree BST )
    {
        if( !BST ) return NULL;
        else if( !BST->Left) return BST;
        else return FindMin( BST->Left );
    }

#### 插入： ####

BinTree Insert( ElementType X, BinTree BST)
    {
        if( !BST ){
            BST = malloc(sizeof(struct TreeNode));
            BST->Data = X;
            BST->Left = BST->Right = NULL;
        }else{
            if( X < BST->Data )
                BST->Left = Insert( X, BST->Left);
            else if( X > BST->Data )
                BST->Right = Insert( X, BST->Right);
        }
        return BST;
    }

#### 删除： ####

需要考虑三种情况：

*  删除的结点没有儿子结点->直接删除；
 *  删除的结点有一个儿子结点；
 *  删除的结点有两个儿子结点。

BinTree Delete( ElementType X, BinTree BST)
    {
        Position Tmp;
        if( BST==NULL ) cout<<"要删除的元素未找到"<<endl;
        else if( X < BST->Data )
            BST->Left = Delete( X,BST->Left);
        else if( X > BST->Data )
            BST->Right = Delete( X,BST->Right);
        else{                                         //找到该元素
            if( BST->Left!=NULL && BST->Right!=NULL){ //被删除结点有两个非空子节点
                Tmp = FindMin( BST->Right );          //用右子树的最小结点填充被删除结点
                BST->Data = Tmp->Data;
                BST->Right = Delete( BST->Data, BST->Right);
            }else{                                    //被删除结点有一个或无子结点
                Tmp = BST; 
                if( BST->Left==NULL )
                    BST = BST->Right;
                else if( BST->Right==NULL)
                     BST = BST->Left;
                free( Tmp );
            }
        return BST;
        }
    }

[http_www.icourse163.org_learn_ZJU-93001_tid_1002654021_learn_content_type_detail_id_1003620986]: http://www.icourse163.org/learn/ZJU-93001?tid=1002654021#/learn/content?type=detail&id=1003620986