C语言实现二叉搜索树：概念、操作及应用示例

实验目的： 掌握二叉搜索树的基本概念和操作，了解二叉搜索树的应用。

实验原理： 二叉搜索树是一种基于二分查找的数据结构，它是由一棵根节点和两个子树构成的，左子树上所有节点的值都小于根节点的值，右子树上所有节点的值都大于根节点的值。二叉搜索树的插入、查找和删除操作都可以在O(log n)的时间内完成，因此在实际应用中非常常见。

实验内容：

实现二叉搜索树的基本操作，包括插入、查找和删除。
对二叉搜索树进行遍历，包括前序遍历、中序遍历和后序遍历。
应用二叉搜索树解决实际问题，比如查找最小值、最大值、查找某个节点、判断二叉树是否平衡等。

实验步骤：

定义节点结构体:

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

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

实现插入操作:

// 插入节点
TreeNode* insert(TreeNode* root, int val) {
    if (root == NULL) {
        root = (TreeNode*) malloc(sizeof(TreeNode));
        root->val = val;
        root->left = NULL;
        root->right = NULL;
    } else if (val < root->val) {
        root->left = insert(root->left, val);
    } else {
        root->right = insert(root->right, val);
    }    
    return root;
}

实现查找操作:

// 查找节点
TreeNode* search(TreeNode* root, int val) {
    if (root == NULL || root->val == val) {
        return root;
    } else if (val < root->val) {
        return search(root->left, val);
    } else {
        return search(root->right, val);
    }    
}

实现删除操作:

// 删除节点
TreeNode* delete(TreeNode* root, int val) {
    if (root == NULL) {
        return root;
    } else if (val < root->val) {
        root->left = delete(root->left, val);
    } else if (val > root->val) {
        root->right = delete(root->right, val);
    } else {
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        TreeNode* temp = root->right;
        while (temp->left != NULL) {
            temp = temp->left;
        }
        root->val = temp->val;
        root->right = delete(root->right, temp->val);
    }    
    return root;
}

实现遍历操作:

// 前序遍历
void preorder(TreeNode* root) {
    if (root != NULL) {
        printf('%d ', root->val);
        preorder(root->left);
        preorder(root->right);
    }
}

// 中序遍历
void inorder(TreeNode* root) {
    if (root != NULL) {
        inorder(root->left);
        printf('%d ', root->val);
        inorder(root->right);
    }
}

// 后序遍历
void postorder(TreeNode* root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf('%d ', root->val);
    }
}

实现应用示例:

// 查找最小值
int findMin(TreeNode* root) {
    if (root == NULL) {
        return -1;
    }
    while (root->left != NULL) {
        root = root->left;
    }
    return root->val;
}

// 查找最大值
int findMax(TreeNode* root) {
    if (root == NULL) {
        return -1;
    }
    while (root->right != NULL) {
        root = root->right;
    }
    return root->val;
}

// 判断是否存在节点
int hasNode(TreeNode* root, int val) {
    if (root == NULL) {
        return 0;
    } else if (root->val == val) {
        return 1;
    } else if (val < root->val) {
        return hasNode(root->left, val);
    } else {
        return hasNode(root->right, val);
    }    
}

// 判断是否平衡
int isBalanced(TreeNode* root) {
    if (root == NULL) {
        return 1;
    }
    int left = getHeight(root->left);
    int right = getHeight(root->right);
    if (abs(left - right) <= 1 && isBalanced(root->left) && isBalanced(root->right)) {
        return 1;
    }
    return 0;
}

// 获取节点高度
int getHeight(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int left = getHeight(root->left);
    int right = getHeight(root->right);
    return left > right ? left + 1 : right + 1;
}

int main() {
    TreeNode* root = NULL;
    root = insert(root, 5);
    root = insert(root, 3);
    root = insert(root, 7);
    root = insert(root, 1);
    root = insert(root, 4);
    root = insert(root, 6);
    root = insert(root, 8);

    printf("Preorder traversal: ");
    preorder(root);
    printf("\n");

    printf("Inorder traversal: ");
    inorder(root);
    printf("\n");

    printf("Postorder traversal: ");
    postorder(root);
    printf("\n");

    printf("Min value: %d\n", findMin(root));
    printf("Max value: %d\n", findMax(root));

    printf("Has node with value 4: %d\n", hasNode(root, 4));
    printf("Has node with value 2: %d\n", hasNode(root, 2));

    printf("Is balanced: %d\n", isBalanced(root));

    root = delete(root, 5);

    printf("Preorder traversal after deleting 5: ");
    preorder(root);
    printf("\n");

    return 0;
}

实验结果：

Preorder traversal: 5 3 1 4 7 6 8 
Inorder traversal: 1 3 4 5 6 7 8 
Postorder traversal: 1 4 3 6 8 7 5 
Min value: 1
Max value: 8
Has node with value 4: 1
Has node with value 2: 0
Is balanced: 1
Preorder traversal after deleting 5: 6 3 1 4 7 8

实验结论： 本次实验成功实现了二叉搜索树的基本操作，包括插入、查找和删除，以及遍历和应用等操作。二叉搜索树是一种非常高效的数据结构，可以用来解决多种实际问题。