予約注文トラバーサルが指定されたコンストラクトツリー

Question

すべてのリーフにLとマークされ、その他にNとマークされた特別なタイプのツリーがあります。すべてのノードは0または最大で2つのノードを持つことができます。木の先行走査が行われます。

このトラバーサルからツリーを構築するアルゴリズムを指定します。

Answer 1

これは先行順走査アルゴリズムです：

Preorder(T) 
    if (T is not null) 
    print T.label 
    Preorder(T.left) 
    Preorder(T.right) 

はのはNNLLNLの入力のためのアルゴリズムを見つけてみましょう。

明らかに、ルートのラベルが最初に印刷されます。だからあなたは根がラベルNを持っていることを知っています。アルゴリズムは左のサブツリーで繰り返されます。これはまた、入力に応じてNです。その左のサブツリーであるLに再帰します。あなたは葉に達しているので、今戻ってきなければなりません。入力の次の位置もLであるため、現在のノードにはLというラベルの付いた右の子があります。一度バックトラックしてください。現在のノードの子をすべて追加したため（最大2子）、もう一度バックトラックしてください。今、あなたは再び根源にいます。あなたはすでに左に行ったので、右に行かなければなりません。入力によると、これはNです。したがって、根の右の子はNです。その左の子はLになります。これはあなたのツリーです：

 N 
    / \ 
    N  N 
/\ /
    L L L 

解決方法は必ずしも一意ではありませんが、これにより解決策が得られることに注意してください。

擬似コード：nullのノードとの

k = 0 
input = ... get preorder traversal vector from user ... 
Reconstruct(T) 
    if input[k] == N 
    T = new node with label N 
    k = k + 1 
    Reconstruct(T.left) 
    Reconstruct(T.right) 
    else 
    T = new node with label L 
    T.left = T.right = null 
    k = k + 1 

コール。

フォローアップの質問：別個のノードラベルを含むバイナリツリーのプリオーダとインオーダトラバーサルの両方が与えられている場合、どのようにしてツリーを一意に再構築できますか？