首页 文章

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

提问于
浏览
296

任何人都可以用一个例子解释 binary treebinary search tree 之间的区别吗?

11 回答

  • 4

    Binary Tree 代表 data structure ,它由 nodes 组成,可以 only 具有 two children 引用 .

    另一方面, Binary Search TreeBST )是 Binary Tree 数据结构的一种特殊形式,其中每个 node 具有可比较的值,并且附加到左侧的较小值子项和附加到右侧的较大值子项 .

    因此,所有 BST 都是 Binary Tree 但是只有一些 Binary Tree 也可能是 BST . 通知 BSTBinary Tree 的子集 .

    所以, Binary Tree 更像是一般的数据结构而不是 Binary Search Tree . 而且你必须通知 Binary Search Treesorted 树,而通用 Binary Tree 没有这样的规则 .

    二叉树

    A Binary Tree ,这是 not a BST ;

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

    二叉搜索树(已排序树)

    A Binary Search Tree 也是 Binary Tree ;

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

    二进制搜索树节点属性

    同时通知 BST 中的任何 parent node ;

    • 所有左节点的值都小于父节点的值 . 在上面的示例中,值为{20,25,30}的节点( all located on the leftleft descendants )为50)小于50 .

    • 所有正确的节点都具有比父节点的值更大的值 . 在上面的示例中,值为{70,75,80}且 all located on the rightright descendants )为50的节点大于50 .

    Binary Tree Node没有这样的规则 . Binary Tree Node的唯一规则是有两个孩子,所以它自我解释为什么称为二进制 .

  • 1
    • 二进制搜索树:当在二叉树上进行顺序遍历时,您将获得插入项的排序值

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

  • 34

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

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

    • 左子节点小于其父节点

    • 右子节点大于其父节点

  • 10

    二叉树是一棵树,其子节点不超过两个 . 二元搜索树遵循不变量,即左子节点的值应小于根节点的键,而右子节点的值应大于根节点的键 .

  • 13

    Binary tree

    二叉树可以是 anything ,其中有2个子节点和1个父节点 . 它可以实现为链接列表或数组,也可以实现自定义API . 一旦您开始向其中添加更多特定规则,它就变得更加明显了 specialized tree . 最常见的已知实现是,在左侧添加较小的节点,在右侧添加较大的节点 .

    例如,标记为二进制树,大小为9,高度为3,根节点的值为2.树为 unbalanced and not sorted . https://en.wikipedia.org/wiki/Binary_tree

    enter image description here

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

    enter image description here

    Binary Search

    二进制搜索是用于在节点链上查找特定项的技术/算法 . Binary search works on sorted arrays .

    二进制搜索将目标值与数组的 middle element 进行比较;如果它们不相等,则目标不能说谎的一半被消除,并且继续搜索剩下的一半,直到它成功或剩下的一半是空的 . https://en.wikipedia.org/wiki/Binary_search_algorithm

    enter image description here

    代表 binary search 的树 . 这里搜索的数组是[20,30,40,50,90,100],目标值是40 .

    enter image description here

    Binary search tree

    这是二叉树的实现之一 . 这是专门为 searching .

    二进制搜索树和B树数据结构基于 binary search .

    二进制搜索树(BST),有时称为有序或有序二进制树,是 particular type of container :在内存中存储"items"(例如数字,名称等)的数据结构 . https://en.wikipedia.org/wiki/Binary_search_tree

    大小为9且深度为3的二叉搜索树,在根处为8 . 叶子没有绘制 .

    enter image description here

    最后,应用了众所周知的数据结构和算法的性能比较的伟大模式:

    enter image description here

    图片取自Algorithms (4th Edition)

  • 10

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

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

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

  • 3

    要检查给定二进制树是否是二进制搜索树这里是一种替代方法 .

    Inorder Fashion 中的遍历树(即Left Child - > Parent - > Right Child),将临时变量中的遍历节点数据存储在 temp 中,就在存储到 temp 之前,检查当前Node的数据是否高于之前的Node . 然后只是 break 它出来,树不是二进制搜索树其他遍历直到结束 .

    下边是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;
    }
    

    保持外部的临时变量

  • 54

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

    A binary search tree (BST)或"ordered binary tree"是一种二叉树,其中节点按顺序排列:对于每个节点,其左子树中的所有元素都少于节点(<),并且其右子树中的所有元素都大于节点(>) .

    5
       / \
      3   6 
     / \   \
    1   4   9
    

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

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

  • 521

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

  • 4

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

    1
     / \
    2   3
    

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

    2
     / \
    1   3
    
  • 5

    在二进制搜索树中,所有节点按特定顺序排列 - 根节点左侧的节点的值小于其根节点,节点右侧的所有节点的值都大于根 .

相关问题