問題タブ [preorder]

ツリーの内容を印刷する方法があります。

ツリーの内容は正しく読み取られていますが、見栄えが良くなるようにツリーをフォーマットしたいと思います。今、木の場合：

内容の印刷：

しかし、次のようにインデントを追加したいと思います。

形式は次のようになります。

再帰で少し迷っています。ありがとう！

恥ずかしすぎて聞けない、痛々しいほど愚かな質問。私は過去4時間検索し、さまざまなアルゴリズムをテストし、紙でかなりの数を試しましたが、それでも機能させることができません。

プロジェクトの実装の詳細は割愛しますが、基本的な質問は次のとおりです。「プレオーダーバイナリツリーへのノードの挿入をどのように処理しますか。

事前注文BSTとは、すべてのノードをそのような方法で挿入する必要があることを意味します。つまり、事前注文トラバーサル（印刷など）を使用してツリーをトラバースすると、ノードが昇順で印刷されます。

必要なのは単純なアルゴリズムだけです。私はここで与えられた単純な挿入アルゴリズムを試しました（stackoverflowで、しかしそれは正しくないようです（紙でも試しました））;。

ノードは基本的に次のようなものです。

挿入データは、一意の整数の単なるリストです。intをキーとしてノードを作成し、そのノードをツリーに追加する必要があります。私はルートノードを持っています。これはNULLポインターとして始まります。

不明な点がある場合は申し訳ありません。

助けてくれてありがとう！

編集：以下に提供されるアルゴリズムに基づいて、これは私が思いついたものです：

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

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

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

バイナリ ツリーでのプリオーダー トラバーサル中に、要素をリンク リストに追加したいと考えています。BT を破棄したくありません。リンクされたリスト内の要素のコピーを作成するだけです。これは私のコードスニペットです。

上記のコードは何も出力しません。問題は head = List_insert(head, node->data); の使用にあると思います。予約機能で。どんな助けでも大歓迎です。

各ノードがリーフノードまたは内部ノードのいずれかにラベル付けされている完全な二分木のプレオーダートラバーサルを考えると、ツリーの高さを見つけるための優れたアルゴリズムはありますか？たとえば、Nが内部ノードを表し、Lがリーフを表す場合、プレオーダートラバースNLNNLLLが与えられると、高さは3になります。

課題があり、方法について助けが必要です。

だから私はこのような木を持っています:

私の方法は次のとおりです。

講師はツリーの簡単な実装を行っていました。このクラスは BinaryTree と呼ばれ、それにノードをリンクさせたい場合は、右と左の子 BinaryTree ノードが何であるかを指定します。

ノードには 2 つのリンク (1 つは左の子、もう 1 つは右の子) があり、ヘッドへのリンクはありません。

したがって、現在の方法で事前注文トラバーサルを成功させることができるので、ノードに格納されている要素の印刷ステートメントを記述してテストしました。

しかし、テストを実行すると、A からの次の事前注文ノードは B であり、K からの次の事前注文ノードは null 例外をスローしますが、それは I である必要があります。

私が間違っている場所のアイデアはありますか? 変数 prev は、最後に訪れたノードへの参照を保持する必要があるため、ノード v (v の後にノードを返すために指定したノード) に等しい場合、次のノードを取得するべきではありませんか?

適切に機能するために、ツリーを印刷する次の機能があります。

これは私の予約注文印刷機能です:

私は愚かすぎて、 inorder 関数のように印刷する方法を理解できないので、皆さんが私を助けてくれることを願っています!

ありがとう！

アップデート：

予約注文機能が機能するようになりましたが、これは正しい注文注文機能ですか?

T が複数のノードを持つ順序付けられたツリーである場合。T の事前順序トラバーサルが、T の後順序トラバーサルと同じ順序でノードを訪問することは可能ですか? 「はい」の場合、例を教えてください。また、「いいえ」の場合、なぜそれが発生しないのか説明していただけますか?

プレオーダー、ポストオーダー、インオーダーの描画ルールは次のとおりです。

1. トラバーサルの事前注文: ルート、左、右
2. ポストオーダー トラバーサル: 左、右、ルート
3. 順序通りのトラバーサル: 左ルート、右

たとえば、次のような式があるとします。

ABCDEFGHIJKL、

この式を個別に (事前注文、事後注文、注文順で) 描画するにはどうすればよいですか。それぞれ (事前注文、事後注文、注文順) で異なる形式のツリーが存在する可能性があります。(つまり、事前注文の 2 つの形式)。(事前注文と順序どおり) または (事後注文と順序どおり) の両方がある場合は、一意のツリーを持つことができます。予約注文では、最初のノードがルートです (つまり、「A」がルートです)。ポストオーダーでは、最後のノードがルートです (つまり、「L」がルートです)。

これらの木を描くための全体的な公式または「ルール」はありますか? 私はそれらを描くことができません

編集:次のトラバーサルの各プレオーダー、ポストオーダー、インオーダーからツリーを構築する方法を意味します:

ABCDEFGHIJKL、

修正されたプレオーダー ツリーを使用して、アプリケーションの GEO ロケーションを単一のテーブル LOC_TABLE に格納します。たとえば、ギリシャのサブツリーの例は次のようになります。

TYPE列は、場所のタイプ (3 - 国、4 - 都市) を格納するために使用されます。ご覧のように、Crete は city として格納されており、その子として他の都市 (Vamosと など) が含まれています。Rethymno

次の 2 種類のクエリを実行する必要があります。

1) 特定の親の下にある特定のタイプのすべての場所を取得します。

2) 特定の親の下にある特定のタイプの上位のすべての場所を取得します: 提供された例では、ギリシャ国内の都市を照会する場合にのみ、場所の例を返す必要Crete Isl.があります。Crete Isl.VamosRethymnoCrete Isl.

それぞれのケースで実行する最速のクエリは何ですか?

最初のケースでは、2 つのクエリを使用する (最初にギリシャの LFT と RGT を取得し、次に適切な LFT と RGT を持つタイプ = 4 のすべての場所を取得する) か、何らかの結合を使用して 1 つのステップですべての場所を取得することを検討します。 . 最適なアプローチはどれですか?

2番目のケースについては、現在適切なアイデアがありません。私は単純なサブセレクトを試しました：

しかし、長すぎます。

これら 2 種類のクエリを高速化するのに役立つ列を追加して値を設定しても構いません。しかし、データをすばやく取得する必要があります。

ありがとう。