二叉查找树

二叉查找树（Binary Search Tree，简称BST）是一种二叉树，它的每个节点都满足以下条件：

• 如果一个节点有左子树，则左子树中所有节点的值都小于该节点的值。
• 如果一个节点有右子树，则右子树中所有节点的值都大于该节点的值。
• 左右子树都是二叉查找树。

这个性质使得二叉查找树的节点可以按照大小关系被快速地查找、插入和删除。

下面是一个简单的C语言实现二叉查找树的代码：

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

typedef struct bst_node {
    int value;
    struct bst_node *left;
    struct bst_node *right;
} bst_node;

bst_node *bst_insert(bst_node *node, int value) {
    if (node == NULL) {
        bst_node *new_node = (bst_node *)malloc(sizeof(bst_node));
        new_node->value = value;
        new_node->left = NULL;
        new_node->right = NULL;
        return new_node;
    } else if (value < node->value) {
        node->left = bst_insert(node->left, value);
    } else if (value > node->value) {
        node->right = bst_insert(node->right, value);
    }
    return node;
}

void bst_traverse(bst_node *node) {
    if (node == NULL) {
        return;
    }
    bst_traverse(node->left);
    printf("%d ", node->value);
    bst_traverse(node->right);
}

void bst_destroy(bst_node *node) {
    if (node == NULL) {
        return;
    }
    bst_destroy(node->left);
    bst_destroy(node->right);
    free(node);
}

int main() {
    bst_node *root = NULL;
    int i;
    int data[10] = { 4, 2, 6, 1, 3, 5, 7, 8, 9, 0 };
    for (i = 0; i < 10; i++) {
        root = bst_insert(root, data[i]);
    }
    bst_traverse(root);
    printf("\n");
    bst_destroy(root);
    return 0;
}

这个代码实现了二叉查找树的插入、遍历和销毁操作。在插入时，如果节点为空，则创建一个新节点，否则根据节点的大小关系递归地插入到左子树或右子树中。在遍历时，先遍历左子树，然后输出节点的值，最后遍历右子树。在销毁时，先销毁左子树和右子树，然后释放节点的内存。