二叉搜索树：
- 树不是线性的，是层级结构。
- 基本单位是节点，每个节点最多2个子节点。
- 有序。每个节点，其左子节点都比它小，其右子节点都比它大。
- 每个子树都是一个二叉搜索树。每个节点及其所有子节点形成子树。
- 可以是空树。
添加元素：从根节点开始，比对数值。若比它小，往左子树比对；若比它大，往右子树比对；直到找到为空，则为新元素的位置。
删除元素：
- 若删除的节点为叶子节点（即无子节点），则直接删除。
- 若删除的节点只有左子节点，则左子节点替代删除节点。
- 若删除的节点只有右子节点，则右子节点替代删除节点。
- 若删除的节点既有左子节点又有右子节点，则找到直接前驱（即删除节点的左子树中的最大值，即删除节点的左子节点的最右节点），直接前驱的值替代删除节点的值，删除直接前驱节点。
清空树：从根节点开始遍历，依次从叶子节点开始 释放每个节点的内存空间，最终根节点指向NULL。
遍历元素：（可使用递归）
- 前序遍历（顺序：根节点、左子节点、右子节点）。
- 中序遍历（顺序：左子节点、根节点、右子节点）。
- 后序遍历（顺序：左子节点、右子节点、根节点）。
查找元素：从根节点开始，比对数值。若比它小，往左子树查找；若比它大，往右子树查找；直到找到该元素，则返回1（true），若没有，则返回0（false）。
C语言实现：（使用链表实现）
创建结构体数据类型（记录二叉搜索树的根节点和数据个数）：
typedef struct Link
{LinkNode *root; // 根节点int length; // 统计有多少数据
} LinkBST; // 别名创建二叉搜索树，并初始化：
LinkBST bst;
bst.root = NULL; // 根节点，初始化为NULL
bst.length = 0; // 数据个数，初始化为0创建节点（结构体数据类型），并创建具体节点实例的函数：
// 节点（结构体数据类型）
typedef struct Node
{int value; // 数据类型为整型struct Node *left; // 左子节点struct Node *right; // 右子节点
}LinkNode; // 别名// 函数：创建节点
LinkNode *createNode(int data)
{LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode)); // 分配节点内存空间if(node == NULL){perror("Memory allocation failed");exit(-1);}node->value = data; // 数据node->left = NULL; // 左子节点，初始化为NULLnode->right = NULL; // 右子节点，初始化为NULLreturn node;
}添加元素：
void add(LinkBST *bst, int data) // add element
{// 函数：往二叉搜索树中添加元素 LinkNode *addNode(LinkNode *node, int data){if(node == NULL){LinkNode *newnode = createNode(data);node = newnode;bst->length++; // 每添加一个元素，length+1return node;}if(data < node->value) node->left = addNode(node->left, data);else if(data > node->value) node->right = addNode(node->right, data);return node;}// 从根节点开始比对，root指针始终指向二叉搜索树的根节点bst->root = addNode(bst->root, data);
}删除元素：
void delete(LinkBST *bst, int data) // delete element
{// 函数：删除节点 LinkNode *del(LinkNode *node){ // 若只有右子节点，则右子节点替代删除节点if(node->left == NULL){bst->length--; // 每删除一个元素，length-1return node->right;}// 若只有左子节点，则左子节点替代删除节点else if(node->right == NULL){bst->length--; // 每删除一个元素，length-1return node->left;}// 左右子节点都有，则直接前驱(左子节点的最右节点)替代删除节点，并删除直接前驱else if(node->left && node->right){LinkNode *tmp = node, *cur = node->left;while(cur->right){tmp = cur;cur = cur->right;}node->value = cur->value;if(tmp != node) tmp->right = cur->left;else tmp->left = cur->left;bst->length--; // 每删除一个元素，length-1return node;}}// 函数：找到将要删除的节点LinkNode *delNode(LinkNode *node, int data){if(node == NULL) return node;if(data == node->value) node = del(node);else if(data < node->value) node->left = delNode(node->left, data);else if(data > node->value) node->right = delNode(node->right, data);return node;} // 从根节点开始比对。root指针始终指向二叉搜索树的根节点bst->root = delNode(bst->root, data);
}清空树：
void clear(LinkBST *bst)
{// 函数：释放每个节点的内存空间void clearNode(LinkNode *node){if(node->left == NULL && node->right == NULL){free(node); // 使用malloc动态分配内存空间，不使用时需使用free释放内存空间node == NULL; // 释放内存空间后，指针指向NULL，避免野指针return ;}if(node->left) clearNode(node->left);if(node->right) clearNode(node->right);}// 树非空，释放所有节点的内存空间，根节点为NULL，数据个数为0if(bst->root == NULL) return ;clearNode(bst->root); // 从根节点开始遍历，依次从叶子节点开始释放内存空间bst->root = NULL; // 根节点指向NULLbst->length = 0; // 数据个数为0
}遍历元素：（使用递归）
// 前序遍历（根，左，右）
void pretravel(LinkNode *node)
{if(node == NULL) return ;printf("%d ", node->value);pretravel(node->left);pretravel(node->right);
}// 中序遍历（左，根，右）
void midtravel(LinkNode *node)
{if(node == NULL) return ;midtravel(node->left);printf("%d ", node->value);midtravel(node->right);
}// 后序遍历（左，右，根）
void posttravel(LinkNode *node)
{if(node == NULL) return ;posttravel(node->left);posttravel(node->right);printf("%d ", node->value);
}查找元素：
找到元素，返回1(true)；没找到，返回0(false)。
int find(LinkNode *node, int data)
{if(node == NULL) return 0;if(data == node->value) return 1;if(data < node->value) find(node->left, data);else if(data > node->value) find(node->right, data);
}完整代码：（bst.c）
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>/* structure */
typedef struct Node // linkedlist node
{int value; // value type is integerstruct Node *left; // left child nodestruct Node *right; // right child node
}LinkNode;typedef struct Link // binary search tree
{LinkNode *root; // root node of the treeint length; // the number of the tree
} LinkBST;/* function prototype */
void add(LinkBST *, int); // add element to the tree
void delete(LinkBST *, int); // delete element from the tree
void clear(LinkBST *); // clear the tree
void pretravel(LinkNode *); // show element one by one,(root,left,right)
void midtravel(LinkNode *); // show element one by one,(left,root,right)
void posttravel(LinkNode *); // show element one by one,(left,right,root)
int find(LinkNode *, int); // if find data,return 1(true),or return 0(false)/* main function */
int main(void)
{// create binary search tree and initializationLinkBST bst;bst.root = NULL;bst.length = 0;printf("isempty(1:true, 0:false): %d, length is %d\n", bst.root==NULL, bst.length);add(&bst, 15);add(&bst, 8);add(&bst, 23);add(&bst, 10);add(&bst, 12);add(&bst, 19);add(&bst, 6);printf("isempty(1:true, 0:false): %d, length is %d\n", bst.root==NULL, bst.length);printf("midtravel: ");midtravel(bst.root);printf("\n");printf("pretravel: ");pretravel(bst.root);printf("\n");printf("posttravel: ");posttravel(bst.root);printf("\n");printf("find 10 (1:true, 0:false): %d\n", find(bst.root, 10));printf("find 9 (1:true, 0:false): %d\n", find(bst.root, 9));delete(&bst, 23);delete(&bst, 15);delete(&bst, 6);printf("isempty(1:true, 0:false): %d, length is %d\n", bst.root==NULL, bst.length);printf("midtravel: ");midtravel(bst.root);printf("\n");printf("pretravel: ");pretravel(bst.root);printf("\n");printf("posttravel: ");posttravel(bst.root);printf("\n");clear(&bst);printf("isempty(1:true, 0:false): %d, length is %d\n", bst.root==NULL, bst.length);return 0;
}/* subfunction */
LinkNode *createNode(int data) // create a node
{LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));if(node == NULL){perror("Memory allocation failed");exit(-1);}node->value = data;node->left = NULL;node->right = NULL;return node;
}void add(LinkBST *bst, int data) // add element
{// subfunction(recursion): add element to the binary search tree LinkNode *addNode(LinkNode *node, int data){if(node == NULL){LinkNode *newnode = createNode(data);node = newnode;bst->length++;return node;}if(data < node->value) node->left = addNode(node->left, data);else if(data > node->value) node->right = addNode(node->right, data);return node;}// root node receive the resultbst->root = addNode(bst->root, data);
}void delete(LinkBST *bst, int data) // delete element
{// subfunction(recursion): delete element from the binary search tree LinkNode *del(LinkNode *node){if(node->left == NULL){bst->length--;return node->right;}else if(node->right == NULL){bst->length--;return node->left;}else if(node->left && node->right){LinkNode *tmp = node, *cur = node->left;while(cur->right){tmp = cur;cur = cur->right;}node->value = cur->value;if(tmp != node) tmp->right = cur->left;else tmp->left = cur->left;bst->length--;return node;}}// subfunction: find delete node,return nodeLinkNode *delNode(LinkNode *node, int data){if(node == NULL) return node;if(data == node->value) node = del(node);else if(data < node->value) node->left = delNode(node->left, data);else if(data > node->value) node->right = delNode(node->right, data);return node;} // root node receive the resultbst->root = delNode(bst->root, data);
}void clear(LinkBST *bst) // clear the tree
{// function: free memory space on ecah nodevoid clearNode(LinkNode *node){if(node->left == NULL && node->right == NULL){free(node);node == NULL;return ;}if(node->left) clearNode(node->left);if(node->right) clearNode(node->right);}// if not empty tree,free memory space on each node,root is NULL and length is 0if(bst->root == NULL) return ;clearNode(bst->root);bst->root = NULL;bst->length = 0;
}void pretravel(LinkNode *node) // show element one by one,(root,left,right)
{if(node == NULL) return ;printf("%d ", node->value);pretravel(node->left);pretravel(node->right);
}void midtravel(LinkNode *node) // show element one by one,(left,root,right)
{if(node == NULL) return ;midtravel(node->left);printf("%d ", node->value);midtravel(node->right);
}void posttravel(LinkNode *node) // show element one by one,(left,right,root)
{if(node == NULL) return ;posttravel(node->left);posttravel(node->right);printf("%d ", node->value);
}int find(LinkNode *node, int data) // if find data,return 1(true),or return 0(false)
{if(node == NULL) return 0;if(data == node->value) return 1;if(data < node->value) find(node->left, data);else if(data > node->value) find(node->right, data);
}编译链接： gcc -o bst bst.c
执行可执行文件： ./bst
