問題タブ [preorder]

私は BST に取り組んでおり、現在ツリー トラバーサルを試みています。私のインオーダー トラバーサル出力は事前オーダーによって正しくなり、ポストオーダー出力は正しくなりません。私のコードは

予約注文で私が得ている出力は

4-1-2-3-5-6-7

そうではないはずなのに

4-1-2-3-6-5-7

. 同様に、注文後の出力は

1-2-3-5-6-7-4

あるべきなのに

3-2-1-5-7-6-4

.

どこが間違っているのかわかりません。

事前注文トラバーサルと DFS は、葉ノードまで深さ方向にトラバースする両方の場合と同じように思えます。私が間違っている場合、誰かが私を修正してもらえますか?

前もって感謝します！

一意の要素を持つ非バイナリ ツリーの事前順および事後順トラバーサルを考えると、元のツリーをどのように作成するのでしょうか?

例えば

preorder = ABCDEF
および postorder = BCEFDA の場合

~~A~~~~~
~/~|~\~~~
B~C~D~~
~~~~/~\~~
~~~E~~F~に相当するツリーを構築する必要があります

（チルダについては申し訳ありませんが、ツリーを正しく表示し、読みやすくする方法を理解できる唯一の方法でした）

とにかく、これは宿題のプロジェクトであり、コード自体は問題ではないので、コードにこれを行うよう求めているわけではありません。私が助けを必要としているのは、適切なツリーを確実に作成するように2つの入力を比較するアルゴリズムです

PS指定されたツリーは、任意の数（おそらく<= 26）のノードで多かれ少なかれ複雑になる可能性があります

TL;DR
How do I use Pre-order and Post-order traversals to construct their original tree

私は Haskell の初心者で、クラスの課題に取り組もうとしています。次の形式でツリー オブジェクトをトラバースする予約注文関数を作成しようとしています。

私のツリークラスは次のとおりです

preorder 関数を定義すると、次のようなエラーが発生します。

そして、それらは最後の preorder 関数定義で発生しました

ターミナル（リーフノード）ノードの左の子になるように、ツリーを作成しようとしています。
リンクをクリックして、ツリーがどのように見えるかを確認してください。

ツリーをスレッド化する単純な挿入関数であるコードの inorder バージョンを取得しましたが、このコードを preOrder 挿入に変更することが問題です。

これはできますが、私の主な問題は、他のサブツリーにある予約注文の後継者を見つけることです。予約注文の後継者を取得する簡単な方法を知っている人はいますか?

問題の説明: (言語は Java)

二分探索木の前順トラバーサルを表す入力配列を指定すると、BST の後順トラバーサルを出力します。

キャッチ :

• BSTノードの構築なし。
• 再帰はありません。
• O(n) 実行時間。

私は何時間もそれを理解しようとしましたが、まだ手がかりがありません.
最も困難な部分は、ツリー ノード構造体を使用しないことです。
誰にもアイデアがありますか？

既存のバイナリ ツリーの前後のトラバーサルを実行する関数を実装したいと思います。

これらのトラバーサルは、定義済みのテスト関数によって表示される必要があります

ここに私がこれまでにプレオーダートラバーサルのために得たものがあります

現在のノードの値を配列に挿入し、配列内の位置をインクリメントし、左側のツリーと右側のツリーで再帰を実行すると考えましたが、これは機能しません。誰かがそれを実行するのを手伝ってくれることを願っています

私がしたことは、事前注文トラバーサルを使用した深さ優先検索であり、現在の値で埋めるために配列を含めました

メイン内のテスト関数:

木の高さを見つけるための事前注文トラバーサルを思いつきました。

高さは正確ですが、方法が正しいかどうかはわかりません。私がしていることはc、一番左のノードまでカウンターをインクリメントし、上に移動した場合は、右に移動する必要がある場合に備えてカウンターを減らし、演習全体を繰り返すことです。あれは正しいですか？