如何從給定的輸入構建二叉樹

Question

我必須從某些給定的輸入構造二叉樹。輸入的格式如下： 。第一行代表接下來數據的行數（n）。 。接下來的n行代表以下形式的數據： 1.第一個字符是父節點 2.第二個字符是子節點 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 

它可能會更容易額外節省每添加節點在字典中，並做了查找字典中立即找到它。這隻適用於樹不包含重複項的情況。經典的方法是做樹遍歷。選擇上面的任何鏈接算法。