二叉搜索树(BinarySearchTree): 用于实现快速的查找, 同时支持快速插入和删除。
BST要求: 在树种的任意一个节点, 其左子树的每个节点的值都要小于该节点的值, 其右子树的每个节点的值都要大于该节点的值。

#include <stdio.h>
#include <stdlib.h>typedef struct tree_node {int value;struct tree_node *left;struct tree_node *right;
} tree_node_t;tree_node_t *create_tree_node(int value)
{tree_node_t *new_node = (tree_node_t *)malloc(sizeof(tree_node_t));if (new_node == NULL) {printf("malloc for new tree node failed.\n");return NULL;}new_node->value = value;new_node->left = NULL;new_node->right = NULL;return new_node;
}void binary_search_tree_insert(tree_node_t **node, int value)
{if (*node == NULL) {*node = create_tree_node(value);} else if (value < (*node)->value) {return binary_search_tree_insert(&(*node)->left, value);} else if (value > (*node)->value) {return binary_search_tree_insert(&(*node)->right, value);} else {printf("value: %d is alread exist in bst.\n", value);}
}void inorder_traversal(tree_node_t *root)
{if (root == NULL) {return;}inorder_traversal(root->left);printf("%d ", root->value);inorder_traversal(root->right);
}int main()
{tree_node_t *root = NULL;int numbers[] = {50, 30, 70, 10, 40, 60, 90, 20, 80, 100, 0};int size = sizeof(numbers) / sizeof(numbers[0]);for (int i = 0; i < size; i++) {binary_search_tree_insert(&root, numbers[i]);}printf("inorder traversal of binary search tree: \n");inorder_traversal(root);return 0;
}