二叉排序树的实现c语言

二叉排序树的C语言实现

下面是一个完整的二叉排序树（Binary Search Tree, BST）的C语言实现，包括插入、查找、删除、遍历等基本操作。

#include <stdio.h>
#include <stdlib.h>
// 二叉排序树节点结构
typedef struct BSTNode {
    int data;
    struct BSTNode *left;
    struct BSTNode *right;
} BSTNode;
// 创建新节点
BSTNode* createNode(int data) {
    BSTNode* newNode = (BSTNode*)malloc(sizeof(BSTNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
// 插入节点
BSTNode* insert(BSTNode* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    // 如果数据已存在，不插入
    return root;
}
// 查找最小值节点
BSTNode* findMin(BSTNode* root) {
    if (root == NULL) {
        return NULL;
    }
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}
// 删除节点
BSTNode* deleteNode(BSTNode* root, int data) {
    if (root == NULL) {
        return NULL;
    }
    // 查找要删除的节点
    if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        // 找到要删除的节点
        // 情况1: 叶子节点
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }
        // 情况2: 只有一个子节点
        else if (root->left == NULL) {
            BSTNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            BSTNode* temp = root->left;
            free(root);
            return temp;
        }
        // 情况3: 有两个子节点
        else {
            BSTNode* temp = findMin(root->right);
            root->data = temp->data;
            root->right = deleteNode(root->right, temp->data);
        }
    }
    return root;
}
// 查找节点
BSTNode* search(BSTNode* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    if (data < root->data) {
        return search(root->left, data);
    } else {
        return search(root->right, data);
    }
}
// 中序遍历（递增顺序）
void inorderTraversal(BSTNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}
// 先序遍历
void preorderTraversal(BSTNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}
// 后序遍历
void postorderTraversal(BSTNode* root) {
    if (root != NULL) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        printf("%d ", root->data);
    }
}
// 释放树内存
void freeTree(BSTNode* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}
// 计算树的高度
int height(BSTNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
// 计算节点数量
int countNodes(BSTNode* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}
int main() {
    BSTNode* root = NULL;
    // 插入节点
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 60);
    root = insert(root, 80);
    printf("中序遍历: ");
    inorderTraversal(root);
    printf("\n");
    printf("先序遍历: ");
    preorderTraversal(root);
    printf("\n");
    printf("后序遍历: ");
    postorderTraversal(root);
    printf("\n");
    printf("树的高度: %d\n", height(root));
    printf("节点数量: %d\n", countNodes(root));
    // 查找节点
    int searchValue = 40;
    BSTNode* found = search(root, searchValue);
    if (found != NULL) {
        printf("找到节点: %d\n", searchValue);
    } else {
        printf("未找到节点: %d\n", searchValue);
    }
    // 删除节点
    int deleteValue = 30;
    root = deleteNode(root, deleteValue);
    printf("删除 %d 后的中序遍历: ", deleteValue);
    inorderTraversal(root);
    printf("\n");
    // 释放树内存
    freeTree(root);
    return 0;
}

代码说明

1. 节点结构：BSTNode结构体包含数据域和左右子节点指针。

2. 基本操作：

   • createNode: 创建新节点
   • insert: 插入新节点（保持BST性质）
   • deleteNode: 删除节点（处理三种情况：叶子节点、单子节点、双子节点）
   • search: 查找节点
   • findMin: 查找最小值节点（用于删除双子节点的情况）

3. 遍历方式：

   • 中序遍历（递增顺序）
   • 先序遍历
   • 后序遍历

4. 辅助功能：

   • freeTree: 释放树内存
   • height: 计算树的高度
   • countNodes: 计算节点数量

5. 主函数：演示了各种操作的使用方法。

注意事项

1. 二叉排序树在最坏情况下（如插入已排序数据）会退化成链表，时间复杂度为O(n)，可以通过平衡二叉树（如AVL树、红黑树）来优化。

2. 删除操作是BST中最复杂的部分,需要仔细处理三种不同的情况。

3. 实际应用中可能需要添加错误处理和边界条件检查。

这个实现涵盖了二叉排序树的基本操作,可以根据需要进一步扩展功能。