Htykuut

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:

• you processed the characters one by one while several-digit numbers could be present (fixed by splitting the expression to a list)


• you did not account for the fact that chained operator expressions could be longer that just your standard increment (fixed by adding a size property to Node
  

So 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