二叉排序树（二叉查找树）

二叉排序树（二叉查找树）的性质：

• 若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值。
• 若它的右子树不为空，则右子树上所有结点的值均大于它的根将诶点的值。
• 它的左、右子树也分别为二叉排序树。

对二叉排序树进行中序遍历时，变可得到一个有序的序列。

构建二叉排序树不是为了排序，而是为了查找，也有利于插入和删除的实现。

代码

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>typedef struct Node
{int data;struct Node *left, *right;
} Node;// returns true on success with ret set to found node.
// returns false on failure with ret set to last accessed node.
// parent passed is NULL at the first call.
bool
search_v2 (Node *tree, int key, Node *parent, Node **ret)
{if (tree == NULL){*ret = parent;return false;}if (key == tree->data){*ret = tree;return true;}else if (key < tree->data)return search_v2 (tree->left, key, tree, ret);elsereturn search_v2 (tree->right, key, tree, ret);}// Returns pointer to the searched node on success, or 0 on failure.
Node *
search (Node *tree, int key)
{if (tree == NULL)return NULL;if (key == tree->data)return tree;else if (key < tree->data)return search (tree->left, key);//search at left childelsereturn search (tree->right, key);//search at right child
}bool
insert_node (Node **ptree, int key)
{Node *result, *new_node;if (search_v2 (*ptree, key, NULL, &result) == false) //not found{new_node = malloc (sizeof (Node));*new_node = (Node){.data = key,.left = NULL,.right = NULL};if (result == NULL)*ptree = new_node; // insert as new rootelse if (key < result->data)result->left = new_node; //insert as lchildelseresult->right = new_node; //insert as rchildreturn true;}elsereturn false;//there is already such value, refuses to insert.
}bool
delete_node_impl (Node **ptree)
{Node *prev;if ( (*ptree)->right == NULL) //if right is NULL, reset it to its left child{prev = *ptree;*ptree = (*ptree)->left;free (prev);}else if ( (*ptree)->left == NULL) //if left is NULL, reset it to its right{prev = *ptree;*ptree = (*ptree)->right;free (prev);}else//both left and right are not NULL{prev = *ptree;Node *s = (*ptree)->left;while (s->right != NULL) //turn left, then turn to right for ever{prev = s;s = s->right;}//找到了左子树中的最大结点（直接前驱），这意味者它的right为NULL。(*ptree)->data = s->data;//s points to the direct predecessor of deleted nodeif (prev != *ptree) //如果直接前驱的父结点 ！= 被删除的treeprev->right = s->left; //reset right tree of prevelse //否则，说明tree的左子树没有右子树，直接替换左子树即可。prev->left = s->left; //reset left tree of prevfree (s);//释放被删除的结点——直接前驱。}return true;
}bool
delete_node (Node **ptree, int key)
{if (ptree == NULL)return false;else{if (key == (*ptree)->data)return delete_node_impl (ptree);else if (key < (*ptree)->data)return delete_node (& (*ptree)->left, key);elsereturn delete_node (& (*ptree)->right, key);}
}void
traverse_LDR (Node *tree)
{if (tree == NULL)return;traverse_LDR (tree->left);printf ("%d\n", tree->data);traverse_LDR (tree->right);
}int main (void)
{Node *tree = NULL;insert_node (&tree, 100);insert_node (&tree, 101);insert_node (&tree, 102);insert_node (&tree, 103);insert_node (&tree, 104);traverse_LDR (tree);}

#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <stdbool.h>typedef struct Node
{int data;struct Node *left;struct Node *right;
} Node;Node *
create_tree()
{return NULL;
}enum search_result
{NOT_FOUND,};// 成功返回true，同时ret保留找到的结点。
// 失败返回false，同时ret保留最后一个结点（用于插入）。
// parent是辅助参数，第一次传入时应为NULL
bool
search_v2 (Node *tree, int key, Node *parent, Node **result)
{if (tree == NULL){*result = parent;return false;}if (tree->data == key){*result = tree;return true;}if (key < tree->data)return search_v2 (tree->left, key, tree, result);elsereturn search_v2 (tree->right, key, tree, result);
}Node *
search (Node *tree, int key)
{Node *result;if (search_v2 (tree, key, NULL, &result))return result;return NULL;
}bool
insert_node (Node **ptree, int key)
{Node *result;if (search_v2 (*ptree, key, NULL, &result) == false){Node *new_node = malloc (sizeof (Node));*new_node = (Node){.data = key,.left = NULL,.right = NULL};if (result == NULL) //说明树为空，插入为根结点*ptree = new_node;else if (key < result->data)result->left = new_node;elseresult->right = new_node;return true;}elsereturn false;// 已经存在相同值，插入失败
}bool
delete_node_impl (Node **ptree)
{Node *prev;if ( (*ptree)->right == NULL) // 只有左子树，重设左子树即可{prev = *ptree;*ptree = (*ptree)->left;free (prev);}else if ( (*ptree)->left == NULL) //只 有右子树，重设右子树即可{prev = *ptree;*ptree = (*ptree)->right;free (prev);}else// 都不为空{prev = *ptree;Node *predecessor = (*ptree)->left;while (predecessor->right != NULL){prev = predecessor;predecessor = predecessor->right;}(*ptree)->data = predecessor->data;if (*ptree != prev)prev->right = predecessor->left;else(*ptree)->left = predecessor->left;}return true;
}bool
delete_node (Node **ptree, int key)
{if (*ptree == NULL)return false;else{if ( (*ptree)->data == key)return delete_node_impl (ptree);else if (key < (*ptree)->data)return delete_node (& (*ptree)->left, key);elsereturn delete_node (& (*ptree)->right, key);}
}void
traverse_LDR (Node *tree)
{if (tree == NULL)return;traverse_LDR (tree->left);printf ("%d\n", tree->data);traverse_LDR (tree->right);
}int main (void)
{Node *tree = NULL;insert_node (&tree, 100);insert_node (&tree, 101);insert_node (&tree, 102);insert_node (&tree, 103);insert_node (&tree, 104);delete_node (&tree, 100);delete_node (&tree, 101);delete_node (&tree, 102);delete_node (&tree, 103);delete_node (&tree, 104);traverse_LDR (tree);}

经测试没有内存泄露。

参考书籍：大话数据结构