从中缀和前缀表达式重建二叉树 [python]

Question

我花了几个小时试图弄清楚如何做到这一点，我知道函数 "buildtree" 必须递归调用才能绘制，但我就是想不通，我只需要一个勺子喂我可以研究的答案，我已经尝试这样做很长时间了，这不在我的能力范围内，因为我无法理解事物的逻辑流程。（可悲的是我知道这只需要几行代码）

from ListBinaryTree import ListBinaryTree

def buildtree(left_inorder, left_preorder, right_inorder, right_preorder, root, tree):
    #dont know what to do.


def main(): 
    print("Binary Tree reconstructed by glee598:") 
    inorder_seq = input("Please enter the inorder sequence: ")
    preorder_seq = input("Please enter the preorder sequence: ")
    root = preorder_seq[0]
    root_inorder_index = inorder_seq.find(root)

    left_inorder = inorder_seq[:root_inorder_index]
    right_inorder = inorder_seq[root_inorder_index+1:]

    left_preorder = preorder_seq[1:preorder_seq.find(left_inorder[0])+1]
    right_preorder = preorder_seq[preorder_seq.find(left_inorder[0])+1:]

    tree = ListBinaryTree(root)

    buildtree(left_inorder, left_preorder, right_inorder, right_preorder, root, tree)
main()

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

Objective:

Answer 1

我想你差不多明白了，你只是在设置代码中加入了太多的逻辑，而没有意识到递归代码将是同一件事。

如果您将递归 buildtree 函数的 API 更改为简单地获取整个 inorder 和 preorder 序列以及 return 一棵用它们建造的树。

def buildtree(inorder, preorder):
    root_val = preorder[0]
    left_size = inorder.index(root_val) # size of the left subtree

    if left_size > 0:
        left = buildtree(inorder[:left_size], preorder[1:left_size+1])
    else:
        left = None

    if (left_size + 1) < len(inorder):
        right = buildtree(inorder[left_size+1:], preorder[left_size+1:])
    else:
        right = None

    return ListBinaryTree(root_val, left, right)

从中缀和前缀表达式重建二叉树 [python]

Reconstructing a binary tree from infix and prefix expressions [python]

tree

binary-tree

python-3.x