0

入力がフォーマットを与え、親ノードであり、子ノードであるツリーを構築する最良の方法は(a,b)何aですかb? (ノード 1 がルート) 例:

1 2 //adds node #2 as the children of #1 (the root)
1 3 //adds node #3 as the second children of the root
2 4 //adds node #4 as the children of node #2
etc...

二分木に似ている場合、この種の木を作成する方法を理解しています (特定の親ノードに対して、左の子は値が小さく、右の子は値が大きいため)。しかし、親が持つことができる子ノードの量は、私のツリーでは固定されていません。これを効率的に作成するにはどうすればよいですか？ノードが持つaことbができる子の量が直らない。

編集：追加したいもう1つのこと：各リーフノード（子ノードのないもの）にはいくつかの値が割り当てられます。各ノードの値を計算できるように、再帰的に (または他の方法で) ツリーをたどる必要があります。親ノードの値は、そのすべての子ノードの値の合計です。

4

2 に答える 2

0

各ノードに右の子と兄弟のアドレスを格納します。

を受け取ったときa,b、ノードaに正しい子がない場合は正しい子として挿入bし、正しい子がある場合は正しい子の兄弟をたどって最後の子を見つけb、最後のノードの兄弟として挿入します。

ツリーのトラバース:

このアルゴリズムは、深さ優先でツリーをトラバースできると思います。

traverse(Node) 
 visit (Node) // pre order 
 if (Node.RightChild != Null)
  n = Node.RightChild
  while(n.LeftSibling != Null)
   traverse ( n.LeftSibling )
   n = n.LeftSibling
  end
 end
end
于 2013-10-25T07:05:31.737 に答える
0

通常は、子ノードをリンク リスト (または配列) として格納するだけで十分です (ただし、ツリーの種類によっては、他の表現の方が効率的な場合もあります)。

通常、ノードのマップまたは配列があります。

を探しているときaは、マップまたは配列でルックアップを行うだけです。

次にb、子のリストに追加するだけです。

ツリーを再帰的にトラバースする必要があります

これには、単純な幅優先検索または深さ優先検索が含まれます。

于 2013-10-25T07:46:17.203 に答える