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