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


当前回答

当且仅当任意节点的最大子节点数为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;
}

保持室外温度变量

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

  1
 / \
2   3

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

  2
 / \
1   3

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

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。

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

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

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

左子<=父<=右子

其实就是这么简单。