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。如果测试返回true，innerCurrentNode则将其视为叶子，忽略其子级。

编辑：这是我建议的模型（未经测试）：

//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 回答