二叉搜索树(BST)是一种数据结构，它与我们之前讲过的其他结构有很大的不同。与栈、队列和列表不同，BST的结构不是一条“直线”。BST中的每个节点都有一个左右子节点。
上面的BST是BST如何工作的一个经典例子。“10”是树中的第一个节点，然后将所有其他节点放入树中。我们今天要做一个不平衡搜索树，除了删除节点外，节点的位置不会改变。一个平衡的搜索树，我们今天不会细讲，它在树中移动节点来保持平衡。
BST有四种主要功能：
1.插入。由于BST的性质，插入功能将创建一个新的叶（树的底部节点）。
2.找到功能（Findmin，findmax，包含）。“查找”功能与插入非常相似，将在树上朝下，直到找到值。
3.删除。删除删除节点。这是BST中最复杂的功能，因为有三种不同的情况（我们将覆盖这些）。
4.打印。打印BSTs有三种方法，我们将在这篇文章中介绍。每个节点都以不同的顺序输出节点。
是什么让二进制搜索树如此有趣，即插入，查找和删除功能都具有o（log n）的平均复杂性。当调用这些函数时，每个迭代都会减少剩余的“n”值的数量，导致O（log n）复杂性。一个简单的例子是搜索，如果我们在上面的BST中搜索“14”，则第一个迭代将需要我们到11，从而删除BST的整个左半部分。
现在已经介绍了BST，让我们进入他们的实施。值得注意的是，我们的BST不会支持重复项，但这绝对是您可以添加的功能！我们不会转过主页和标题文件，大多数它们与堆栈和队列博客文章相同。在这里检查一下：头和主要。
1.插入
您可以看到有两个插入功能。第一个函数只是呼叫第二个功能。这似乎有点令人困惑，而是由于递归调用，这使得最容易调用主要。
在insert中，有四种情况。第一个是基本情况，我们创建一个新节点，将元素值赋给我们的条目，然后将左右节点赋给NULL。第二种情况和第三种情况是递归调用，这两种情况将元素往下移动。如果元素小于当前分支中的值，我们将它发送到左边，否则我们将发送到右边。这两种说法让bst变得有趣。其他数据结构的插入函数是线性的，但BST的插入有多个选项。
2.findMin, findMax和contains
这些功能都非常相似，但每个功能都有不同的目的。包含是一个布尔函数，如果找到该值，它会通过树返回“true”。findmin和findmax是必不可少的“镜像”功能。findmin转到每个分支的左侧节点，直到达到最后一个节点 - 这是最小的值 - 然后返回此节点。FINDMAX通过所有正确的节点进行，直到达到结尾，然后返回最大值节点。
3.删除
删除很容易是二进制搜索树最复杂的函数。删除有三个单独的案例。
第一个是要删除的节点没有孩子时。这是最简单的情况，其中我们只删除节点。
第二种情况是要删除的节点有一个子。如我们将要删除的节点的子节点分配给原始节点位置，然后删除旧节点，因此这种情况并不极难。最后一个情况很容易是最复杂的，当节点有两个孩子时。为了让我们确保我们的BST的完整性，我们必须替换要删除的节点，其中值不是二进制搜索树的工作原理。为我们这样做，我们需要选择合适的子女子的最小节点。这是唯一可以确保树的完整性未更改的节点。这是我们的findmin函数很有用的地方，我们在右侧节点上调用findmin，并将该值分配给要删除的节点。然后，我们“移动”我们发现的节点我们发现要删除的节点的位置，然后我们相应地更新树（不允许重复）。
4.打印功能
二进制搜索树可以用三种方式打印出：预订，邮政和inOrder。所有这些功能都有一个“cout”调用和两个递归调用，这基本上是打印功能的所有函数。
预订在调用节点 - >左侧和节点 - >右侧打印出节点的值。这打印出树的左侧，然后是树的右侧。
PostOrder输出node->左边和node->右边的值，然后输出节点的值。因为这是一个递归调用，它将打印出所有的叶节点，然后打印出分支。
InOrder相当简单。通过在左调用node->和右调用node->之间打印节点值，我们按顺序打印出树。
