【数据结构】（C语言）：二叉搜索树

二叉搜索树：

• 树不是线性的，是层级结构。
• 基本单位是节点，每个节点最多2个子节点。
• 有序。每个节点，其左子节点都比它小，其右子节点都比它大。
• 每个子树都是一个二叉搜索树。每个节点及其所有子节点形成子树。
• 可以是空树。

添加元素：从根节点开始，比对数值。若比它小，往左子树比对；若比它大，往右子树比对；直到找到为空，则为新元素的位置。

删除元素：

1. 若删除的节点为叶子节点（即无子节点），则直接删除。
2. 若删除的节点只有左子节点，则左子节点替代删除节点。
3. 若删除的节点只有右子节点，则右子节点替代删除节点。
4. 若删除的节点既有左子节点又有右子节点，则找到直接前驱（即删除节点的左子树中的最大值，即删除节点的左子节点的最右节点），直接前驱的值替代删除节点的值，删除直接前驱节点。

遍历元素：（可使用递归）

• 前序遍历（顺序：根节点、左子节点、右子节点）。
• 中序遍历（顺序：左子节点、根节点、右子节点）。
• 后序遍历（顺序：左子节点、右子节点、根节点）。

查找元素：从根节点开始，比对数值。若比它小，往左子树查找；若比它大，往右子树查找；直到找到该元素，则返回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 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 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");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 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