如何简单实现并分析二叉搜索树的运行流程？

本文共计3043个文字，预计阅读时间需要13分钟。

目录+二叉搜索树+二叉搜索树的重要操作+二叉搜索树实现（key模型）+二叉搜索树的应用+二叉搜索树实现（key/value模型）+二叉搜索树+二叉搜索树又称二叉排序树。它可能是一个空树。

目录

• 二叉搜索树
• 二叉搜索树的重要操作
• 二叉搜索树实现(key模型)
• 二叉搜索树的应用
• 二叉搜索树的实现(key/value模型)

二叉搜索树

二叉搜索树又被称为二叉排序树。它可以是一个空树，如果不是空树则满足下列性质：

1、如果它的左子树不为空，那么左子树上的所有节点都小于根。

2、如果它的右子树不为空，那么右子树上的所有节点都大于根

3、它的左子树、右子树也是二叉搜索树。

二叉搜索树的重要操作

二叉搜索树的插入

1、如果树为空，则直接插入

2、如果树不为空，则找到对应的位置插入。

查找办法：

根据二叉搜索树的性质，

1、如果给出的关键码比当前节点的关键码小，则在当前节点的左子树中找位置

2、如果给出的关键码比当前节点的关键码大，则在当前节点的右子树中找位置

如此反复循环……，直到找到一个空的位置插入。

二叉搜索树的删除

删除分为三种情况：

• 情况一：要删除的节点左孩子为空
• 情况二：要删除的节点左孩子不为空，右孩子为空
• 情况三：要删除的节点既有左孩子也有右孩子。