二叉树创建，二叉排序树新建，中序遍历，查找，删除

二叉树创建，二叉排序树新建，中序遍历，查找，删除

#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;
typedef struct BSTNode {
    KeyType key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BiTree;

int insertBST(BiTree &T, KeyType k) {
    BiTree treeNew = (BiTree) calloc(1, sizeof(BSTNode));// 给新节点申请空间
    treeNew->key = k;
    if (NULL == T) {  // T 是树根
        T = treeNew;
        return 1;
    }
    BiTree p = T, parent; // 用来查找树
    while (p) {
        parent = p; // parent用来存储p的父亲
        if (k > p->key) {
            p = p->rchild;
        } else if (k < p->key) {
            p = p->lchild;
        } else {
            return -1;  // 相等的元素不可以放入查找树
        }
    }
    // 接下来要判断放到父亲的左边还是右边
    if (k > parent->key) {
        parent->rchild = treeNew;
    } else {
        parent->lchild = treeNew;
    }
    return 0;
}

// 创建二叉查找树
void createBST(BiTree &T, KeyType *str, int len) {
    int i;
    for (i = 0; i < len; i++) {
        insertBST(T, str[i]);
    }
}

// 创建二叉树排序
void createBSTOrder(BiTree &T, KeyType *str, int len) {
    T = NULL; // T 是树根
    int i;
    while (i < len) {
        insertBST(T, str[i]);
        i++;
    }
}

// 中序遍历，从小到大
void inOrder(BiTree T) {
    if (T != NULL) {
        inOrder(T->lchild);
        printf("%3d", T->key);
        inOrder(T->rchild);
    }
}

// 查找
BiTree searchBST(BiTree T, KeyType k, BiTree parent) {
    parent = NULL;
    while (T != NULL && k != T->key) {
        parent = T;
        if (k < T->key) {
            T = T->lchild;
        } else {
            T = T->rchild;
        }
    }
    return T;
}

// 删除 递归实现
void deleteNode(BiTree &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) { //左子树为空，右子树直接顶上去
            BiTree tempNode = root;//用临时的存着的目的是一会要 free
            root = root->rchild;
            free(tempNode);
        } else if (root->rchild == NULL) { //右子树为空，左子树直接顶上去
            BiTree tempNode = root;//临时指针
            root = root->lchild;
            free(tempNode);
        } else { //左右子树都不为空
            //一般的删除策略是左子树的最大数据 或 右子树的最小数据 代替要删除的节点(这里采用查找左子树最大数据来代替)
            BiTree tempNode = root->lchild;
            while (tempNode->rchild != NULL) {//向右找到最大的
                tempNode = tempNode->rchild;
            }
            root->key = tempNode->key;//把 tempNode 对应的值替换到要删除的值的位置上
            deleteNode(root->lchild, tempNode->key);//删除 tempNode
        }
    }
}

// 二叉树创建，二叉排序树新建，中序遍历，查找，删除
int main() {
    BiTree T = NULL;//树根
    BiTree parent;//存储父亲结点的地址值
    BiTree search;
    KeyType str[7] = {54, 20, 66, 40, 28, 79, 58};//将要进入二叉排序树的元素值
    // 创建二叉树
    createBST(T, str, 7);
    // 遍历
    inOrder(T);
    printf("\n");
    search = searchBST(T, 40, parent);
    if (search) {
        printf("找到相应的节点=%d\n", search->key);
    } else {
        printf("没有找到");
    }
    // 创建二叉排序树
    createBSTOrder(T, str, 7);
    printf("排序后的二叉树\n");
    inOrder(T);
    printf("\n");
    // 删除某个节点
    deleteNode(T, 40);
    inOrder(T);
    return 0;
}