如何在递归的先序遍历中找到下一个节点

Question

我想编写一个函数，它接受一棵树的节点作为参数。该函数应返回在preOrder中取出节点后访问的下一个节点。 我写了这段代码： （此代码搜索左子节点并返回它。如果temp没有左子节点但有右子节点，则此函数返回右子节点。但是，如果该节点是叶子节点且没有子节点，则获取父节点，直到获得具有右子节点的节点为止。）

    public Node fineNextPreOrder(Node temp)
    {
    if(temp.left!=null)
        return temp.left;
    else if((temp.left==null)&&(temp.right!=null))
        return temp.right;
    else if((temp.left==null)&&(temp.right==null))
    {
        while((temp!=root)&&(!((temp.parent.left!=null)&&(temp.parent.left==temp)&&(temp.parent.right!=null))))
            temp = temp.parent;
        if(temp != root)
            return temp.parent.right;
    }

        return null;

}

它可以正常工作，但我想让它递归。

有人能帮助我吗？

感谢您的关注和支持。

- Linda

---

不，这是preOrder（先序遍历）。例如，你应该在preOrder遍历中找到跟节点后面的节点，然后你应该检查根节点是否有左子节点，接下来的节点就是root.left，... - Linda

在前序遍历中，首先检查父节点。 - Hunter McMillen

是的，正如我在那个评论和@HunterMcMillen的代码中解释的那样。 - Linda

Answer 1

public Node preOrderMod(Node temp)
{
    if (temp != null)
    {
        if (temp.left != null)
            return temp.left;

        if (temp.right != null)
            return temp.right;

        return mod(temp.parent);
    }

    return null;
}

private Node mod(Node temp)
{
    if (temp != null && temp != root)
    {
       if (temp.parent.left == temp && temp.parent.right != null)
          return temp.parent.right;

       return mod(temp.parent);
    }

    return null;
}

参考：

预订购：根 左 右
中序遍历：左 根 右
后序遍历：左 右 根

- Steve P.

---

很遗憾，它不起作用。如果我们有一个右子叶，上面的代码将返回该叶子本身。 - Linda

@Steve-p 不，它应该搜索具有未访问的右子节点的父节点。 - user2494741

@SteveP。它应该搜索具有未访问的右子节点的父节点。让我澄清我的问题：请想象我们有一棵树，我们想要按preOrder遍历它。因此，我想编写一个函数，它接受树的节点并返回应该在preOrder中确切访问的下一个节点。 - Linda

@SteveP。你写的这段代码存在问题，例如当我们有这些数字：120,130,70,80,90,100时，在preOrder遍历中这些节点的顺序是：120,70,80,90,100,130。因此，当我为100调用此函数时，该函数应返回130。但是你编写的代码返回了90。 - Linda

@Linda 我想我明白你的意思了。现在看起来怎么样？ - Steve P.

@Linda 没问题，很高兴我们终于解决了。 - Steve P.