C++ 二叉排序树

/*
二叉排序树（又叫二叉查找树）
*/

#include <iostream>

using namespace std;

typedef int KeyType;

// 树
typedef struct BSTNode {
    KeyType key;                     // 数据域
    struct BSTNode *lchild, *rchild; // 左孩子，右孩子
} BSTNode, *BiTree;

// 插入结点
int BST_Insert(BiTree &T, KeyType k) {
    if (T == NULL) { // 第一个结点作为树根
        T = (BSTNode *)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = NULL;
        return 1;
    } else if (k == T->key) {
        return 0; // 发现相同元素，不插入
    } else if (k < T->key) {
        return BST_Insert(T->lchild, k); // 插入结点小于当前结点，插入左边
    } else {
        return BST_Insert(T->rchild, k); // 插入结点小于当前结点，插入右边
    }
}

// 构建二叉排序树
void Creat_BST(BiTree &T, KeyType str[], int n) {
    T = NULL;
    int i = 0;
    while (i < n) {
        BST_Insert(T, str[i]); // 把某一结点放入二叉排序树
        i++;
    }
}

// 二叉排序树的查找
BSTNode *BST_Search(BiTree T, KeyType key, BSTNode *&p) {
    p = NULL;
    while (T != NULL && key != T->key) {
        p = T;
        if (key < T->key) {
            T = T->lchild;
        } else {
            T = T->rchild;
        }
    }
    return T; // 没有引用，不会造成影响
}

// 删除结点
void DeleteNode(BSTNode *&root, KeyType x) {
    if (root == NULL) {
        return;
    }
    if (root->key > x) {
        DeleteNode(root->lchild, x);
    } else if (root->key < x) {
        DeleteNode(root->rchild, x);
    } else {                        // 查找到了删除结点
        if (root->lchild == NULL) { // 左子树为空
            BSTNode *tempNode = root;
            root = root->rchild; // 直接将右子树赋值该结点，然后释放
            free(tempNode);
        } else if (root->rchild == NULL) { // 右子树为空
            BSTNode *tempNode = root;
            root = root->lchild; // 直接将右子树赋值该结点，然后释放
            free(tempNode);
        } else { // 左右子树都不为空
            // 删除策略：选取左子树的最大数据 或 右子树的最小数据
            // 此处策略寻找左子树的最大数据
            BSTNode *tempNode = root->lchild;
            if (tempNode->rchild != NULL) {
                tempNode = tempNode->rchild; // 左子树的最大数据，一定位于左子树的最右结点，右子树的最小数据，一定位于右子树的最左结点
            }
            root->key = tempNode->key; // 将左子树的最大结点置于根结点，再删除左子树的对应结点
            DeleteNode(root->lchild, tempNode->key);
        }
    }
}

// 中序遍历：左根右
void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild);
        cout << T->key << " ";
        // putchar(T->key);
        InOrder(T->rchild);
    }
}

int main() {
    BiTree T;        // 树根
    BSTNode *parent; // 存储父亲结点的地址
    BSTNode *search; // 查找结点
    KeyType str[] = {54, 20, 66, 40, 28, 79, 58};
    Creat_BST(T, str, 7);
    InOrder(T);

    printf("\n");
    search = BST_Search(T, 40, parent);
    if (search) {
        printf("找到对应结点，值=%d\n", search->key);
    } else {
        printf("未找到对应结点\n");
    }

    DeleteNode(T, 40);
    InOrder(T);

    return 0;
}