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

の代わりに再帰を使用してStackいますが、どちらでも機能します。iterativePreorder()トラバーサルをdoCalculation()実行し、それぞれを呼び出しNode、ルートと一緒に渡します（ツリー全体を追跡するため）。次に、そのメソッドは独自のトラバーサルを実行して計算を実行しますが、特別にマークされたに達するとすぐに停止しますNode。

于 2011-09-22T03:24:14.220 に答える