4

ツリー構造をレベルごとに表示したいと思います。私の現在のコードは BFS または Level Order Traversal を実行しますが、ツリーのようなツリー構造を表示する出力を取得できません。現在の出力と期待される出力を参照してください。

私のアイデアは、ある種のカウントを使用して、キュー内の同じレベルの要素を反復処理することでした。

どうすればそうできますか。

この関数のない元のコードは、誰かが実装全体を必要とする場合に備えて、以下のリンクで見つけることができます。それ以外の場合は、以下の displayBFS 関数を参照してください。

Javaのジェネリックツリー（n-aryツリー）のレベルオーダートラバーサル

ありがとう！

   void displayBFS(NaryTreeNode n)
   {
      Queue<NaryTreeNode> q  = new LinkedList<NaryTreeNode>();
      System.out.println(n.data);

       while(n!=null)
     {   
         for(NaryTreeNode x:n.nary_list)
         {
             q.add(x);
             System.out.print(x.data + " ");
         }
         n=q.poll();
         System.out.println();
      } 
  }

Current Tree Structure for reference:

         root(100)
        /      |       \
      90       50       70
      /        \
    20 30   200  300


    Current Output:
        100
        90 50 70
        20 30
        200 300

    Expected Output
        100
        90 50 70
        20 30 200 300

また、以前に同じ機能でロジックの問題を投稿しました。それは回答済みで、現在の質問は別の問題に関連しているため、新しい質問を投稿しました。このアプローチは大丈夫ですか、それとも以前の質問を編集して開かないでください新しいもの？

4

5 に答える 5

2

現在のレベルと次のレベルを追跡する必要があるだけです。

static void displayBFS(NaryTreeNode root) {
    int curlevel = 1;
    int nextlevel = 0;

    LinkedList<NaryTreeNode> queue = new LinkedList<NaryTreeNode>();
    queue.add(root);

    while(!queue.isEmpty()) { 
        NaryTreeNode node = queue.remove(0);

        if (curlevel == 0) {
            System.out.println();
            curlevel = nextlevel;
            nextlevel = 0;
        }

        for(NaryTreeNode n : node.nary_list) {
            queue.addLast(n);
            nextlevel++;
        }

        curlevel--;
        System.out.print(node.data + " ");
    } 
}

レベルを切り替えるときは、nextlevelをcurrentlevelに交換し、nextlevelをリセットします。私は、完全に別個のキューを保持するよりも、これの単純さを好みます。

先週のマイクロソフトのインタビューでこの質問がありました...電話ではうまくいきませんでした。それを勉強してくれてありがとう。

于 2012-10-10T09:56:28.413 に答える
2

この問題に対する私が知っている最も簡単な解決策は、センチネルを使用することです。キューは、ルート ノードとそれに続くセンチネルで初期化され、キューをループ処理します。

  1. フロント要素を削除します
  2. それが歩哨の場合：
    • レベルの終わりにいるので、出力行を終了できます
    • キューが空でない場合は、センチネルを最後にキューに戻します。
  3. センチネルでない場合:
    • 印刷する
    • すべての子をキューにプッシュします。

私は Java をしませんが、深さを認識する BFS 用の C++ コードをいくつか持っています。

void show_tree_by_levels(std::ostream& os, Node* tree) {
  Node* sentinel = new Node;
  std::deque<Node*> queue{tree, sentinel};
  while (true) {
    Node* here = queue.front();
    queue.pop_front();
    if (here == sentinel) {
      os << std::endl;
      if (queue.empty())
        break;
      else
        queue.push_back(sentinel);
    } else {
      for (Node* child = here->child; child; child = child->sibling)
        queue.push_back(child);
      os << here->value << ' ';
    }
  }
}

私は 2 ポインター ソリューション (first_child/next_sibling) を使用することを好むことに注意してください。これは、通常、埋め込みリストよりも単純になるためです。YMMV。

于 2012-10-13T23:24:28.650 に答える
1

あと 3 つの変数が必要だと思います。現在のレベルの要素数を追跡するための numInCurrentLevel、現在のレベルで走査するときにカウントを行うためのindexInCurrentLevel 、次のレベルの要素数を追跡するためのnumInNextLevel。コードは以下のとおりです。

static void displayBFS(NaryTreeNode root) {

    Queue<NaryTreeNode> q  = new LinkedList<NaryTreeNode>();;
    q.add(root);
    int numInCurrentLevel = 1;
    int numInNextLevel = 0;
    int indexInCurrentLevel=0;

    while(!q.isEmpty()) { 
        NaryTreeNode node = q.poll();
        System.out.print(node.data + " ");
        indexInCurrentLevel++;

        for(NaryTreeNode n : node.nary_list) {
            q.add(n);
            numInNextLevel++;
        }

        //finish traversal in current level
        if(indexInCurrentLevel==numInCurrentLevel) {
            System.out.println();
            numInCurrentLevel=numInNextLevel;
            numInNextLevel=0;           
            indexInCurrentLevel=0;
        }
  } 
}

私は Java プログラミングにあまり詳しくありません。

于 2012-10-11T07:42:47.967 に答える
1

別のキューを使用して深さを示します。以下のコードはテストされていませんが、アイデアが得られるはずです (末尾の空白を避けるために sep 変数が導入されています)。

void displayBFS(NaryTreeNode n) {
  Queue<NaryTreeNode> q  = new LinkedList<NaryTreeNode>();
  Queue<Integer> depth  = new LinkedList<Integer>();
  q.add(n);
  depth.add(0);

  String sep = "";
  int oldDepth = 0

  while(!q.isEmpty()) {
    NaryTreeNode currN = q.poll();
    int currDepth = depth.poll();
    if (currDepth > oldDepth) {
      System.out.println();
      oldDepth = currDepth;
      sep = "";
    }
    System.out.print(sep + currN.data);
    sep = " ";

    for(NaryTreeNode x : currN.nary_list) {
      q.add(x);
      depth.add(currDepth + 1);
    }
  }
}

私の好みでは、このアプローチは、他の方法と比較して自明です。

于 2012-10-10T09:55:05.190 に答える