数据结构——树——二叉搜索树

电玩女神 2022-04-16 02:53 319阅读 0赞

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。  
二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，O(log(n)).  
![在这里插入图片描述][20181115221203876.PNG]

## 二叉搜索树操作 ##

![在这里插入图片描述][20181115221235426.PNG]![在这里插入图片描述][20181115221344315.PNG]  
![在这里插入图片描述][20181115221430784.PNG]![在这里插入图片描述][20181115221509565.PNG]

## 最小元素和最大元素 ##

![在这里插入图片描述][20181115221600760.PNG]![在这里插入图片描述][20181115221700325.PNG]

## 二叉搜索树的插入算法 ##

BinTree Insert( BinTree BST, ElementType X )
    {
        
        if( !BST ){
         /* 若原树为空，生成并返回一个结点的二叉搜索树 */
            BST = (BinTree)malloc(sizeof(struct TNode));
            BST->Data = X;
            BST->Left = BST->Right = NULL;
        }
        else {
         /* 开始找要插入元素的位置 */
            if( X < BST->Data )
                BST->Left = Insert( BST->Left, X );   /*递归插入左子树*/
            else  if( X > BST->Data )
                BST->Right = Insert( BST->Right, X ); /*递归插入右子树*/
            /* else X已经存在，什么都不做 */
        }
        return BST;
    }

## 二叉搜索树的删除 ##

![在这里插入图片描述][20181115221835365.PNG]![在这里插入图片描述][20181115231056213.PNG]![在这里插入图片描述][20181115231153434.PNG]

## 算法实现 ##

BinTree Delete( BinTree BST, ElementType X ) 
    {
         
        Position Tmp; 
     
        if( !BST ) 
            printf("要删除的元素未找到"); 
        else {
        
            if( X < BST->Data ) 
                BST->Left = Delete( BST->Left, X );   /* 从左子树递归删除 */
            else if( X > BST->Data ) 
                BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */
            else {
         /* BST就是要删除的结点 */
                /* 如果被删除结点有左右两个子结点 */ 
                if( BST->Left && BST->Right ) {
        
                    /* 从右子树中找最小的元素填充删除结点 */
                    Tmp = FindMin( BST->Right );
                    BST->Data = Tmp->Data;
                    /* 从右子树中删除最小元素 */
                    BST->Right = Delete( BST->Right, BST->Data );
                }
                else {
         /* 被删除结点有一个或无子结点 */
                    Tmp = BST; 
                    if( !BST->Left )       /* 只有右孩子或无子结点 */
                        BST = BST->Right; 
                    else                   /* 只有左孩子 */
                        BST = BST->Left;
                    free( Tmp );
                }
            }
        }
        return BST;
    }

[练习：是否同一棵二叉搜索树][Link 1]  
[练习：搜索树判断][Link 2]  
[ 二叉搜索树的操作集][Link 3]

[20181115221203876.PNG]: /images/20220416/5b23afb9f8e34b29999fd528c9610b27.png
[20181115221235426.PNG]: https://img-blog.csdnimg.cn/20181115221235426.PNG
[20181115221344315.PNG]: /images/20220416/0dd56206feba497eba800ee01c10b586.png
[20181115221430784.PNG]: https://img-blog.csdnimg.cn/20181115221430784.PNG
[20181115221509565.PNG]: /images/20220416/8fc25542c4994d638f9587891c9e9498.png
[20181115221600760.PNG]: https://img-blog.csdnimg.cn/20181115221600760.PNG
[20181115221700325.PNG]: /images/20220416/324c8ef46c5740939ca664f0815d1881.png
[20181115221835365.PNG]: https://img-blog.csdnimg.cn/20181115221835365.PNG
[20181115231056213.PNG]: https://img-blog.csdnimg.cn/20181115231056213.PNG
[20181115231153434.PNG]: /images/20220416/8524139997aa452190b4ac766e5a680b.png
[Link 1]: https://blog.csdn.net/qq_42623428/article/details/83661047
[Link 2]: https://blog.csdn.net/qq_42623428/article/details/83792118
[Link 3]: https://blog.csdn.net/qq_42623428/article/details/83661895