1

二分探索木でルートから各リーフまでのパスからすべてのノードを検索し、それらを配列に格納する1つのメソッドを作成しようとしています。これまでのところ、ルートの右側に2つのノードの親であるノードが複数ない場合に正常に機能する厄介な方法を作成しました。何が悪いのかを理解するのに長い時間がかかりましたが、私の現在の方法が機能するのであれば、私は木を知らなければなりません、そしてそれはただ愚かです。

これは基本的に私がやろうとしていることです：

二分探索木の例

出力：[[8, 3, 1],[8 ,3 ,6 ,4],[8, 3, 6, 7],[8, 10, 14, 13]]

再帰を避け、スタックを使用したい。しかし、スタックからポップするノードを「制御」する方法がわかりません。サブツリーとサブツリーがある場合はどうなりますか。

4

4 に答える 4

3

このようなもの：

function Explore(node, currentPath)
   Add node to the currentPath

   If node has any Children
     If node has a left child
       Explore(left child, currentPath)
     if node has a right child  
       Explore(right child, currentPath)
   Else
     Node is a leaf node, report currentPath as a result.

   Remove the last node from currentPath
end
于 2012-11-06T14:46:58.940 に答える
1

http://en.wikipedia.org/wiki/Tree_traversal#Preorder

ウィキペディアはそれを私がこれまでにできたよりもよく説明しています。深さ優先探索が必要で、葉に当たったときに、これまでにたどったパス全体を記録します。

于 2012-11-06T14:41:32.403 に答える
1

再帰的および反復的（スタックを使用）の両方のDFS実装については、反復DFSと再帰DFS、およびさまざまな要素の順序を参照してください。

編集：

C ++固有の構文を無視すると、非常に読みやすくなりますが、ここに簡単な疑似コディッシュの説明があります。

create a stack of nodes
push root node of the tree on the stack. 
while (the stack is not empty) {
   pop the top of the stack, call it 'node' 
   if (we have not already marked 'node') {
     print the name of that node
     mark that node
     push any children of that node onto the stack
   } 
}

再帰的方法で必要とされないのは、すでにアクセスしたノードを追跡する方法です（これは、ノードに「マークを付ける」ことを意味します）。これは、ノード自体のプロパティにすることも、別のデータ構造を維持することもできます。これには、JavaHashSetが適切に機能します。

于 2012-11-06T19:08:40.277 に答える
1

再帰を実行しない場合は、呼び出しが行われた場所または再帰ソリューションのローカル変数によって暗示される種類のデータをスタックに明示的に格納する必要があります。この場合、いくつかのブール値を使用して、左側のサブツリーが実行されたかどうか、および右側のサブツリーが実行されたかどうかを示しました。

すべてを1つの方法で行うことはできませんでした。別の方法を使用して、スタックからノードラベルのリストを抽出します。また、別のラベルリストを持ち歩く手間を省くために、厳密にはスタックとして扱っていません。厳密なスタックにするための変更はかなり明白だと思います。コアコードにコメントしただけです。他に不明な点がないか、お気軽にお問い合わせください。

これは私がお勧めするデザインではないことを強調したいと思います。再帰を使用すると、コードが単純になると思います。私もそれを磨くのに多くの時間を費やしていません。

  import java.util.Stack;

  public class Bad {
    public static void main(String[] args) {
      TreeNode root;
      boolean firstLeaf = true;
      root = makeTree();
      Stack<StackNode> stack = new Stack<StackNode>();
      stack.push(new StackNode(root));
      System.out.print("[");
      while (stack.size() > 0) {
        // Decide what to do next with the top element
        StackNode top = stack.lastElement();
        if (top.tn == null) {
          // Nothing to do for a null subtree
          stack.pop();
        } else {
          if (top.tn.left == null && top.tn.right == null) {
            // leaf element, print it out and pop it.
            if(!firstLeaf) {
              System.out.print(",");
            }
            firstLeaf = false;
            System.out.print("[" + getLabelList(stack) + "]");
            stack.pop();
          } else {
            if (top.leftDone) {
              if (!top.rightDone) {
                stack.push(new StackNode(top.tn.right));
                top.rightDone = true;
              } else {
                // Done both subtrees
                stack.pop();
              }
            } else {
              stack.push(new StackNode(top.tn.left));
              top.leftDone = true;
            }
          }
        }
      }
      System.out.println("]");
    }

    private static class StackNode {
      TreeNode tn;
      boolean leftDone;
      boolean rightDone;

      public StackNode(TreeNode tn) {
        this.tn = tn;
      }
    }

    private static String getLabelList(Stack<StackNode> in) {
      String result = "";
      for (StackNode node : in) {
        if (result.length() > 0) {
          result += ", ";
        }
        result += node.tn.label;
      }
      //System.out.print("getLabelList: " + result);
      return result;
    }

    private static TreeNode makeTree() {
      TreeNode l;
      TreeNode r;
      l = new TreeNode(4, null, null);
      r = new TreeNode(7, null, null);
      r = new TreeNode(6, l, r);
      l = new TreeNode(1, null, null);
      l = new TreeNode(3, l, r);
      r = new TreeNode(14, new TreeNode(13, null, null), null);
      r = new TreeNode(10, null, r);
      return (new TreeNode(8, l, r));
    }
  }

  class StackNode {
    TreeNode current;
    boolean leftSubtreeDone;
  }

  class TreeNode {
    int label;
    TreeNode left;
    TreeNode right;

    public TreeNode(int label, TreeNode left, TreeNode right) {
      this.label = label;
      this.left = left;
      this.right = right;
    }
  }
于 2012-11-06T22:43:38.640 に答える