二叉搜索树 c语言

以下是一个简单的二叉搜索树的 C 语言实现：

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

struct node {
    int data;
    struct node* left;
    struct node* right;
};

struct node* create_node(int data) {
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

struct node* insert_node(struct node* root, int data) {
    if (root == NULL) {
        return create_node(data);
    } else if (data < root->data) {
        root->left = insert_node(root->left, data);
    } else if (data > root->data) {
        root->right = insert_node(root->right, data);
    }
    return root;
}

void inorder_traversal(struct node* root) {
    if (root != NULL) {
        inorder_traversal(root->left);
        printf("%d ", root->data);
        inorder_traversal(root->right);
    }
}

int main() {
    struct node* root = NULL;
    root = insert_node(root, 5);
    insert_node(root, 3);
    insert_node(root, 8);
    insert_node(root, 1);
    insert_node(root, 4);
    insert_node(root, 7);
    insert_node(root, 9);

    printf("Inorder traversal of the binary search tree: ");
    inorder_traversal(root);

    return 0;
}

在此实现中，我们定义了一个结构体 `node` 来表示二叉搜索树中的一个节点。每个节点包含一个整数值 `data`，以及指向其左子节点和右子节点的指针 `left` 和 `right`。

我们还定义了一个 `create_node` 函数，用于创建一个新的节点。该函数分配了一个新的节点并初始化其数据和指针。

`insert_node` 函数用于将新的节点插入到二叉搜索树中。如果根节点为空，则它将创建一个新的节点并将其设置为根节点。否则，它将根据值的大小将新节点插入到树的适当位置。

最后，我们定义了一个 `inorder_traversal` 函数，用于按中序遍历顺序打印二叉搜索树中的所有节点。在此实现中，我们使用递归来遍历树，并在遍历每个节点时打印其值。

在 `main` 函数中，我们创建了一个空的二叉搜索树，并使用 `insert_node` 函数将几个节点插入树中。然后，我们使用 `inorder_traversal` 函数按中序遍历顺序打印树中的所有节点。