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

小开

最佳答案

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

  1
/ \
2   3

二叉搜索树:用于搜索。一种二叉树，其中左子结点包含只有节点，其值小于父结点，右子结点只有包含节点，其值大于或等于父结点。

  2
/ \
1   3

小开

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

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

上面显示的树是一个二叉搜索树——“根”节点是5，它的左子树节点(1,3,4)是<5，其右子树节点(6,9)为> 5。递归地，每个子树也必须遵守二叉搜索树的约束:在(1,3,4)子树中，3是根，1 <3、4 > 3.单击“确定”。

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

小开

二叉搜索树是一种特殊的二叉树，它表现出如下性质:对于任意节点n, n的左子树中每个后代节点的值都小于n，而右子树中每个后代节点的值都大于n。

小开

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

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


}

希望对你有所帮助。抱歉，如果我转移了话题，因为我觉得这里值得一提。

小开

二叉树 .是具有两个子树(左子和右子)的特殊形式。它只是用Tree结构

表示数据

< a href = " http://en.wikipedia.org/wiki/Binary_search_tree " >二叉搜索树(BST) < / >是一种特殊类型的二叉树，它满足以下条件:

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

小开

二叉树是一种子树的数目永远不超过两个。二叉搜索树遵循一个不变式，即左子节点的值应该小于根节点的键，而右子节点的值应该大于根节点的键。

小开

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

小开

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

在为了时尚手册中(即左子->父->右子)，将遍历的节点数据存储在临时变量中，例如临时，在存储到临时之前，检查当前节点的数据是否高于前一个。然后只是打破它出来，树不是二叉搜索树，否则遍历直到结束

下面是一个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;
}

保持室外温度变量

小开

二叉树代表由节点组成的数据结构，而只有可以有两个孩子引用。

另一方面，二叉搜索树 (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。

二叉树 Node没有这样的规则。二叉树节点的唯一规则是有两个子节点，所以它自我解释了为什么被称为二进制。

小开

二叉树

二叉树可以是任何东西，它有两个子树和一个父树。它可以实现为链表或数组，或与您的自定义API。一旦你开始向它添加更具体的规则，它就变得更专门的树。最常见的实现是，在左边添加较小的节点，在右边添加较大的节点。

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

例如，在左边的树中，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版)

小开

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

小开

当且仅当任意节点的最大子节点数为2时，树可以被称为二叉树。

当且仅当任意节点的最大子节点数为2且左子节点总是小于右子节点时，树可以被称为二叉搜索树。

小开

在二叉树中，每个节点有两个子节点，左节点和右节点。二叉搜索树是一种特殊的树，其中节点被排序，左节点比父节点小，左节点比父节点大。二叉树允许重复值，二叉搜索树不允许重复值，而且在二叉搜索树中执行任何类型的操作都比在二叉树中更快，因为BST排序

小开

二叉树是一种树，其中每个节点最多可以有2个子节点。

二叉搜索树是对它的进一步修改，赋予父结点和两个子结点一定的关系。因为，只有两个子结点，即左子结点和右子结点;关系式定义如下:

左子<=父<=右子

其实就是这么简单。