Python: построить двоичное дерево с Pre и Inorder

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), поэтому он должен появиться только один раз.