二叉树 FindParent 方法似乎不起作用

Question

这是我的 BNode class

class BNode
{
    public int number;
    public BNode left;
    public BNode right;
    public BNode(int number)
    {
        this.number = number;
    }
}

这是我在 BTree 中实现的 FindParent 方法 class

 public BNode FindParent(BNode BNode, BNode searchNode)
    {
        if (searchNode.left == BNode || searchNode.right == BNode)
        {
            return searchNode;
        }
        if (searchNode.left != null)
        {
            return (FindParent(BNode, searchNode.left));
        }
        if (searchNode.right != null)
        {
            return (FindParent(BNode, searchNode.right));
        }
        return null;
    }

我是这样称呼它的

    BNode bnodeFound = btree.Find(18);
    BNode bparent = btree.FindParent(bnodeFound, btree.rootNode);

它 returns 始终为空，除非数字是树根的第一个根。我还通过调试发现它到达最左边的根，检查它是否没有右根，然后 returns 为空。试图弄清楚这一点，但没有成功。我用类似的方法在树中找到一个数字，这对找到 18 很有效。

Answer 1

当你每次为左节点递归调用FindParent()时（当它不为空时），你直接returning它，这意味着右节点的FindParent()永远不会被调用。

// Assume we run this for the root node
if (searchNode.left != null)
{
    // If left node is not null, then it tries to find in left subtree only
    // Since it returns directly, whether found or not-found it WILL NOT
    // search in right sub-tree
    return (FindParent(BNode, searchNode.left));
}

// Unreachable code if left is not NULL
if (searchNode.right != null)
{
    return (FindParent(BNode, searchNode.right));
}

要修复，您可以删除 return 语句，然后检查是否仍未找到它。

if (searchNode.left != null)
{
    var found = (FindParent(BNode, searchNode.left));
    // Return if found, else continue to check in right
    if (found != null) return found;
}

// Checks in right sub-tree if not found in left subtree
if (searchNode.right != null)
{
    // While checking in right sub-tree, then return irrespective of whether
    // it was found or not found, since there aren't any more places to check
    return (FindParent(BNode, searchNode.right));
}

二叉树 FindParent 方法似乎不起作用

Binary trees FindParent method doesn't seem to work

c#

binary-tree

parent