的Python：建立二叉樹Pre和中序

Question

我需要幫助我完成功能的遞歸部分。該函數應該使用我的ListBinaryTree類來幫助重建一棵樹，並按字符串格式進行序列遍歷：例如。

preorder = '1234567' 
inorder = '3241657' 

def build_tree(inorder, preorder): 
    head = preorder[0] 
    print(head) 
    head_pos = inorder.index(head) 
    print(head_pos) 
    left_in = inorder[:head_pos] 
    print(left_in) 
    right_in = inorder[(head_pos+1):] 
    print(right_in) 
    left_pre = preorder[1:-len(right_in)] 
    print(left_pre) 
    right_pre = preorder[-len(right_in):] 
    print(right_pre) 

其中發現在序和中序遍歷的重要價值和分裂樹起來，以確定哪些數字是左邊和右邊的樹。

其輸入和輸出的一個例子是：

build_tree('3241657', '1234567') 

。

1 
3 
324 
657 
234 
567 

我，我用它來創建樹類如下：

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])+']' 

對於我試圖做類似的函數的遞歸部分：

my_tree= ListBinaryTree(head) 
while my_tree.get_value() != None: 
     left_tree = build_tree(left_in, left_pre) 
     right_tree = build_tree(right_in, right_pre) 
     my_tree.insert_value_left(left_tree) 
     my_tree.insert_value_right(right_tree) 
    print (my_tree) 

但它返回「索引超出範圍」錯誤。

也類似：

def build_tree(inorder, preorder): 
    head = preorder[0] 
    head_pos = inorder.index(head) 
    left_in = inorder[:head_pos] 
    right_in = inorder[(head_pos+1):] 
    left_pre = preorder[1:-len(right_in)] 
    right_pre = preorder[-len(right_in):] 
    if left_in: 
     left_tree = build_tree(left_in, left_pre) 
    else: 
     left_tree = None 
    if right_in: 
     right_tree = build_tree(right_in, right_pre) 
    else: 
     right_tree = None 
    my_tree = ListBinaryTree(head, left_tree, right_tree) 
    print(my_tree) 

輸入

build_tree('3241657', '1234567') 

回報

[3, None, None] 
[4, None, None] 
[2, None, None] 
[6, None, None] 
[7, None, None] 
[5, None, None] 
[1, None, None]  

任何人都可以請幫我遞歸部分？

謝謝

Answer 1

你正在使遞歸部分比需要更難。

if left_in: 
    left_tree = build_tree(left_in, left_pre) 
else: 
    left_tree = None 

if right_in: 
    right_tree = build_tree(right_in, right_pre) 
else: 
    right_tree = None 

return ListBinaryTree(head, left_tree, right_tree) 

你或許可以通過移動爲空序列的檢查到功能（例如if not inorder: return None）的頂部進一步簡化，這樣它僅需要出現一次。