Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/(C)840数据结构与算法/5.二叉排序树.md

#pragma clang diagnostic push
#pragma ide diagnostic ignored "misc-no-recursion"

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

typedef int ElementType;

struct BSTreeNode {
    ElementType Data;
    struct BSTreeNode *Left;
    struct BSTreeNode *Right;
};

struct BSTreeNode *Find(struct BSTreeNode *T, ElementType X) {
    if (T == NULL) {
        return NULL;
    }
    if (X < T->Data) {
        return Find(T->Left, X);
    } else if (X > T->Data) {
        return Find(T->Right, X);
    } else {
        return T;
    }
}

struct BSTreeNode *FindMinRecursion(struct BSTreeNode *T) {
    //二叉排序树查找最小结点， 最小结点必在二叉排序树的最左侧
    if (T == NULL) {
        return NULL;
    }
    return (T->Left == NULL) ? T : FindMinRecursion(T->Left);
}

struct BSTreeNode *FindMaxRecursion(struct BSTreeNode *T) {
    //二叉排序树查找最大结点， 最大结点必在二叉排序树的最右侧
    if (T == NULL) {
        return NULL;
    }
    return (T->Right == NULL) ? T : FindMaxRecursion(T->Right);
}

struct BSTreeNode *FindMinIterate(struct BSTreeNode *T) {
    //二叉排序树查找最小结点， 最小结点必在二叉排序树的最左侧
    if (T == NULL) {
        return NULL;
    }
    while (T->Left != NULL) {
        T = T->Left;
    }
    return T;
}

struct BSTreeNode *FindMaxIterate(struct BSTreeNode *T) {
    //二叉排序树查找最大结点， 最大结点必在二叉排序树的最右侧
    if (T == NULL) {
        return NULL;
    }
    while (T->Right != NULL) {
        T = T->Right;
    }
    return T;
}

/*
二叉排序树的插入
如果该树为空树，则生成新结点，并置左右孩子为空
否则
(1)若插入值与根结点相同，取消插入
(2)若插入值小于根结点，在左子树中插入
(3)若插入值大于根结点，在右子树中插入
按照此方法插入，插入的结点必为叶结点
只要插入后满足二叉排序树定义，任何插入方法均可
 */
struct BSTreeNode *InsertBST(struct BSTreeNode *T, ElementType key) {
    if (T == NULL) {
        T = malloc(sizeof(struct BSTreeNode));
        T->Data = key;
        T->Left = T->Right = NULL;
    } else if (key < T->Data)
        T->Left = InsertBST(T->Left, key);
    else if (key > T->Data)
        T->Right = InsertBST(T->Right, key);
    // else key == T->data的情况，不做任何事

    return T; // 注意：由于插入后树根可能发生变化，因此必须返回新根
}

/*
(1)被删除的结点是叶子结点
其双亲结点中相应指针域的值改为“空”
(2)被删除的结点只有左子树或者只有右子树
其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。
(3)被删除的结点既有左子树，也有右子树
在其右子树中找到最小结点，将其值拷贝到根结点，然后删掉此最小结点（该结点必然有0或1个子树，从而满足第1、2种删除情况）
 */
struct BSTreeNode *DeleteBST(struct BSTreeNode *T, ElementType X) {
    if (T == NULL) {
        return NULL;
    }
    struct BSTreeNode *q;
    if (X < T->Data) {
        T->Left = DeleteBST(T->Left, X);
    } else if (X > T->Data) {
        T->Right = DeleteBST(T->Right, X);
    } else {
        if (T->Left != NULL && T->Right != NULL) {
            q = FindMinIterate(T->Right);
            T->Data = q->Data;
            T->Right = DeleteBST(T->Right, q->Data);
        } else {
            q = T;
            if (T->Left == NULL) {
                T = T->Right;
            } else if (T->Right == NULL) {
                T = T->Left;
            }
            free(q);
        }
    }
    return T;
}

void Visit(struct BSTreeNode *T) {
    printf("%d ", T->Data);
}

void PreOrder(struct BSTreeNode *T) {
    if (T != NULL) {
        Visit(T);
        PreOrder(T->Left);
        PreOrder(T->Right);
    }
}

void PrintPreOrder(struct BSTreeNode *T) {
    printf("PreOrder: ");
    PreOrder(T);
    printf("\n");
}

void InOrder(struct BSTreeNode *T) {
    if (T != NULL) {
        InOrder(T->Left);
        Visit(T);
        InOrder(T->Right);
    }
}

void PrintInOrder(struct BSTreeNode *T) {
    printf("InOrder: ");
    InOrder(T);
    printf("\n");
}

void PostOrder(struct BSTreeNode *T) {
    if (T != NULL) {
        PostOrder(T->Left);
        PostOrder(T->Right);
        Visit(T);
    }
}

void PrintPostOrder(struct BSTreeNode *T) {
    printf("PostOrder: ");
    PostOrder(T);
    printf("\n");
}

int main() {
    struct BSTreeNode *T = NULL;
    T = InsertBST(T, 20);
    T = InsertBST(T, 5);
    T = InsertBST(T, 4);
    T = InsertBST(T, 8);
    T = InsertBST(T, 31);
    T = InsertBST(T, 25);
    T = InsertBST(T, 30);

    T = DeleteBST(T, 30);

    PrintPreOrder(T);
    PrintInOrder(T);
    PrintPostOrder(T);


    free(T);
    return 0;
}

#pragma clang diagnostic pop