java - 在二叉树中查找父节点到子节点

Question

我试图创建一个函数来获取子节点和二叉树并返回给定子节点的父节点。如果给定的子节点是根，它应该返回 null。这就是我想要做的:

//input : The function gets a binary tree and a child node
//output : The function returns the parent of a given child of the tree, if the given child is the root
//then it will return null
public static BinTreeNode<Character> Parent(BinTreeNode<Character> bt, BinTreeNode<Character> child){
    if(bt==null){
        return bt;
    }
    else{
        if(bt.hasLeft()&&(bt.hasRight())){
            if((bt.getLeft().getValue()==child.getValue())||(bt.getRight().getValue()==child.getValue())){
                return bt;
            }
            else{
                Parent(bt.getLeft(),child);
                Parent(bt.getRight(),child);

            }
        }
        if(bt.hasLeft()){
            if(bt.getLeft().getValue()==child.getValue()){
                return bt;
            }
            else{
                return Parent(bt.getLeft(),child);
            }
        }
        if(bt.hasRight()){
            if(bt.getRight().getValue()==child.getValue()){
                return bt;
            }
            else{
                return Parent(bt.getRight(),child);
            }
        }
    }
    return null;
}

出于某种原因，它一直返回 null，在调试之后我看到当它到达第一个条件时它检查它是否等于但是然后而不是继续递归到其他条件和我告诉它做的只是盯着底部的 return null 看，我不知道为什么？我将非常感谢我对 Java 的任何帮助。

Answer 1

返回前需要遍历树。

您的实现只是向左走然后返回 null(可能您的 child 在右边)...

尝试这样的事情:

public static BinTreeNode<Character> getParent(BinTreeNode<Character> 
bt, BinTreeNode<Character> child){
    if(bt==null){
        return bt;
    }
    BinTreeNode<Character> left = null;
    BinTreeNode<Character> right = null;
    if(bt.hasLeft()){
        if(bt.getLeft().equals(child))
            return bt;
        left = getParent(bt.getLeft(),child);
    }
    if(left == null){
        if(bt.hasRight()) {
            if(bt.getRight().equals(child))
                return bt;
            right = getParent(bt.getRight(),child);
        }
    } else {
        return left;
    }
    return right;
}

这里我们实现了深度优先搜索。