-2

如何从任何给定节点找到二叉搜索树的根？更具体地说，从任何给定节点遍历祖先时，我应该什么时候停止？java中有没有获取root的函数？请帮我。

4

3 回答 3

3

这是java中的二叉树节点表示

class Node{
    int data;
    Node leftChild;
    Node rightChild;
}

但是，如果我们遵循这种节点表示，那么就很难从叶节点遍历到它们的祖先。这种表示适用于与问题陈述一起给出对根节点的引用的问题。

为了从树中任意位置的节点开始遍历，我们必须在节点类中放置对父节点的引用。

class Node{
    int data;
    Node parent;
    Node leftChild;
    Node rightChild;
}

现在，如果您开始遍历，则必须在找到节点的空父节点时停止。

/* the logic for traversing */
Node tempRoot = given node;
while(true){
    if(null != tempRoot.parent){
        tempRoot = tempRoot.parent;

    }else{
        break;
    }
}
/* return value of tempRoot: this is your root */

[编辑：我省略了 getter 和 setter。虽然我不建议这样实现:)]

于 2013-06-16T12:45:07.407 回答
1

我假设您正在用 Java 或其他方式编写自己的 BST 实现？如果节点存储了对父节点的引用，最终您将在爬上树时遇到父节点为 null 的节点。这个节点通常应该是根。

如果您的节点没有存储此类引用，那么如果您只有一个节点，则无法到达根目录。许多实现缺少对父节点的引用，因为它可以节省内存并且可以在遍历树时使用堆栈来处理（用于深度优先遍历）。

但我不清楚你到底想做什么。为什么需要找到根节点？

于 2013-06-16T12:37:37.353 回答
1

If you have implemented your own BST, then you should have a data member Node root; in your BST class, you can access/find the root by simply accessing that data member from any method of BST class

于 2013-06-16T12:45:52.713 回答