0

好的。我有一个二叉树,这就是我想要做的:

对于原始树中的每个节点:如果它不是叶子,则将其替换为叶子节点。对使用删除的分支更新的原始树进行计算。将节点恢复到原来的样子(所以现在树与开始时相同)。

问题是这样的:我正在使用堆栈遍历树。如果我将 stack.pop() 节点更改为叶子,这不会删除原始树中的任何分支。这与您为什么可以这样做的原因相同:

int x=1
int y=x
y++

x 仍然等于 1。对此有一个技术术语,但我忘记了。

那么如何编辑原始树中的节点并仍然遍历它呢?

这基本上就是我现在正在做的遍历树:

public void iterativePreorder(Node root) {
        Stack nodes = new Stack();
        nodes.push(root);

        Node currentNode;

        while (!nodes.isEmpty()) {
                currentNode = nodes.pop();
                Node right = currentNode.right();
                if (right != null) {
                        nodes.push(right);
                }
                Node left = currentNode.left();
                if (left != null) {
                        nodes.push(left);      
                }
                //This is where you do operations on the currentNode
        }
}
4

1 回答 1

0

从我从你的问题中可以看出,对于每一个Node你想要计算关于树的东西,就好像那个节点是一片叶子一样。

为此,没有理由实际使该节点成为叶子然后重新附加它。相反,您的逻辑可以简单地记住每次计算将哪个节点视为叶子。

遍历树,并且对于每个Node,让我们称之为outerCurrentNode,再次遍历树进行计算 - 但现在对于每个Node,让我们称之为innerCurrentNode,测试看看是否outerCurrentNode == innerCurrentNode。如果测试返回trueinnerCurrentNode则将其视为叶子,忽略其子级。

编辑:这是我建议的模型(未经测试):

//entry point - called from directing code
public void iterativePreorder(Node root) {
   iterativePreorderKernel(root, root);
}

//recursive method - keeps track of root in addition to current Node
private void iterativePreorderKernel(Node root, Node current) {

    if (current.left() != null) {
        iterativePreorderKernel(root, current.left());
    }
    if (current.right() != null) {
        iterativePreorderKernel(root, current.right());
    }

    //for each Node in the tree, do calculations on the entire tree, pretending
    //the current Node is a leaf
    doCalculation(root, current);
}

//calculation method (also recursive) - takes a current Node, plus
//the Node to treat as a leaf
public void doCalculation(Node innerCurrent, Node pretendLeaf) {

   //do calculation with inner current node

   if (innerCurrent != pretendLeaf) {
      if (innerCurrent.left() != null) {
         doCalculation(innerCurrent.left(), pretendLeaf);
      }
      if (innerCurrent.right() != null) {
         doCalculation(innerCurrent.right(), pretendLeaf);
      }
   }
}

我正在使用递归而不是 a Stack,但两者都可以。iterativePreorder()进行遍历,调用doCalculation()each Node,将其与根一起传递(以跟踪整个树)。然后该方法会进行自己的遍历,进行您的计算,但在到达特别标记的Node.

于 2011-09-22T03:24:14.220 回答