在二叉树中查找节点的父节点

Question

我正在尝试编写一个查找给定节点的父节点的方法。以下是我的方法。
我创建了一个名为r的BinaryNode对象，最初指向根节点。

    public BinaryNode r=root;
    public BinaryNode parent(BinaryNode p){
    BinaryNode findParent=p;        
        if (isRoot(findParent) || r==null){
                return null;
        }
        else{
            if(r.left==findParent || r.right==findParent)
                return r;
            else{
                if (r.element<findParent.element)
                    return parent(r.right);
                else
                    return parent(r.left);
            }
        }
    }  

这段代码无法正常工作。我认为这是因为r是一个空对象。因为当我执行

if (isRoot(findParent) || r==null){
                System.out.println(r==null);
                return null;}  

r==null 的结果是 true。这是为什么呢？因为我已经插入了节点。

public static void main (String args[]){
        BinaryTree t=new BinaryTree();
        t.insert(5);
        t.insert(t.root,4);
        t.insert(t.root,6);
        t.insert(t.root,60);
        t.insert(t.root,25);
        t.insert(t.root,10);  

并且根节点不为空。
请问有人能指出为什么会发生这种情况，以及我尝试查找父节点的逻辑是否正确。

- sam_rox

---

你如何调用查找父级方法？你提供哪些参数？ - wastl

@wastl：findParent不是一个方法。它是一个二叉节点，用于存储我们需要查找父节点的节点。 - sam_rox

抱歉，我是指父节点(BinaryNode)的方法。 - wastl

@wastl：如果我想找到位于根节点左侧的节点的父节点，可以调用方法 parent(root.left)。 - sam_rox

你检查过isRoot(findParent)是否为true了吗？ - wastl

如果我调用 parent(root.left) 方法，isRoot() 的评估结果为 false，这是正确的，因为它不是根节点。 - sam_rox

Answer 1

问题在于你必须跟踪当前节点，同时保持要查找父节点的节点。就我了解你的代码而言，你保留了变量，但从未更改过它。

我建议使用一个辅助函数。它应该像这样：

public BinaryNode parent(BinaryNode p){
    parentHelper(root,p)
}
private BinaryNode parentHelper(BinaryNode currentRoot, BinaryNode p) {        
    if (isRoot(p) || currentRoot==null){
            return null;
    }
    else{
        if(currentRoot.left==p || currentRoot.right==p)
            return currentRoot;
        else {
            if (currentRoot.element<p.element) {
                return parentHelper(currentRoot.right,p);
            }
            else {
                return parentHelper(currentRoot.left,p);
            }
        }
    }
}  

- wastl

---

感谢您提供的答案。我意识到我从未更改当前变量，并找到了一种我认为可以解决这个问题的方法。在开始时，我尝试将根节点获取到变量r中。为此，我在parent()方法之外使用了public BinaryNode r=root;。然后为了检查，我执行了以下操作：public BinaryNode parent(BinaryNode p){System.out.println("r"+r.element);}，结果出现了空指针异常。 - sam_rox

这意味着r是一个空对象，所以if (isRoot(findParent) || r==null){总是被评估，并且在那里返回false，其余的代码甚至没有运行。为什么r变成了一个空对象。这是我的二叉树实现。public class BinaryTree { private BinaryNode root; public BinaryTree(){ root= null;}BinaryTree(int nodeValue){ root=new BinaryNode(nodeValue);}我将元素插入其中t.insert(5); t.insert(t.root,4); - sam_rox

你的代码已经可以运行了，我认为行 return parent(currentRoot.right,p); 应该改为 return parentHelper(currentRoot.right,p);。 - sam_rox

Answer 2

我将值与值进行比较，因为我没有定义节点比较的方式。

    public static Node FindParent(Node root, Node node)
    {
        if (root == null || node == null)
        {
            return null;
        }
        else if ( (root.Right != null && root.Right.Value == node.Value) || (root.Left != null && root.Left.Value == node.Value))
        {
            return root;
        }
        else
        {
            Node found = FindParent(root.Right, node);
            if (found == null)
            {
                found = FindParent(root.Left, node);
            }
            return found;
        }
    }

- aerin

Answer 3

使用两个参数：一个用于当前节点，另一个用于被搜索的节点。

- Peter Zeller

---

虽然这是正确的，但这并不说明 OP 的代码出了什么问题以及为什么 OP 应该这样做。添加这些内容无疑会使回答更好。 - HelloWorld123456789

嗯，这个问题看起来像是一道作业题，所以我不想给出太多提示 ;) - Peter Zeller

我认为这篇文章作为答案来说太短了（无论是长度还是内容）。 - HelloWorld123456789

@peq：我认为r充当了一个变量，负责处理当前节点。 - sam_rox

@peq：这不是一项作业任务。我正在学习数据结构，其中包括树。我只是尝试编写一个查找父节点的方法，以帮助自己学习它。 - sam_rox

Answer 4

这里是使用栈数据结构查找父节点的代码。

Stack<TreeNode> parentStack = new Stack<TreeNode>();

public static void inOrderTraversal(TreeNode root){
            if(root != null){
                if(parentStack.size()==0){
                    parentStack.push(root);
                }
                if(root.getLeftChild()!=null){
                    parentStack.push(root); 
                    inOrderTraversal(root.getLeftChild());  
                }
                parent = parentStack.pop();
                System.out.println(root.getNodeValue()+"'s parent is "+parent.getNodeValue());
                if(root.getRightChild()!=null){
                    parentStack.push(root);
                    inOrderTraversal(root.getRightChild());
                }
            }
            else{
                if(root==null){System.err.println("Can't process a empty root tree");}
            }
        }

- Puneeth Reddy V

Answer 5

我喜欢将尽可能多的工作委托给较低级别的组件，例如节点类。关于查找节点的父级，这是我的做法...

template <typename T>
Node<T>* Node<T>::parent (const Node<T>* node) 
{
    if (node)
    {
        if (*node < *this)
        {
            if (left && (*node < *left))
                return left->parent (node);
            return this;
        }
        if (*node > *this)
        {
            if (right && (*right > *node))
                return right->parent (node);
            return this;
        }
    }
    return nullptr;
}

- Kaal