二叉树和二叉搜索树的区别

Question

请问有人能用一个例子解释二叉树和二叉搜索树的区别吗？

- Neel

Answer 1

二叉树：每个节点最多有两个子节点的树

  1
 / \
2   3

---

二叉搜索树：用于查找。它是一棵二叉树，其中左子节点只包含值小于父节点的节点，右子节点则只包含值大于等于父节点的节点。

---

  2
 / \
1   3

- user541686

---

@pete：这是一个概念性的东西，你不一定会真正地创造出完全无限制的树。然而，有许多非搜索的二叉树在某些其他方面是特殊的，例如二叉堆。 - user541686

二叉树并不一定需要包含可比较的数据，许多（非搜索）二叉树被用于解析代数表达式。使用二叉树来编写中缀表达式解析器非常完美，只需将运算符作为节点，数字值作为叶子即可。 - JBoy

@JBoy：在这种情况下，它们不会是二叉树。（例如，一元运算符不能有两个子节点。）我真的想不出无限制的二叉树的实际用例，这就是为什么我发表了那个评论。 - user541686

太棒了，而且简单易懂。给你点赞，因为有视觉示例 :) - Andrei Konstantinov

@Vroomfondel：有趣。不幸的是，我对这些树一无所知，但我不认为它们被称为BSTs。如果您想了解更多信息，可以在CS.SE上提问，看看是否有人了解更多关于它们的知识。 - user541686

Answer 2

二叉树是一种具有两个孩子（左孩子和右孩子）的特殊树形结构。它简单地表示了数据在树形结构中的分布。

二叉搜索树（BST）是一种特殊类型的二叉树，遵循以下条件：

1. 左节点小于其父节点
2. 右节点大于其父节点

- Jayzcode

---

这些条件并不足够。整个左子树必须不包含任何键，只能比父节点的键更小；整个右子树必须包含比父节点更大的节点。 - user207421

@EJP，您能详细说明一下您的评论吗？您所说的整个子树是什么意思？您是指左侧子树中所有值都应小于根节点吗？右侧子树中所有值都应大于根节点的值吗？ - Asif Mushtaq

请点击第二个链接，阅读“验证”部分，就会明白了。 - Rob

Answer 3

二叉树由节点组成，每个节点包含一个“左”指针、一个“右”指针和一个数据元素。 “根”指针指向树中最顶部的节点。左右指针递归地指向两侧较小的“子树”。空指针表示没有元素的二叉树 - 空树。正式的递归定义是：二叉树要么为空（用null指针表示），要么由一个单独的节点组成，其中左右指针（递归定义在前面）分别指向二叉树。

二叉搜索树（BST）或“有序二叉树”是一种二叉树类型，其中节点按顺序排列：对于每个节点，其左子树中的所有元素都小于该节点（<），而其右子树中的所有元素都大于该节点（>）。

    5
   / \
  3   6 
 / \   \
1   4   9    

上面展示的树是一棵二叉搜索树——"根"节点是5，其左子树节点（1、3、4）< 5，右子树节点（6、9）> 5。递归地讲，每个子树都必须遵守二叉搜索树的约束条件：在（1、3、4）子树中，3是根节点，1<3且4>3。

注意问题中的确切措辞——“二叉搜索树”不同于“二叉树”。

- Emmanuel Oddy

---

@GabrielStaples 添加了树形结构。 - Gaurav Borole

Answer 4

正如其他人已经解释了二叉树和二叉搜索树之间的区别，我只是补充说明如何测试给定的二叉树是否为二叉搜索树。

boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max)
{

    if(node == null)
    {
        return true;
    }

    boolean left = isBinarySearchTree(node.getLeft(), min, node.getValue());
    boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

    return left && right && (node.getValue()<max) && (node.getValue()>=min);

}

希望这能对你有所帮助。如果我偏离了话题，很抱歉，但我觉得在这里提到这点是值得的。

- Trying

---

左子树或右子树可以为空。你的代码没有正确处理这种情况。 - user207421

@user207421 还有一些二叉搜索树不遵循本地排序标准，但仍然是二叉搜索树（具有最优性等）。 - Vroomfondel

Answer 5

二叉树是一种由节点组成的数据结构，每个节点只能有两个子节点。

二叉搜索树（BST）则是一种特殊形式的二叉树数据结构，其中每个节点都有一个可比较的值，较小值的子节点连接到左侧，较大值的子节点连接到右侧。

因此，所有的BST都是二叉树，但只有一些二叉树也是BST。请注意，BST是二叉树的子集。

因此，二叉树更像是一个通用的数据结构，而二叉搜索树是一个排序的树，对于通用的二叉树没有这样的规则。

非BST的二叉树

         5
       /   \
      /     \
     9       2
    / \     / \
  15   17  19  21

二叉搜索树（排序树）

二叉搜索树，也是一棵二叉树；

         50
       /    \
      /      \
     25      75
    /  \    /  \
  20    30 70   80

二叉搜索树节点属性

需要注意的是，对于BST中的任何一个父节点：

• 所有左节点的值都比父节点小。在上面的例子中，值为{20,25,30}的节点位于50的左侧分支（即左后代），小于50。

• 所有右节点的值都比父节点大。在上面的例子中，值为{70,75,80}的节点位于50的右侧分支（即右后代），大于50。

对于二叉树节点没有此规则。二叉树节点仅有的规则是具有两个孩子节点，因此自我解释为什么称为二叉。

- Levent Divilioglu

---

我们能实现简单的二叉树吗？是否有可用的实现？这个树的用途是什么？ - Asif Mushtaq

@UnKnown 你可以使用二叉搜索树进行排序和查找。你可以在这里找到二叉搜索树的实现：https://github.com/bzdgn/data-structures-in-java/blob/master/src/ds_010_trees/BinaryTree.java - Levent Divilioglu

我知道这个，但是是否存在简单树或简单二叉树？或者有没有简单二叉树的实现？ - Asif Mushtaq

没有必要使用它，但是您可以将任意的Node实例添加到根和子节点中。 - Levent Divilioglu

Answer 6

一棵二叉搜索树是一种特殊的二叉树，具有以下特性：对于任何节点n，n左子树中每个后代节点的值都小于n的值，而n右子树中每个后代节点的值都大于n的值。

- Kaushik Lele

Answer 7

二叉树

二叉树可以是任何具有2个子节点和1个父节点的东西。它可以实现为链表或数组，或使用您的自定义API。一旦您开始将更具体的规则添加到其中，它就变成了更加专业化的树。最常见的已知实现是在左侧添加较小的节点，并在右侧添加较大的节点。

例如，一个带有值为2的根节点、大小为9且高度为3的有标签二叉树。此树不平衡且未排序。https://en.wikipedia.org/wiki/Binary_tree

例如，在左侧的树中，A有6个子节点{B,C,D,E,F,G}。它可以转换为右侧的二叉树。

二分查找

二分查找是用于在节点链中查找特定项的技术/算法。二分查找适用于排序数组。

二分查找将目标值与数组的中间元素进行比较；如果它们不相等，则消除目标所在的半部分并继续在剩余的半部分上进行搜索，直到成功或剩余的半部分为空为止。https://en.wikipedia.org/wiki/Binary_search_algorithm

一棵代表二叉搜索的树。在此搜索的数组为 [20, 30, 40, 50, 90, 100]，目标值为 40。

二叉搜索树

这是二叉树的一种实现，专门用于搜索。

二叉搜索树和B树数据结构都基于二分查找。

二叉搜索树（BST），有时被称为有序或排序二叉树，是存储“项”（如数字、名称等）的数据结构的特定类型容器。 https://en.wikipedia.org/wiki/Binary_search_tree

大小为9、深度为3的二叉搜索树，根为8。叶子节点未绘制出来。

最后，展示了应用于知名数据结构和算法的性能比较的重要架构：

图片来源于 《算法（第4版）》

- Teoman shipahi

Answer 8

• 二叉搜索树: 当对二叉树进行中序遍历时，您会得到插入项的排序值
• 二叉树: 在任何遍历中都找不到排序顺序

- AlienOnEarth

---

不需要找到排序顺序。二叉搜索树也是一种二叉树，它们并不互斥。BST是BT的一个真子集。 - user207421

没错，如果你仔细阅读，这就是为什么在二叉树上进行中序遍历时，会有二叉搜索树的解释。 - AlienOnEarth

Answer 9

二叉树是一种子节点不超过两个的树结构。二叉搜索树遵循以下规则：左子节点的键值应小于根节点的键值，而右子节点的键值应大于根节点的键值。

- nana yaah

Answer 10

为了检查给定的二叉树是否是二叉搜索树，这里有一种替代方法。

以中序遍历方式（即左子树 -> 父节点 -> 右子树）遍历树， 将遍历的节点数据存储在一个临时变量中，比如说 temp，在存储到 temp 之前，检查当前节点的数据是否高于前一个节点的数据。 如果是，则直接跳出循环，说明该树不是二叉搜索树；反之则继续遍历至结束。

以下是 Java 的示例代码：

public static boolean isBinarySearchTree(Tree root)
{
    if(root==null)
        return false;

    isBinarySearchTree(root.left);
    if(tree.data<temp)
        return false;
    else
        temp=tree.data;
    isBinarySearchTree(root.right);
    return true;
}

将临时变量放在外部进行维护

- Neeraj Jain

---

任何一个子树都可能为空。你的算法没有正确处理这种情况。 - user207421