在 Python 中给定前缀表示法中的字符串表达式递归创建二叉树
Recursively Creating a Binary Tree Given a String Expression in Prefix Notation in Python
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='')
我实现了自己的二叉树 class，如下所示。 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 添加了代码 class。广度遍历方法实现中使用的ArrayQueueclass只是一个使用Python列表作为底层数据结构的基本队列。
您的代码的两个问题是：
- 你一个一个地处理了字符，而可能存在几个数字（通过将表达式拆分为列表来修复）
- 你没有考虑到链式运算符表达式可能比你的标准增量更长的事实（通过添加
size 属性 到 Node
所以这是新的 Node class
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
EDIT这里是不需要修改的版本 Node class
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
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='')
我实现了自己的二叉树 class，如下所示。 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 添加了代码 class。广度遍历方法实现中使用的ArrayQueueclass只是一个使用Python列表作为底层数据结构的基本队列。
您的代码的两个问题是：
- 你一个一个地处理了字符，而可能存在几个数字（通过将表达式拆分为列表来修复）
- 你没有考虑到链式运算符表达式可能比你的标准增量更长的事实（通过添加
size属性 到Node
所以这是新的 Node class
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
EDIT这里是不需要修改的版本 Node class
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