python - 给定 Python 中前缀表示法的字符串表达式，递归创建二叉树

Question

Representation of LinkedBinaryTree that should be outputted
导入LinkedBinaryTree

def create_expression_tree(prefix_exp_str):

    def create_expression_tree_helper(prefix_exp, start_pos):
        start_pos += 1
        op = ['+', '-', '*', '/']
        elem = prefix_exp[start_pos]
        if elem == ' ':
            elem = prefix_exp[start_pos+1]
            start_pos += 1

        if elem not in op:
            return LinkedBinaryTree.LinkedBinaryTree.Node(int(elem))
        else:
            left = create_expression_tree_helper(prefix_exp, start_pos)
            right = create_expression_tree_helper(prefix_exp, start_pos+2)
            return LinkedBinaryTree.LinkedBinaryTree.Node(elem, left, right)

    tree = LinkedBinaryTree.LinkedBinaryTree(create_expression_tree_helper(prefix_exp_str, -1))

    return tree

tree1 = create_expression_tree('* 2 + - 15 6 4')
for i in tree1.preorder():
    print(i.data, end='')

我实现了自己的二叉树类，如下所示。 Preorder() 是 LinkedBinaryTree 的生成器，它按前缀顺序给出树的值。使用这段代码，我输出*2+-151但它应该输出*2+-1564 如果二叉表达式树已正确创建。我知道大于 1 位的数字存在问题，但我不确定如何在不影响运行时的情况下修复它(即使用切片)。我也不确定为什么它省略了一些标记。有任何想法吗？ (该实现必须以线性时间运行，并且在我定义的辅助函数中不使用任何附加参数)。

import ArrayQueue

class LinkedBinaryTree:

    class Node:
        def __init__(self, data, left=None, right=None):
            self.data = data
            self.parent = None
            self.left = left
            if (self.left is not None):
                self.left.parent = self
            self.right = right
            if (self.right is not None):
                self.right.parent = self

    def __init__(self, root=None):
        self.root = root
        self.size = self.subtree_count(root)

    def __len__(self):
        return self.size

    def is_empty(self):
        return len(self) == 0

    def subtree_count(self, root):
        if (root is None):
            return 0
        else:
            left_count = self.subtree_count(root.left)
            right_count = self.subtree_count(root.right)
            return 1 + left_count + right_count


    def sum(self):
        return self.subtree_sum(self.root)

    def subtree_sum(self, root):
        if (root is None):
            return 0
        else:
            left_sum = self.subtree_sum(root.left)
            right_sum = self.subtree_sum(root.right)
            return root.data + left_sum + right_sum


    def height(self):
        return self.subtree_height(self.root)

    def subtree_height(self, root):
        if (root.left is None and root.right is None):
            return 0
        elif (root.left is  None):
            return 1 + self.subtree_height(root.right)
        elif (root.right is  None):
            return 1 + self.subtree_height(root.left)
        else:
            left_height = self.subtree_height(root.left)
            right_height = self.subtree_height(root.right)
            return 1 + max(left_height, right_height)


    def preorder(self):
        yield from self.subtree_preorder(self.root)

    def subtree_preorder(self, root):
        if(root is None):
            return
        else:
            yield root
            yield from self.subtree_preorder(root.left)
            yield from self.subtree_preorder(root.right)


    def postorder(self):
        yield from self.subtree_postorder(self.root)

    def subtree_postorder(self, root):
        if(root is None):
            return
        else:
            yield from self.subtree_postorder(root.left)
            yield from self.subtree_postorder(root.right)
            yield root


    def inorder(self):
        yield from self.subtree_inorder(self.root)

    def subtree_inorder(self, root):
        if(root is None):
            return
        else:
            yield from self.subtree_inorder(root.left)
            yield root
            yield from self.subtree_inorder(root.right)


    def breadth_first(self):
        if (self.is_empty()):
            return
        line = ArrayQueue.ArrayQueue()
        line.enqueue(self.root)
        while (line.is_empty() == False):
            curr_node = line.dequeue()
            yield curr_node
            if (curr_node.left is not None):
                line.enqueue(curr_node.left)
            if (curr_node.right is not None):
                line.enqueue(curr_node.right)

    def __iter__(self):
        for node in self.breadth_first():
            yield node.data

我在此处添加了 LinkedBinaryTree 类的代码。广度遍历方法的实现中使用的ArrayQueue类只是一个使用Python列表作为底层数据结构的基本队列。

Answer 1

您的代码存在两个问题:

• 您逐一处理了字符，但可能存在多位数字(通过将表达式拆分为列表来修复)
• 您没有考虑到链式运算符表达式可能比标准增量更长的事实(通过向 Node 添加 size 属性来修复

这是新的 Node 类

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.parent = None
        self.left = left
        if (self.left is not None):
            self.left.parent = self
        self.right = right
        if (self.right is not None):
            self.right.parent = self

    @property
    def size(self):
        l = 1
        if self.left is not None:
            l += self.left.size
        if self.right is not None:
            l += self.right.size
        return l

这是新的树创建者

def create_expression_tree(prefix_exp_str):

    expr_lst = prefix_exp_str.split(" ")

    op = {'+': None, '-': None, '*': None, '/': None}

    def create_expression_tree_helper(prefix_exp, start_pos):
        start_pos += 1
        elem = prefix_exp[start_pos]

        node = None

        if elem not in op:
            node = LinkedBinaryTree.Node(int(elem))
        else:
            left = create_expression_tree_helper(prefix_exp, start_pos)
            incr = left.size
            right = create_expression_tree_helper(prefix_exp, start_pos+incr)
            node = LinkedBinaryTree.Node(elem, left, right)

        return node

    tree = LinkedBinaryTree(create_expression_tree_helper(expr_lst, -1))

    return tree

编辑这是一个不需要修改Node类的版本

def create_expression_tree(prefix_exp_str):

    expr_lst = prefix_exp_str.split(" ")

    op = {'+': None, '-': None, '*': None, '/': None}

    def create_expression_tree_helper(prefix_exp, start_pos):
        start_pos += 1
        elem = prefix_exp[start_pos]

        node = None
        size = 1

        if elem not in op:
            node = LinkedBinaryTree.Node(int(elem))
        else:
            left, left_size   = create_expression_tree_helper(prefix_exp, start_pos)
            right, right_size = create_expression_tree_helper(prefix_exp, start_pos+left_size)

            node  = LinkedBinaryTree.Node(elem, left, right)
            size += left_size + right_size

        return node, size

    tree = LinkedBinaryTree(create_expression_tree_helper(expr_lst, -1)[0])

    return tree