これは、ノードの 1 つが空である可能性があることを除けば、ごく普通のバイナリ ツリーです。
水平方向に出力する方法を見つけたいと思います(つまり、ルートノードが左側にあり、右側に拡張します)。
ツリーを垂直方向に拡張する (ルート ノードが上部にあり、下方向に拡張する) 経験はありますが、この場合、どこから始めればよいのかわかりません。
できれば、次の 2 つのルールに従うことが望ましいでしょう。
たとえば、これは 6 つのエンド ノードを持つ有効なツリーです (ノードは名前とその深さで表されます): 編集: 代替の簡単なレンダリングについては、質問の最後を参照してください。
[a0]-----------[b3]------[c5]------[d8]
\ \ \----------[e9]
\ \----[f5]
\-[g1]--------[h4]------[i6]
\ \--------------------[j10]
\-[k3]
これは、垂直の明示的な二分木を表します。
0 a
/ \
1 g *
/ \ \
2 * * *
/ \ \
3 k * b
/ / \
4 h * *
/ \ \ \
5 * * f c
/ \ / \
6 * i * *
/ / \
7 * * *
/ / \
8 * * d
/ /
9 * e
/
10 j
(コンパクトにするためにブランチは折りたたまれています。* 冗長な 1 つの子ノードを表します。* は実際のノードであり、それぞれ 1 つの子を格納しています。ここでは見栄えのために名前を省略しているだけです)
(また、明確にするために、この垂直ツリーではなく、最初の水平ツリーを生成したいと思います)
私が言語に依存しないと言ったのは、単にアルゴリズムを探しているだけだからです。 Ruby と言ったのは、いずれにせよ最終的には Ruby で実装する必要があるからです。
各ノード データ構造には、その ID、左側のノード、および右側のノードのみが格納されていると仮定します。
マスター ツリー クラスはすべてのノードを追跡し、以下を見つけるための適切なアルゴリズムを備えています。
もう知っている：
どこから始めればよいか考えている人はいますか?再帰的アプローチを採用する必要がありますか?反復的ですか？ いくつかの擬似コードも非常にクールであり、非常に感謝されます =)
進捗
walkytalky の提案に従って、私は各「関連する」ノードまたは重要なノードをグリッドにマップするとどうなるかを確認することにしました。列は深さであり、行は終端ノードで識別可能です。何が起こるかは次のとおりです (深さ 7 には重要なノードがないため、列 7 をスキップします)。
depth: 0 1 2 3 4 5 6 8 9 10
a b c d
e
f
g h i
j
k
幅優先または深さ優先の検索を使用して、このグリッドを生成するのは十分に簡単です。おそらく最も簡単なのは、単純に 2D 配列を保持し、見つかったすべての重要なノードをその中に配置し、「2 番目の子」ごとに行を挿入することです。
さて、これらの事実を知ると、
有効なグリッドが与えられた場合、いわば「点を接続する」ための明確な方法が 1 つあることがわかります。 1 つの明確なツリーが表現されています。
さて、「点と点を結ぶ」はもはや二分木構造の質問ではなく、単なる装飾的な質問です。必要なのは、バイナリ ツリー構造のルールではなく、おそらく単純なグリッド/辞書編集ルールのみに従って、適切な - と を配置できる場所に適切に配置するアルゴリズムを構築することだけです。
基本的に、これは、ツリーをレンダリングする問題が、派手な装飾を施したグリッドをレンダリングするというはるかに単純な問題になることを意味します。
誰かがこれらのルールを定式化する方法を提案できますか?それともまったく別の方法でしょうか?
編集
私は、はるかに簡単な最終レンダリングを考え出しました。
--d0----d1----d3----d4----d5----d6----d8----d9----d10-- => guide line (not rendered)
[a0 ]-------[b3 ]-------[c5 ]-------[d8 ]
| | \---------------[e9 ]
| \---------[f5 ]
\---[g1 ]-------[h4 ]-------[i6 ]
| \---------------------------[j10]
\---[k3 ]
--d0----d1----d3----d4----d5----d6----d8----d9----d10-- => guide line (not rendered)
以前に投稿したものの代わりに、これを作成してみる方が簡単かもしれません。まず、きれいなグリッド形状が維持され、対角線にこだわる必要がありません。行はすべて、はっきりと見える列の線に沿ってマッピングされます。残念ながら、最初のものほど美しくはありません。
N 個のエンド ノードがある場合、2 つの子を持つ N-1 個の内部ノードが存在する必要があります。 (1 つの子を持つ内部ノードはいくつでも存在できますが、深さを取得するにはカウントする必要がありますが、それ以外の場合は無視します。) したがって、ツリーの生成は、これらのノードをグリッド上に配置することと同じです。ここで、次のとおりです。
それでは、見てみましょう:
アップデート：
あなたが言うように、位置決めは接続を明確に決定するのに十分ですが、それを正しくするためにはまだボトムアップの作業を行う必要があるため、おそらくグリッドの構築中に「マーク」ステップを実行するでしょう。
印刷は無視できるほど些細なものだと思っていましたが、次のとおりです。
これを印刷対角線に変換するのは、最初に直線バージョンを生成してから文字配列でいくつかの置換を行う場合が最も簡単かもしれません。そうしないと、長い垂直の枝を、それが配置されている列とは別の列にレンダリングする場合が発生する可能性があります。起源となった。
ある時点で、これをコードに組み込もうとするかもしれませんが、それはおそらく今日ではないでしょう – やるべきことです!