有人能举例说明二叉树和二叉搜索树的区别吗?
当前回答
在二叉树中,每个节点有两个子节点:左节点和右节点。 二叉搜索树是一种特殊的树,其中节点被排序,左节点比父节点小,左节点比父节点大。 二叉树允许重复值,二叉搜索树不允许重复值,而且在二叉搜索树中执行任何类型的操作都比在二叉树中更快,因为BST是排序的
其他回答
二叉树:每个节点最多有两个叶的树
1
/ \
2 3
二叉搜索树:用于搜索。二叉树,其中左子节点只包含值小于父节点的节点,而右子节点只包含值大于或等于父节点的节点。
2
/ \
1 3
二叉搜索树是一种特殊的二叉树,它表现出如下性质:对于任意节点n, n的左子树中每个后代节点的值都小于n,而右子树中每个后代节点的值都大于n。
二叉搜索树:当对二叉树进行序遍历时,您将得到插入项的排序值 二叉树:在任何遍历中都没有找到排序的顺序
二叉树表示一种数据结构,它由只能有两个子引用的节点组成。
另一方面,二叉搜索树(BST)是一种特殊形式的二叉树数据结构,其中每个节点都有一个可比较的值,较小的值子连接到左边,较大的值子连接到右边。
因此,所有的BST都是二叉树,但只有一些二叉树也是BST。通知BST是二叉树的一个子集。
因此,二叉树比二叉搜索树更像是一种通用的数据结构。你还需要知道二叉搜索树是一棵排序树而一般的二叉树没有这样的规则。
二叉树
二叉树不是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。
二叉树节点没有这样的规则。二叉树节点的唯一规则是有两个子结点,所以它自己解释了为什么叫二叉树。
二叉树是一种子树的数目永远不超过两个。二叉搜索树遵循一个不变式,即左子节点的值应该小于根节点的键,而右子节点的值应该大于根节点的键。
推荐文章
- HyperLogLog算法是如何工作的?
- 二叉搜索树的定义中允许重复的键吗?
- 如何有效地清除std::queue ?
- 非递归深度优先搜索算法
- 如何在Java中打印二叉树图?
- 堆与二叉搜索树(BST)
- 多维数组如何在内存中格式化?
- “冰冻词典”是什么?
- 在javascript中从平面数组构建树数组
- 为什么我们使用数组而不是其他数据结构?
- 在Java中从HashMap获取键
- 数组与链表
- set()是如何实现的?
- .Net数据结构:ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary—速度,内存,以及何时使用每个?
- 为什么std::map被实现为红黑树?