C语言二叉排序树：创建、查找与输出详解（附代码示例）

本文将使用 C 语言实现二叉排序树，并提供详细的代码示例和解释，帮助您理解和学习二叉排序树的算法。

1. 二叉排序树简介

二叉排序树是一种特殊的二叉树，它满足以下性质：

• 左子树上所有节点的值均小于根节点的值；
• 右子树上所有节点的值均大于根节点的值；
• 左右子树也都是二叉排序树。

2. 代码实现

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

// 二叉排序树结点的定义
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 创建二叉排序树
Node* createBST(int data) {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = data;
    root->left = NULL;
    root->right = NULL;
    return root;
}

// 向二叉排序树中插入结点
Node* insertBST(Node* root, int data) {
    if (root == NULL) {
        root = createBST(data);
    } else {
        if (data < root->data) {
            root->left = insertBST(root->left, data);
        } else if (data > root->data) {
            root->right = insertBST(root->right, data);
        }
    }
    return root;
}

// 在二叉排序树中查找指定值
Node* searchBST(Node* root, int target) {
    if (root == NULL || root->data == target) {
        return root;
    } else if (target < root->data) {
        return searchBST(root->left, target);
    } else {
        return searchBST(root->right, target);
    }
}

// 输出二叉排序树（中序遍历）
void printBST(Node* root) {
    if (root != NULL) {
        printBST(root->left);
        printf('%d ', root->data);
        printBST(root->right);
    }
}

int main() {
    int n;
    printf('请输入整数的个数：');
    scanf('%d', &n);
    
    int data;
    printf('请输入整数：');
    scanf('%d', &data);
    Node* root = createBST(data);
    
    for (int i = 1; i < n; i++) {
        printf('请输入整数：');
        scanf('%d', &data);
        root = insertBST(root, data);
    }
    
    int target;
    printf('请输入要查找的整数：');
    scanf('%d', &target);
    Node* result = searchBST(root, target);
    
    if (result != NULL) {
        printf('找到了！\n');
    } else {
        printf('未找到！\n');
    }
    
    printf('二叉排序树中的元素为：');
    printBST(root);
    printf('\n');
    
    return 0;
}

3. 代码解释

• Node 结构体定义了二叉树的节点，包含数据域 data 和指向左右子节点的指针 left 和 right。
• createBST() 函数用于创建一个新的节点并初始化其数据。
• insertBST() 函数用于向二叉排序树中插入一个新的节点，它会根据节点的值将其插入到正确的位置，以维护二叉排序树的性质。
• searchBST() 函数用于在二叉排序树中查找指定值的节点，如果找到则返回该节点的指针，否则返回 NULL。
• printBST() 函数用于输出二叉排序树的所有节点，这里使用中序遍历的方式输出，以便按照从小到大的顺序输出所有节点的值。
• main() 函数是程序的入口，它首先创建一个二叉排序树，然后提示用户输入要查找的值，最后输出查找结果和二叉排序树的所有节点。

4. 总结

本文介绍了如何使用 C 语言实现二叉排序树，并提供了详细的代码示例和解释。二叉排序树是一种常用的数据结构，它可以高效地进行插入、删除、查找等操作，因此在实际应用中得到了广泛的应用。