6-12二叉搜索树的操作集

题目描述

实现给定二叉搜索树的5种常用操作。

题目地址为:https://pintia.cn/problem-sets/15/problems/927

BinTree结构定义 

1
2
3
4
5
6
7
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

插入结点

要求

函数Insert将X插入二叉搜索树BST并返回结果树的根结点指针。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
BinTree Insert( BinTree BST, ElementType X ) {
    BinTree node = (BinTree)malloc(sizeof(struct TNode));
    node->Data = X;
    node->Left = NULL;
    node->Right = NULL;

    if (!BST) {
        return node;
    }

    if (X > BST->Data) {
        BST->Right = Insert(BST->Right,X);
    } else if (X < BST->Data) {
        BST->Left = Insert(BST->Left,X);
    } else {
        return BST;
    }
    return BST;
}

删除结点

要求

函数Delete将X从二叉搜索树BST中删除，并返回结果树的根结点指针；如果X不在树中，则打印一行Not Found并返回原树的根结点指针。

找到最小或者最大的结点直接替换掉删除的结点，然后查找到这个用于替换的结点在树中进行删除。因为它必为叶子结点,或单孩子结点。

算法导论上的结论就有些晦涩难懂了。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
BinTree Delete( BinTree BST, ElementType X ) {
    if (!BST){
        printf("Not Found\n");
        return NULL;
    }
    if (X > BST->Data) {
        BST->Right = Delete(BST->Right,X);
    } else if (X < BST->Data) {
        BST->Left = Delete(BST->Left,X);
    } else { //删除操作
        Position Node;
        if (BST->Left && BST->Right) {
            Node = FindMin(BST->Right);
            BST->Data = Node->Data;
            BST->Right = Delete(BST->Right, BST->Data);
        } else {
            Node = BST;
            if (BST->Left == NULL)
                BST = BST->Right;
            else if (BST->Right == NULL)
                BST = BST->Left;
            free(Node);
        }
    }
    return BST;
}

查找结点

要求

函数Find在二叉搜索树BST中找到X，返回该结点的指针；如果找不到则返回空指针。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
Position Find( BinTree BST, ElementType X ) {
    while (BST) {
        if (X == BST->Data) {
            return BST;
        } else if (X < BST->Data) {
            BST=BST->Left;
        } else {
            BST=BST->Right;
        }
    }
    return NULL;
}

查找最小结点

要求

函数FindMin返回二叉搜索树BST中最小元结点的指针。

在树最左边的叶节点就是最小结点。

具体代码

1
2
3
4
5
6
7
8
9
Position FindMin( BinTree BST ) {
    if (!BST) {
        return NULL;
    }
    while (BST->Left) {
        BST=BST->Left;
    }
    return BST;
}

查找最大结点

要求

函数FindMax返回二叉搜索树BST中最大元结点的指针。

在树最右边的叶节点就是最大结点。

具体代码

1
2
3
4
5
6
7
8
9
Position FindMax( BinTree BST ) {
    if (!BST) {
        return NULL;
    }
    while (BST->Right) {
        BST=BST->Right;
    }
    return BST;
}