有人能举例说明二叉树和二叉搜索树的区别吗?


当前回答

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

  1
 / \
2   3

二叉搜索树:用于搜索。二叉树,其中左子节点只包含值小于父节点的节点,而右子节点只包含值大于或等于父节点的节点。

  2
 / \
1   3

其他回答

二叉树是一种树,其中每个节点最多可以有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。

二叉树表示一种数据结构,它由只能有两个子引用的节点组成。

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

二叉树节点没有这样的规则。二叉树节点的唯一规则是有两个子结点,所以它自己解释了为什么叫二叉树。

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