与えられた入力からバイナリツリーを構築する方法

Question

与えられた入力からバイナリツリーを構築する必要があります。入力は以下の形式で入力します： 。最初の行は、次に来るデータの行数（n）を表します。 。次のn行は、次の形式のデータを表します。 1.最初の文字は親ノード 2. 2番目の文字は子ノード 3. 3番目の文字は方向です（Lは左の子を表し、Rは次のように右の子）

サンプル入力は次のとおりです。

9 
1 2 R 
1 3 L 
2 4 R 
2 5 L 
3 6 R 
3 7 L 
5 8 R 
5 9 L 
7 10 R 

誰かがこのバイナリツリーを構築するためのコードを書く方法へと私を導いてくださいすることができます。 これは非常に簡単な質問ですが、誰かが私にこのことについてどうやって行くか教えてください。

私はこのような単純なツリークラス構築：

class Tree: 
    def __init__(self,x): 
     self.data = x 
     self.left = None 
     self.right = None 

をしかし、私はロジックを進めることができないのです。

ありがとうございました。

Answer 1

まず、バイナリツリーの仕組みを理解する必要があります。tree traversal。 アルゴリズムは、このように動作します：

1. Traverse tree to find parent (first number) 
2. If next char is R insert new Tree(secondNumber), else insert Tree at left 
3. Repeat 

辞書に加えて追加されたすべてのノードを保存する方が簡単かつ即座にそれを見つけるために辞書で検索を行うことができます。これは、ツリーに重複が含まれていない場合にのみ機能します。 古典的なやり方は、ツリーを横切ることです。上記のリンクされたアルゴリズムのいずれかを選択します。