問題タブ [inorder]

インオーダートラバーサルのコードは次のようになります

すべてをコーディングしましたが、正常に動作します。その後、私はもっと考え始め、プロセスを考えすぎて、再帰が実際にどのように機能するかについて迷っています。ずっと左だと思うので、両方のノードがnullであるため、再帰は終了します。

私がずっと左にいて、左右のノードの両方が NULL である場合、再帰呼び出しによってどのように親ノードに戻ってトラバーサルを続けることができますか?

私は、4 日前にかかった中間試験の問題に出くわしました。理解できませんでした。

木の順不同のトラバーサルを行ったときに答えが得られたと仮定すると、プリオーダーのトラバーサルの場合、どうして解を見つけることができるのでしょうか。次の例がありますE A C K F H D B G。

preorder traversal は何を返しますか?

誰が私を学習面で助けてくれますか?

編集：答えはFAEKCDHGBです。しかし、これはどのように計算されますか？

質問は基本的にそれをすべて言っていますが、これは私がこれまでに持っているものです

}

アイデアは、最初に順不同のトラバーサルを実行し、代わりにすべての単語をそのカウントとともに出力するというものです。しかし、後でそのトラバーサルを再訪して、一意の単語のみを出力したいのですが、そのためのアルゴリズムコードを作成する方法がわかりません。単語数が 1 の場合、その単語はファイル内で 1 回しか出現しないため、一意である必要があります。誰かが私を助けることができれば、それは素晴らしいことです。

と呼ばれるメソッドを実装する必要があるバイナリ検索ツリーがあります

問題は、順序通りのトラバーサルで位置が必要なことです。

順番にトラバーサルを見つけるには、次のコードを使用しますが、再帰呼び出しを数えて正しい位置を取得する方法がわかりません。

二分木実装の正しい inorder-method を書く方法は?

これは私のテストトライです：

ツリーの場合、トラバーサル メソッドで値が返されるようにします。私が試した方法は、1つの値しか返しません。

このコードは完全に機能しますが、代わりにメソッドが値を返すようにしたい

最近、私の質問は、そうでなくても、このように重複としてマークされました。それでは、以下から始めましょう。次に、質問について説明します。

この質問が重複していないのはなぜですか?

inorder および preorder トラバーサルが与えられたときにバイナリ ツリーを作成する方法を尋ねているわけではありません。inorder+preorder トラバーサルが一意のバイナリ ツリーを定義するという証拠を求めています。

さて、元の質問に。私は面接に行き、面接官は私にこの質問をしました。行き詰まり、先に進めませんでした。:|

質問: バイナリ ツリーの順不同および順順トラバーサルが与えられました。与えられたデータに対して二分木が 1 つしか存在しないことを証明してください。言い換えれば、2 つの異なる二分木が同じ inorder および preorder トラバーサルを持つことはできないことを証明してください。ツリー内のすべての要素が一意であると仮定します (この仮定を指摘してくれた @envy_intelligence に感謝します)。

例を使ってインタビュアーを説得しようとしましたが、インタビュアーは数学的/直感的な証明を求めていました。誰かがそれを証明するのを手伝ってくれますか?