Python: 用 Pre 和 Inorder 构建二叉树

Question

我需要帮助来完成函数的递归部分。该函数应该使用我的 ListBinaryTree Class 来帮助重建树，给定其字符串格式的中序和先序遍历：例如

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

.

我用来创建树的class如下：

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)

但它 returns 一个 "index out of range" 错误。

还有类似的东西：

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

returns

[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）来进一步简化它，这样它只需要出现一次。

Python: 用 Pre 和 Inorder 构建二叉树

Python: Build Binary Tree with Pre and Inorder

python

tree

recursion

tree-traversal