有人能举例说明二叉树和二叉搜索树的区别吗?
当前回答
二叉搜索树:当对二叉树进行序遍历时,您将得到插入项的排序值 二叉树:在任何遍历中都没有找到排序的顺序
其他回答
在二叉搜索树中,所有节点都按照特定的顺序排列——根节点左侧的节点的值小于根节点,节点右侧的所有节点的值大于根节点的值。
当且仅当任意节点的最大子节点数为2时,树可以被称为二叉树。
当且仅当任意节点的最大子节点数为2且左子节点总是小于右子节点时,树可以被称为二叉搜索树。
二叉搜索树:当对二叉树进行序遍历时,您将得到插入项的排序值 二叉树:在任何遍历中都没有找到排序的顺序
要检查给定的二叉树是否是二叉搜索树,这里有一个替代方法。
按顺序遍历树(即左子->父->右子), 在临时变量中存储遍历的节点数据,比如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;
}
保持室外温度变量
二叉树
二叉树可以是任何有两个子结点和一个父结点的树。它可以实现为链表或数组,或与您的自定义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版)》