有人能举例说明二叉树和二叉搜索树的区别吗?
当前回答
A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.
二叉搜索树(BST)或“有序二叉树”是一种二叉树,其中节点是按顺序排列的:对于每个节点,其左子树中的所有元素都小于该节点(<),而其右子树中的所有元素都大于该节点(>)。
5
/ \
3 6
/ \ \
1 4 9
上面所示的树是一棵二叉搜索树——“根”节点为5,其左子树节点(1,3,4)< 5,右子树节点(6,9)为> 5。递归地,每个子树也必须服从二叉搜索树约束:在(1,3,4)子树中,3是根,1 < 3和4 > 3。
注意问题中的确切措辞——“二叉搜索树”不同于“二叉树”。
其他回答
二叉树
二叉树可以是任何有两个子结点和一个父结点的树。它可以实现为链表或数组,或与您的自定义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版)》
二叉树是一种子树的数目永远不超过两个。二叉搜索树遵循一个不变式,即左子节点的值应该小于根节点的键,而右子节点的值应该大于根节点的键。
当且仅当任意节点的最大子节点数为2时,树可以被称为二叉树。
当且仅当任意节点的最大子节点数为2且左子节点总是小于右子节点时,树可以被称为二叉搜索树。
正如上面每个人都解释了二叉树和二叉搜索树的区别,我只是补充如何测试给定的二叉树是否是二叉搜索树。
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);
}
希望对你有所帮助。抱歉,如果我转移了话题,因为我觉得这里值得一提。
二叉搜索树是一种特殊的二叉树,它表现出如下性质:对于任意节点n, n的左子树中每个后代节点的值都小于n,而右子树中每个后代节点的值都大于n。