Representation of LinkedBinaryTree that should be outputted
import 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='')
I implemented my own binary tree class which is shown below. Preorder() is a generator for my LinkedBinaryTree that gives the values of the tree in prefix order. With this code, I'm outputting *2+-151 but it should be outputting *2+-1564 if the binary expression tree has been created correctly. I'm aware that there is an issue with numbers greater than 1 digit, but I'm not sure how to fix it without compromising the runtime (ie. using slicing). Also I'm not sure why it is omitting some of the tokens. Any ideas? (The implementation must run in linear time and use no additional parameters in the helper function I've defined).
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
I added the code here for LinkedBinaryTree class. The ArrayQueue class that is used in the implementation of the breadth traversal method is just a basic queue using a Python list as the underlying data structure.
The two issues with your code were:
size property to NodeSo here is the new 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
and here is the new tree creator
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 here is a version that does not require to modify the 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