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.