Python: 二叉树 Class: 遍历重构

Question

我正在尝试创建一个函数，该函数使用我的 ListBinaryTree: class 根据作为输入提示给出的中序遍历和先序遍历构造和打印二叉树（以字符串形式，例如 Inorder = 213 , 预购 = 123).我的二叉树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])+']'

到目前为止我有以下内容：

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

首先，发布的代码不能像您显示的那样工作：class 没有构造函数参数。最重要的是，您需要查阅 class 资料，了解如何根据两个给定的顺序重建树。

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

Python: 二叉树 Class: 遍历重构

Python: Binary Tree Class: Reconstruct with traversals

python

tree

binary-tree

class

tree-traversal