标签: binary-tree

任何人都可以用一个例子解释二叉树和二叉搜索树 之间的区别吗？

我想知道二叉树的特定应用是什么.你能举一些真实的例子吗？

我最近遇到了称为跳过列表的数据结构.它似乎与二叉搜索树具有非常相似的行为.

为什么你想在二叉搜索树上使用跳过列表？

这里的二叉树可能不一定是二进制搜索树.
结构可以视为 -

struct node {
    int data;
    struct node *left;
    struct node *right;
};

我可以和朋友一起解决的最大解决方案就是这种 -
考虑这个二叉树:

二叉树http://lcm.csa.iisc.ernet.in/dsa/img151.gif

顺序遍历产量 - 8,4,9,2,5,1,6,3,7

后序遍历产量 - 8,9,4,5,2,6,7,3,1

因此,例如,如果我们想要找到节点8和5的共同祖先,那么我们在顺序树遍历中创建8到5之间的所有节点的列表,在这种情况下恰好是[4,9] ,2].然后我们检查此列表中的哪个节点在后序遍历中最后出现,即2.因此,8和5的共同祖先是2.

这个算法的复杂性,我相信是O(n)(O(n)对于顺序/后序遍历,其余的步骤再次是O(n),因为它们只不过是数组中的简单迭代).但这很有可能是错误的.:-)

但这是一个非常粗略的方法,我不确定它是否会因某些情况而崩溃.这个问题还有其他(可能是更优的)解决方案吗？

堆和BST有什么区别？

何时使用堆以及何时使用BST？

如果你想以排序的方式获取元素,BST是否优于堆？

如何在Java中打印二叉树,以便输出如下:

   4 
  / \ 
 2   5 

我的节点:

public class Node<A extends Comparable> {
    Node<A> left, right;
    A data;

    public Node(A data){
        this.data = data;
    }
}

我正在尝试找到二叉搜索树的定义,并且我一直在寻找不同的定义.

有人说,对于任何给定的子树,左子键小于或等于根.

有人说,对于任何给定的子树,右子键大于或等于根.

我的旧大学数据结构书中说"每个元素都有一个键,没有两个元素具有相同的键."

是否存在bst的通用定义？特别是关于如何处理具有相同密钥的多个实例的树.

编辑:也许我不清楚,我看到的定义是

1)左<= root <右

2)左<root <=右

3)左<root <右,这样就不存在重复的密钥.

这些学年已经有一段时间了.在医院找到了IT专家的工作.现在试着去做一些实际的编程.我现在正在研究二叉树,我想知道确定树是否高度平衡的最佳方法是什么.

我在考虑这个问题:

public boolean isBalanced(Node root){
    if(root==null){
        return true;  //tree is empty
    }
    else{
        int lh = root.left.height();
        int rh = root.right.height();
        if(lh - rh > 1 || rh - lh > 1){
            return false;
        }
    }
    return true;
}

这是一个很好的实现吗？还是我错过了什么？

我需要在二进制搜索树中找到第k个最小元素,而不使用任何静态/全局变量.如何有效地实现它？我在脑海中的解决方案是在O(n)中进行操作,这是最糟糕的情况,因为我计划对整个树进行顺序遍历.但在内心深处,我觉得我没有在这里使用BST属性.我的假设解决方案是正确的还是有更好的解决方案？

有人可以帮我理解下面的Morris inorder树遍历算法而不使用堆栈或递归吗？我试图了解它是如何工作的,但它只是逃避了我.

 1. Initialize current as root
 2. While current is not NULL
  If current does not have left child     
   a. Print current’s data
   b. Go to the right, i.e., current = current->right
  Else
   a. In current's left subtree, make current the right child of the rightmost node
   b. Go to this left child, i.e., current = current->left

我理解的树被修改的方式,将current node在作出right child的的max node中right subtree和使用该财产序遍历.但除此之外,我迷失了.

编辑:找到这个附带的c ++代码.我很难理解修改后树的恢复方式.神奇在于else子句,一旦修改了正确的叶子就会被击中.请参阅代码了解详情:

/* Function to traverse binary …