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

Question

任何人都可以用一个例子解释二叉树和二叉搜索树 之间的区别吗？

Answer 1

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

  1
 / \
2   3

二进制搜索树:用于搜索.一个二叉树,其中左子节点仅包含值小于父节点的节点,右子节点仅包含值大于或等于父节点的节点.

  2
 / \
1   3

Answer 2

二叉树是一种特殊形式的树,有两个孩子(左孩子和右孩子).它只是Tree结构中数据的表示

二进制搜索树(BST)是一种特殊类型的二叉树,遵循以下条件:

1. left子节点小于其父节点
2. 右子节点大于其父节点

Answer 3

二叉树由节点组成,其中每个节点包含"左"指针,"右"指针和数据元素."根"指针指向树中最顶层的节点.左右指针递归地指向任一侧较小的"子树".空指针表示没有元素的二叉树 - 空树.形式递归定义是:二叉树是空的(由空指针表示),或者由单个节点组成,其中左右指针(前面的递归定义)每个都指向二叉树.

二叉搜索树(BST)或"有序二叉树"是一种二叉树,其中节点按顺序排列:对于每个节点,其左子树中的所有元素都少于节点(<),以及所有元素在其右子树中大于节点(>).

    5
   / \
  3   6 
 / \   \
1   4   9    

上面显示的树是二叉搜索树 - "根"节点是5,其左子树节点(1,3,4)是<5,其右子树节点(6,9)是> 5.递归地,每个子树还必须服从二元搜索树约束:在(1,3,4)子树中,3是根,1 <3和4> 3.

注意问题中的确切措辞 - "二叉搜索树"与"二叉树"不同.

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

}

希望它会对你有所帮助.对不起,如果我偏离主题,因为我觉得这里值得一提.

Answer 5

二叉搜索树是一种特殊的二叉树,它具有以下属性:对于任何节点n,n的左子树中的每个后代节点的值小于n的值,并且右子树中的每个后代节点的值是大于n的值.

Answer 6

二叉树代表一个数据结构,它是由节点,可以只拥有两个孩子的引用.

另一方面,二进制搜索树(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.

二叉树节点没有这样的规则.二元树节点的唯一规则是有两个孩子,所以它自己解释为什么称为二进制.

Answer 7

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

Answer 8

• 二叉搜索树：当在二叉树上进行中序遍历时，你会得到插入项的排序值
• 二叉树：在任何类型的遍历中都找不到排序顺序

Answer 9

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

以中序方式遍历树（即左子节点 --> 父节点 --> 右子节点），将遍历的节点数据存储在临时变量中，比如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;
}

在外面维护临时变量

Answer 10

二叉树

二叉树可以是任何有2个孩子和1个父母的东西.它可以实现为链接列表或数组,也可以实现自定义API.一旦开始向其中添加更多特定规则,它就会变得更加专业化.最常见的已知实现是,在左侧添加较小的节点,在右侧添加较大的节点.

例如,大小为9且高度为3的带标签的二叉树,其根节点的值为2.树是不平衡的,未进行排序. 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版)