本文共 2999 字，大约阅读时间需要 9 分钟。

二叉搜索树

• 左孩子小于根节点
• 右孩子大于根节点
  二叉排序树中序的结果是升序的

int arr[] = { 5, 3, 7, 1, 4, 6, 8, 0, 2, 9 };

typedef int Key;		typedef struct BSTreeNode	{		Key key;		struct BSTreeNode *left;		struct BSTreeNode *right;		}BSTreeNode;

查找

先判断根节点

递归查找

int BSTreeSearch(BSTreeNode *root, Key key)	{		if (root == NULL)		{			return -1; //-1表示没找到哦，0表示找到了		}		if (root->key == key)		{			return 0;		}		else if (root->key < key)		{			return BSTreeSearch(root->right, key);		}		else		{			return BSTreeSearch(root->left, key);		}	}

非递归查找

int BSTreeSearchLoop(BSTreeNode *root, Key key)	{		BSTreeNode *cur = root;		while (cur != NULL)		{			if (cur->key == key)			{				return 0;			}			else if (cur->key < key)			{				cur = cur->right;			}			else			{				cur = cur->left;			}		}		return -1;	}

插入

递归插入

BSTreeNode *CreateBSTreeNode(Key key){	BSTreeNode *node = (BSTreeNode *)malloc(sizeof(BSTreeNode));	node->key = key;	node->left = NULL;	node->right = NULL;	return node;}int BSTreeInsert(BSTreeNode **pproot, Key key){	if (*pproot == NULL)	{		*pproot = CreateBSTreeNode(key);		return 0;	}	if ((*pproot)->key == key)	{		return -1;	}	else if ((*pproot)->key < key)	{		return BSTreeInsert(&(*pproot)->right, key);	}	else	{		return BSTreeInsert(&(*pproot)->left, key);	}}

非递归插入

int BSTreeInsertLoop(BSTreeNode **pproot, Key key)	{		assert(pproot);		BSTreeNode *cur = *pproot;		BSTreeNode *parent = NULL;				while (cur != NULL)		{			if (cur->key == key)			{				return -1;			}			parent = cur;			if (cur->key < key)			{				cur = cur->right;			}			else			{				cur = cur->left;			}		}		BSTreeNode *node = CreateBSTreeNode(key);		if (parent == NULL)		{			*pproot = node;		}		else if (parent->key < key)		{			parent->right = node;		}		else if (parent->key > key)		{			parent->left = node;		}		return 1;	}

删除

删除将会分为8种情况：

int BSTreeRemove(BSTreeNode **pproot, Key key)	{		assert(pproot);		BSTreeNode *cur = *pproot;		BSTreeNode *parent = NULL;			while (cur != NULL)		{			if (cur->key == key)			{				if (cur->left == NULL)				{					if (parent == NULL)					{						*pproot = cur->right;					}					else if (cur->key < parent->key)					{						parent->left = cur->right;					}					else					{						parent->right = cur->right;					}					free(cur);					return 0;				}				else if (cur->right == NULL)				{					if (parent == NULL)					{						*pproot= cur->left;					}					else if (cur->key < parent->key)					{						parent->left = cur->left;					}					else					{						parent->right = cur->left;					}					free(cur);					return 0;				}				else				{					BSTreeNode *del = cur->right;					BSTreeNode *delParent = cur;					while (del->left != NULL)					{						delParent = del;						del = del->left;					}					cur->key = del->key;					if (delParent == cur)					{						delParent->right = del->right;					}					else					{						delParent->left = del->right;					}					free(del);					return 0;				}			}			parent = cur;			if (cur->key < key)			{				cur = cur->right;			}			else			{				cur = cur->left;			}		}		return -1;	}