Python：二叉树类：用遍历重建

Question

我想做一个函数，使用我的ListBinaryTree：类来构造和打印二叉树，基于作为输入提示的inorder和preorder遍历（以字符串形式，例如。 Inorder = 213，Preorder = 123）。我二叉树类如下：

class ListBinaryTree: 
"""A binary tree class with nodes as lists.""" 
DATA = 0 # just some constants for readability 
LEFT = 1 
RIGHT = 2 

def __init__(self, root_value, left=None, right=None): 
    """Create a binary tree with a given root value 
    left, right the left, right subtrees   
    """ 
    self.node = [root_value, left, right] 

def create_tree(self, a_list): 
    return ListBinaryTree(a_list[0], a_list[1], a_list[2]) 

def insert_value_left(self, value): 
    """Inserts value to the left of this node. 
    Pushes any existing left subtree down as the left child of the new node. 
    """ 
    self.node[self.LEFT] = ListBinaryTree(value, self.node[self.LEFT], None) 

def insert_value_right(self, value): 
    """Inserts value to the right of this node. 
    Pushes any existing left subtree down as the left child of the new node. 
    """  
    self.node[self.RIGHT] = ListBinaryTree(value, None, self.node[self.RIGHT]) 

def insert_tree_left(self, tree): 
    """Inserts new left subtree of current node""" 
    self.node[self.LEFT] = tree 

def insert_tree_right(self, tree): 
    """Inserts new left subtree of current node""" 
    self.node[self.RIGHT] = tree 

def set_value(self, new_value): 
    """Sets the value of the node.""" 
    self.node[self.DATA] = new_value 

def get_value(self): 
    """Gets the value of the node.""" 
    return self.node[self.DATA] 

def get_left_subtree(self): 
    """Gets the left subtree of the node.""" 
    return self.node[self.LEFT] 

def get_right_subtree(self): 
    """Gets the right subtree of the node.""" 
    return self.node[self.RIGHT] 

def __str__(self): 
    return '['+str(self.node[self.DATA])+', '+str(self.node[self.LEFT])+', '+\ 
str(self.node[self.RIGHT])+']' 

到目前为止，我有以下几点：

def reconstruct(): 
    inorder = input("Please enter the inorder sequence:") 
    preorder = input("Please enter the preorder sequence:") 
    #root = preorder[0] 
    #left_bottom = inorder[0] 
    #right_bottom = inorder[len(inorder)-1] 
    my_tree = ListBinaryTree(int(preorder[0])) 
    my_tree.insert_tree_left(int(inorder[0])) 
    my_tree.insert_tree_right(int(inorder[len(inorder)-1])) 
    print (my_tree) 

但它仅适用于与1级或2级树： 输出的一个例子是：

调用函数

reconstruct() 

提示：

Please enter the inorder sequence:213 
Please enter the preorder sequence:123 

打印结果：

[1, 2, 3] 

如何更改我的功能，使其可以构建一个树/遍历理论上无限量更高的水平？

Answer 1

首先，发布的代码不起作用，如您所示：该类没有构造函数参数。最重要的是，你需要咨询你的课堂材料，看看如何从两个给定的订单重建树。

• inorder的头是树的根。
• 在预购中找到此元素。
• 在此处拆分预订：根 之前的元素位于其左侧子树中;之后的元素位于正确的子树中。
• 使用这些来拆分inorder。
• 在每个左右子树上重现。

这会让你走吗？

---

让我们来看看关于伪代码：

def build_tree(inorder, preorder): 
    if len(inorder) == 1: 
     make a one-node tree of this node 
     return this tree 
    head = inorder[0] 
    head_pos = position of head in preorder[] 
    left_pre = preorder[:head_pos] 
    right_pre = preorder[head_pos+1:] 
    left_in = inorder[1:-len(right_pre)] 
    right_in = inorder[-len(right_pre):] 
    left_tree = build_tree(left_in, left_pre) 
    right_tree = build_tree(right_in, right_pre) 
    make a tree that has 
     head as its root 
     left_tree as its left subtree 
     right_tree as its right subtree 
    return this tree