Home > database >  there is some error in this recursive binarytree function type
there is some error in this recursive binarytree function type

Time:02-11

I tried to check and fix the code but I just can't find what is the problem anywhere with this code

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()
    
    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)


class BinaryTree:
    def __init__(self, root):
        self.key = root
        self.left_child = None
        self.right_child = None

    def insert_left(self, new_node):
        if self.left_child == None:
            self.left_child = BinaryTree(new_node)
        else:
            t = BinaryTree(new_node)
            t.left_child = self.left_child
            self.left_child = t

    def insert_right(self, new_node):
        if self.right_child == None:
            self.right_child = BinaryTree(new_node)
        else:
            t = BinaryTree(new_node)
            t.right_child = self.right_child
            self.right_child = t

    def get_right_child(self):
        return self.right_child

    def get_left_child(self):
        return self.left_child
    
    def set_root_val(self, obj):
        self.key = obj

    def get_root_val(self):
        return self.key

    def preorder(tree):
        if tree:
            print(tree.get_root_val())
            preorder(tree.get_left_child())
            preorder(tree.get_right_child())

    def postorder(tree):
        if tree != None:
            postorder(tree.get_left_child())
            postorder(tree.get_right_child())
            print(tree.get_root_val())

    def inorder(tree):
        if tree != None:
            inorder(tree.get_left_child())
            print(tree.get_root_val())
            inorder(tree.get_right_child())


def build_parse_tree(fp_exp):
    fp_list = fp_exp.split()
    p_stack = Stack()
    e_tree = BinaryTree('')
    p_stack.push(e_tree)
    current_tree = e_tree
    for i in fp_list:
        if i == '(':
            current_tree.insert_left('')
            p_stack.push(current_tree)
            current_tree = current_tree.get_left_child()
        elif i not in [' ', '-', '*', '/', ')']:
            current_tree.set_root_val(int(i))
            parent = p_stack.pop()
            current_tree = parent
        elif i in [' ', '-', '*', '/']:
            current_tree.set_root_val(i)
            current_tree.insert_right('')
            p_stack.push(current_tree)
            current_tree = current_tree.get_right_child()
        elif i == ')':
            current_tree = p_stack.pop()
        else:
            raise ValueError
    return e_tree

if __name__ == '__main__':
    pt = build_parse_tree("( ( 10   5 ) * ( 3 - 2 ) )")
    pt.postorder()

I run the code and it's return me with this

name 'postorder' is not defined
  File "G:\VSCode\PythonVS\BinaryTree6Feb2022.py", line 63, in postorder
    postorder(tree.get_left_child())
  File "G:\VSCode\PythonVS\BinaryTree6Feb2022.py", line 102, in <module>
    pt.postorder()

I tried to make it a recursive function but I don't know what am I doing wrong or what might I be missing. I'm still checking the code but I just can't find missing things

CodePudding user response:

Your traversal methods preorder, postorder and inorder have declarations that you would expect for standalone functions, but they are indented to be part of the class and so they look like methods.

The easiest fix is to move them out of the class block and replace the call in your main program with postorder(pt), and it will work.

If you prefer to have them as methods on your class, so that you can make the call like pt.postorder(), then rename the parameter tree to self (as that is the common practice), make the recursive calls in method-notation, and move the if condition before the recursive calls:

    def postorder(self):
        print(self.get_root_val())
        if self.get_left_child():
            self.get_left_child().postorder()
        if self.get_right_child():
            self.get_right_child().postorder()

For completeness sake, I provide also an alternative that leaves the if condition at the start, but then you must use another syntax on the recursive calls, as you cannot call a method on None:

    def postorder(self):
        if self:
            print(self.get_root_val())
            BinaryTree.postorder(self.get_left_child())
            BinaryTree.postorder(self.get_right_child())

But this is not normal practice in Python.

  • Related