3

我想编写一个采用树节点的函数。它应该返回在 preOrder 中获取节点之后访问的下一个节点是什么。我写了这段代码：（这段代码搜索左孩子并返回它。如果临时没有左孩子但它有右孩子，这个函数返回右孩子。但是如果节点是叶子并且没有孩子，它会得到父母直到得到一个有右孩子的节点。）

    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;

}

它确实有效，但我想让它递归。

任何人都可以帮我解决这个问题吗？

提前感谢您的关注。

4

1 回答 1

3 
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;
}

以供参考：

预购：root left right
订购：left root right
后订购：left right root

于 2013-12-11T20:26:30.007 回答