如何从给定的输入构建二叉树

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 

它可能会更容易额外节省每添加节点在字典中，并做了查找字典中立即找到它。这只适用于树不包含重复项的情况。经典的方法是做树遍历。选择上面的任何链接算法。