1

私の入力結果24, 4, 2, 3, 9, 10, 32、そして私は次の結果を得ています2, 3, 4, 24。

スタックを使用しています。このプログラムを手動でチェックしたelse if場合、正しいサブツリーがある場合でも、ノードはスタックの4で通過していません。

public void inorderNonRcursive(Node root){

    Stack s = new Stack();
    Node node = root;
    Node k;
    int c=0;

    if(node != null) {
        s.push(node);    
    }

    while(!s.stack.isEmpty()) {   

        //node=(Node) s.stack.get(s.stack.size()-1);
        System.out.println("first condition" + (node.getleft() != null && (node.getVisited() == false)) + "second condi" + (node.getRight() != null));

        if(node.getleft() != null && (node.getVisited() == false)) {
            node = node.getleft();
            s.push(node);
            System.out.println("   from 1           "+(++c)); 

        } else if(node.getRight() != null) {
            k = s.pop();
            System.out.println(k.getvalue());
            node=node.getRight();
            s.push(node);
            System.out.println("    from 2          "+(++c)); 

        } else {
            k = s.pop();
            System.out.println(k.getvalue());
            System.out.println("        from 3      "+(++c)); 
        }  

    }

}
4

2 に答える 2

9

私にとって、設計には2つの問題があります。

  1. アルゴリズムは、反復と
  2. クラスはNode訪問されることを知っています。

これは別の解決策です（少し適応させる必要があります）：

// Inorder traversal:
// Keep the nodes in the path that are waiting to be visited
Stack s = new Stack(); 
// The first node to be visited is the leftmost
Node node = root;
while (node != null)
{
    s.push(node);
    node = node.left;
}
// Traverse the tree
while (s.size() > 0)
{
    // Visit the top node
    node = (Node)s.pop();
    System.out.println((String)node.data);
    // Find the next node
    if (node.right != null)
    {
        node = node.right;
        // The next node to be visited is the leftmost
        while (node != null)
        {
            s.push(node);
            node = node.left;
        }
    }
}

私の最初のコメントを振り返ると、擬似コードを作成してテストしたとは言えません。これは、新しいアルゴリズムを作成する上での重要なステップだと思います。

于 2012-10-03T23:07:06.290 に答える
3

これは、二分木を理解するのに役立つように設計されたクラス演習のように見えます。

コードを書く前に、「A」、「B」、「C」などの各ノードの値を使用して、ツリーの図を描きます。次に、ルートノードから始めて、何をする必要があるかを確認します。各ノードに順番にアクセスします。学んだことを擬似コードで書き、それが言うことを実行してテストします。各ノードについて考えられるさまざまなケースをすべてテストするようにしてください（少なくとも3つは必要です）。ツリーに約7つのノードを配置します。

これで、コードを開始できます。擬似コードをコメントとして入力し、各コメントの間にJavaコードを挿入します。

楽しみ ：-）

于 2012-10-03T05:39:37.350 に答える