1

単純な実装クエリを実行していました。

したがって、次のコードを使用してBSTを作成します。

class Node{

    int data;
    Node left=null;
    Node right=null;
    Node link=null;

    public Node(int d)
    {
        data=d;
    }

    public void append(int d)
    {
        Node n=this;
        Node nval=new Node(d);
        if(n==null)
        {
            n.data=d;
        }
        else
        {   boolean done=false;
            while(!done)
            {
                 if(n.data<=d)
                 {
                     if(n.left==null)
                     {
                         n.left=nval;
                         done=true;
                     System.out.println("Data Entered "+nval.data);
                     }
                     else
                     {
                         n=n.left;
                     }
                 }
                 else
                 if(n.data>d)
                 {
                     if(n.right==null)
                     {
                         n.right=nval;
                         done=true;
                     System.out.println("Data Entered "+nval.data);
                     }
                     else
                     {
                         n=n.right;
                     }
                 }
            }
        }
    }
}

今、私はそれに幅優先探索と深さ優先探索を適用し始めました。私はこれを行うことに真の問題を抱えていました。

DFSの場合、スタックに配置されている現在のノードの左右の値を右に追加する必要がありますか？これをどのようにプログラムしますか？リンクリストを使用してこれを行うのに問題がありましたか？誰かがデータ構造やポインタがどうあるべきか教えてもらえますか？

同じことがBFSでも起こります。以前にはっきりしていなかった場合、私の主な問題は、配列要素を削除してから、それをその子に置き換えることです。

4

2 に答える 2

2

一般に、キュー(FIFO) は BFS に適しています。プライオリティ キューである必要はありませんが、多くの場合、重み付けが非常に一般的であるためです。

キューは通常、FIFO (先入れ先出し) 方式で要素を並べ替えますが、必ずしもそうとは限りません。例外の中には、指定されたコンパレータまたは要素の自然な順序に従って要素を並べ替える優先度キューと、要素を LIFO (後入れ先出し) で並べ替える LIFO キュー (またはスタック) があります。順序がどうであれ、キューの先頭は、remove() または poll() の呼び出しによって削除される要素です。FIFO キューでは、すべての新しい要素がキューの末尾に挿入されます。他の種類のキューでは、異なる配置規則が使用される場合があります。すべての Queue 実装は、その順序付けプロパティを指定する必要があります。

キューを使用した BFS の基本的な「アルゴリズム」ルール:

  1. 初期状態を (Qキュー)に入れる
  2. の頭を取るQ( を参照remove)
  3. 取得した値で何かを行う (例: parent -> [child1, child2 ..])
  4. 手順 3 の結果を末尾に追加しますQ( を参照add) 。
  5. Qが空になるか、他のエンドケースが達成されるまで、ステップ 2 に戻ります。

配列は、過去の初期化と反復を処理するための単なる PITA です。「スライス」と「サイズ変更」は、Java では特に苦痛になりがちです。

于 2012-12-25T01:59:19.350 に答える