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

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

  1
 / \
2   3

二叉搜索树：用于搜索。一棵二叉树，其中左子仅包含值小于父节点的节点，而右子仅包含值大于或等于父节点的节点。

  2
 / \
1   3

---

Binary Tree 是具有两个孩子（左孩子和右孩子）的特殊形式的树。它只是树结构中数据的简单表示

Binary Search Tree (BST) 是一种特殊类型的二叉树，它遵循以下条件：

左子节点小于其父节点右子节点大于其父节点

---

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

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

    5
   / \
  3   6 
 / \   \
1   4   9    

上面显示的树是二叉搜索树——“根”节点为 5，其左子树节点 (1, 3, 4) < 5，其右子树节点 (6, 9) > 5。递归地，每个子树也必须服从二叉搜索树约束：在 (1, 3, 4) 子树中，3 是根，1 < 3 和 4 > 3。

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

---

正如上面每个人都解释了二叉树和二叉搜索树之间的区别，我只是添加了如何测试给定的二叉树是否是二叉搜索树。

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);

}

希望它会帮助你。抱歉，如果我偏离了这个话题，因为我觉得这里值得一提。

---

二叉树代表一种数据结构，它由只能有两个子引用的节点组成。

另一方面，二叉搜索树 (BST) 是二叉树数据结构的一种特殊形式，其中每个节点都有一个可比较的值，较小值的子节点附加到左侧，较大值的子节点附加到右侧。

因此，所有 BST 都是二叉树，但只有一些二叉树可能也是 BST。通知 BST 是二叉树的一个子集。

因此，二叉树比二叉搜索树更像是一种通用的数据结构。而且您还必须通知二叉搜索树是一个排序树，而通用二叉树没有这样的规则集。

二叉树

Binary Tree 不是 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。

二叉树节点没有这样的规则。二叉树节点的唯一规则是有两个孩子，所以它自己解释为什么叫二叉树。

---

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

---

二叉树

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

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

https://i.stack.imgur.com/3xaMD.png

例如，在左边的树中，A 有 6 个孩子 {B,C,D,E,F,G}。可以转化为右边的二叉树。

https://i.stack.imgur.com/zmLGX.png

二进制搜索

二进制搜索是用于在节点链上查找特定项目的技术/算法。二进制搜索适用于已排序的数组。

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

https://i.stack.imgur.com/s0pFw.png

表示二分查找的树。这里要搜索的数组是[20, 30, 40, 50, 90, 100]，目标值为40。

https://i.stack.imgur.com/mFNZu.png

二叉搜索树

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

二叉搜索树和 B 树数据结构基于二叉搜索。

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

大小为 9、深度为 3 的二叉搜索树，根为 8。叶子没有画出来。

https://i.stack.imgur.com/Npp5D.png

最后是用于比较知名数据结构和应用算法的性能比较的绝佳模式：

https://i.stack.imgur.com/5wAZi.png

图片取自 Algorithms (4th Edition)

---

二叉搜索树：当对二叉树进行中序遍历时，你会得到插入项的排序值

二叉树：在任何类型的遍历中都找不到排序顺序

---

二叉树是一棵树，其子节点不超过两个。二叉搜索树遵循这样的不变性：左子节点的值应小于根节点的键，而右子节点的值应大于根节点的键。

---

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

以有序方式遍历树（即 Left Child --> Parent --> Right Child ），将遍历的节点数据存储在临时变量中让我们说 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;
}

保持温度变量在外面

---

当且仅当任何节点的最大子节点数为两个时，树才能称为二叉树。

当且仅当任何节点的最大子节点数为两个并且左子节点总是小于右子节点时，树才可以称为二叉搜索树。

---

在二叉搜索树中，所有节点都按特定顺序排列——根节点左侧的节点的值小于根节点的值，节点右侧的所有节点的值都大于根节点的值根。

---