2

ノードが次のように定義されている、ソートされていないノード配列があるとします。
Node { int id; int parent_id; string label; }

各ノードには独自の一意の ID があります。parent_idツリーでその親を識別します。問題は、ツリーの事前注文トラバーサルを行う方法です。(二分木である必要はありません)

これは、数日間私を悩ませてきたインタビューの質問です. 私が考えることができるのはmap<int,list<node> >、キーが親 ID であるハッシュ マップを使用することです。それから私はそれ以上行くことができません。マップからツリーを構築し、事前注文トラバーサルを行うべきですか、それともマップから直接行う良い方法がある場合は? ではどうやって？どんなヒントでも大歓迎です！

4

1 に答える 1

1

したがって、次のものが必要です。

map<int, list<Node> > childMap;
map<int, Node> nodeMap;

親を持たないノード (parent_id = -1 など) が見つかります。これは明らかにルートです。上記のマップを設定した後、そのノードに対して以下の関数を呼び出します。

preOrder(int id)
{
  process(nodeMap[id]);
  foreach (Node node: childMap[id])
    preOrder(node);
}
于 2013-01-01T20:54:19.827 に答える