数据结构：二叉搜索树（BST）全部基本操作

素颜马尾好姑娘i 2022-05-31 11:13 184阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node {
        int data;
        struct node* left;
        struct node* right;
    } Node;
    
    typedef struct {
        Node* root;
    } Tree;
    
    void insert(Tree* tree, int value) {//二叉搜索树插入 非递归
        Node* node = (Node* )malloc(sizeof(Node));
        node -> data = value;
        node -> left = NULL;
        node -> right = NULL;
    
        if (tree -> root == NULL) {
            tree -> root = node;
        }
        else {
            Node* temp = tree -> root;
            while (temp != NULL) {
                if (value < temp -> data) {
                    if (temp -> left == NULL) {
                        temp -> left = node;
                        return;
                    }
                    else {
                        temp = temp -> left;
                    }
                }
                else if (value > temp -> data) {
                    if (temp -> right == NULL) {
                        temp -> right = node;
                        return;
                    }
                    else {
                        temp = temp -> right;
                    }
                }
                else {
                    return;
                }
            }
        }
    }
    
    bool search(Tree* tree, int value) {//二叉搜索树查询 非递归
        Node* temp = tree -> root;
        while (temp != NULL) {
            if (temp -> data == value) {
                return true;
            }
            else if (value < temp -> data) {
                temp = temp -> left;
            }
            else {
                temp = temp -> right;
            }
        }
        return false;
    }
    
    void preorder(Node* node) {//前序遍历 递归
        if (node != NULL) {
            printf("%d", node -> data);
            preorder(node -> left);
            preorder(node -> right);
        }
    }
    
    void inorder(Node* node) {//中序遍历 递归
        if (node != NULL) {
            inorder(node -> left);
            printf("%d", node -> data);
            inorder(node -> right);
        }
    }
    
    void postorder(Node *node) {//后序遍历 递归
        if (node != NULL) {
            postorder(node -> left);
            postorder(node -> right);
            printf("%d", node -> data);
        }
    }
    
    int get_height(Node* node) {//获取树的高度 递归
        if (node == NULL) {
            return 0;
        }
        int left_h = get_height(node -> left);
        int right_h = get_height(node -> right);
        return (left_h > right_h ? left_h : right_h) + 1;
    }
    
    int get_max(Node* node) {//普通二叉树查找最大值 递归
        if (node == NULL) {
            return -999999;
        }
        else {
            int m1 = get_max(node -> left);
            int m2 = get_max(node -> right);
            int m3 = node -> data;
            int max = m1;
            if (m2 > max) { max = m2; }
            if (m3 > max) { max = m3; }
            return max;
        }
    }
    
    int get_min(Node* node) {//普通二叉树查找最小值 递归
        if (node == NULL) {
            return 9999999;
        }
        else {
            int m1 = get_min(node -> left);
            int m2 = get_min(node -> right);
            int m3 = node -> data;
            int min = m1;
            if (m2 < min) { min = m2; }
            if (m3 < min) { min = m3; }
            return min;
        }
    }
    
    int BST_get_min(Node* node) {//二叉搜索树查找最小值 递归
        if (node == NULL) {
            return -1;
        }
        else if (node -> left == NULL) {
            return node -> data;
        }
        return BST_get_min(node -> left);
    }
    
    int BST_get_max(Node* node) {//二叉搜索树查找最大值 递归
        if (node == NULL) {
            return -1;
        }
        else if (node -> right == NULL) {
            return node -> data;
        }
        return BST_get_max(node -> right);
    }
    
    bool BST_delete(Tree* tree, int value) {//二叉搜索树删除 非递归
        if (tree -> root == NULL) {
            return false;
        }
    
        Node* parents = NULL;
        Node* cur = tree -> root;
        Node* del = cur;
    
        while (cur != NULL && cur -> data != value) {
            if (value < cur -> data) {
                parents = cur;
                cur = cur -> left;
            }
            else if (value > cur -> data) {
                parents = cur;
                cur = cur -> right;
            }
        }
    
        if (cur == NULL) {
            return false;
        }
    
        if (cur -> left == NULL) {
            if (cur == tree -> root) {
                tree -> root = cur -> right;
            }
            else if (cur = parents -> left) {
                parents -> left = cur -> right;
            }
            else {
                parents -> right = cur -> right;
            }
            del = cur;
        }
    
        if (cur -> right == NULL) {//只有左孩子
            if (cur == tree -> root) {
                tree -> root = cur -> left;
            }
            else if (parents -> left == cur) {
                parents -> left = cur -> left;
            }
            else {
                parents -> right = cur -> left;
            }
            del = cur;
        }
    
        else {//有左右孩子
            Node* rights_left = cur -> right;
            parents = cur;
    
    
    
            while (rights_left -> left != NULL) {//找到右子树最左,没想到比rights_left更好的词来表示
                parents = rights_left;
                rights_left = rights_left -> left;
            }
    
            del = rights_left;
            cur -> data = rights_left -> data;//交换节点的值
    
            if (parents -> left == rights_left) {//排除右边第一个节点的左子树为空的情况
                parents -> left = rights_left -> right;
            }
            else {
                parents -> right = rights_left ->right;
            }
        }
        free(del);
    }
    
    int main(int argc, char **argv) {
        int arr[7] = {6, 3, 8, 2, 5, 1, 7};
        Tree tree;
        tree.root = NULL;
    
        for (int i=0; i<7; i++) {
            insert(&tree, arr[i]);
        }
    
        insert(&tree, 4);
        inorder(tree.root);
        BST_delete(&tree, 4);
        printf("\n");
        inorder(tree.root);
        return 0;
    }