Nocturnal Child
Reputation: 19
Having an issue with my Level Order Traversal function in Python
EDIT: I have overall finished the original problem. However I have a small problem. I will print out all of my code to show you all. The objective is print out all of the binary search tree parts in a list, plus every empty spot. The empty spots are represented by None. The problem is, the code prints out the list, however, there are three extra Nones at the end. It would be best if you just took the code and ran it on your own pc, as it is extremely hard to explain all of this.
class TreeNode:
def __init__(self, value, left_child=None, right_child=None, parent=None):
self.value = value
self.left_child = left_child
self.right_child = right_child
self.parent = parent
def __repr__(self):
return '{}'.format(self.value)
class binary_search_tree:
def __init__(self):
self.root=None
def insert(self, value):
if self.root==None:
self.root=TreeNode(value)
else:
self._insert(value, self.root)
def _insert(self, value, current_node):
if value < current_node.value:
if current_node.left_child==None:
current_node.left_child=TreeNode(value)
current_node.left_child.parent=current_node #set parent
else:
self._insert(value, current_node.left_child)
elif value > current_node.value:
if current_node.right_child==None:
current_node.right_child=TreeNode(value)
current_node.right_child.parent=current_node #set parent
else:
self._insert(value, current_node.right_child)
else:
print("Value already in tree")
def height(self):
if self.root!=None:
return self._height(self.root,0)
else:
return 0
def _height(self, current_node, current_height):
if current_node==None: return current_height
left_height=self._height(current_node.left_child,current_height+1)
right_height=self._height(current_node.right_child,current_height+1)
return max(left_height, right_height)
def height_iter(self):
current_node = self.root
if self.root != None:
pass
def print_tree(self):
line = []
if self.root!=None:
line.append(self._print_tree(self.root))
print(line)
def _print_tree(self, current_node):
if current_node!=None:
self._print_tree(current_node.left_child)
print(str(current_node.value))
if current_node.left_child!=None:
print(str(current_node.left_child.value))
if current_node.right_child!=None:
print(str(current_node.right_child.value))
#node.display(current_node)
self._print_tree(current_node.right_child)
#returns the node with the specified input value
def find(self, value):
if self.root!=None:
return self._find(value, self.root)
else:
return None
#private find
def _find(self, value, current_node):
if value==current_node.value:
return current_node
elif value<current_node.value and current_node.left_child!=None:
return self._find(value, current_node.left_child)
elif value>current_node.value and current_node.right_child!=None:
return self._find(value, current_node.right_child)
def delete_value(self, value):
return self.delete_node(self.find(value))
def delete_node(self, node):
#returns node with min in tree rooted at input node
def min_value_node(n):
current=n
while current.left_child!=None:
current=current.left_child
return current
#returns the number of children for the specified node
def num_children(n):
num_children=0
if n.left_child!=None:
num_children+=1
if n.right_child!=None:
num_children+=1
return num_children
#get the parent of the node to be deleted
node_parent = node.parent
#get the number of children of the node to be deleted
node_children = num_children(node)
#CASE 1 (node has no children)
if node_children == 0:
#remove the reference to the node from the parent
if node_parent.left_child==node:
node_parent.left_child=None
else:
node_parent.right_child=None
#CASE 2 (node has 1 child)
if node_children == 1:
#get the populated node
if node.left_child!=None:
child=node.left_child
else:
child=node.right_child
#replace the mode to be deleted with its child
if node_parent.left_child==node:
node_parent.left_child=child
else:
node_parent.right_child=child
child.parent=node_parent
#correct the parent pointer in node
child.parent=node_parent
#CASE 3 (node has two children)
if node_children == 2:
#get the in order successor of the deleted node
successor=min_value_node(node.right_child)
#copy the in order successor value to the node formerly
#holding the value we tried to delete.
node.value=successor.value
#delete in order successor now that the value copied to other node
self.delete_node(successor)
#returns true if the value exists in the tree
def search(self, value):
if self.root!=None:
return self._search(value, self.root)
else:
return False
def _search(self, value, current_node):
if value==current_node.value:
return True
elif value<current_node.value and current_node.left_child!=None:
return self._search(value, current_node.left_child)
elif value>current_node.value and current_node.right_child!=None:
return self._search(value, current_node.right_child)
return False
return type(value)
# def sibling(self,root):
# while root != self.root:
# if root < self.root:
# root = self.root.left_child
def search_iter(self, value):
# if self.root.value == None:
# return False
current_node = self.root
if current_node.value == None:
return False
else:
while (value != current_node.value):
if value < current_node.value:
if current_node.left_child != None:
current_node = current_node.left_child
else:
return False
elif value > current_node.value:
if current_node.right_child != None:
current_node = current_node.right_child
else:
return False
return True
#find the minimum element in the tree
def min(self):
if self.root == None:
return False
current_node = self.root
while (current_node.left_child != None):
current_node = current_node.left_child
return current_node.value
def min_rec(self):
if self.root != None:
return self._min_rec(self.root.left_child)
else:
return self.root.value
def _min_rec(self, current_node):
if current_node == None:
return False
elif current_node.left_child == None:
return current_node.value
else:
return self._min_rec(current_node.left_child)
def max_rec(self):
if self.root != None:
return self._max_rec(self.root.right_child)
else:
return self.root.value
def _max_rec(self, current_node):
if current_node.value == None:
return False
elif current_node.right_child == None:
return current_node.value
else:
return self._max_rec(current_node.right_child)
# while (current_node.left_child != None):
# current_node = current_node.left_child
# return current_node.value
def max(self):
if self.root == None:
return False
current_node = self.root
while (current_node.right_child != None):
current_node = current_node.right_child
return current_node.value
# Function to print level order traversal of tree
def printLevelOrder(self):
from collections import deque
level_lst = []
queue = deque([ self.root ])
while len(queue):
node = queue.popleft()
if node != None:
level_lst.append(node.value)
else:
while node == None:
level_lst.append(None)
node = queue.popleft()
if node != None:
level_lst.append(node.value)
if len(queue) == 0:
break
if node == None:
if len(queue) == 0:
print (level_lst)
break
if node.left_child != None:
queue.append(node.left_child)
else:
queue.append(None)
if node.right_child != None:
queue.append(node.right_child)
else:
queue.append(None)
# root = self.root
# level_lst = []
# if not root:
# return level_lst
# stack = []
# while stack:
# stack.append(root.value)
# root = self.root.left_child
# level = stack.pop()
# curr_level = []
# next_level = []
# for node in level:
# curr_level.append(node.value)
# if node.left_child:
# next_level.append(node.left_child)
# if node.right_child:
# next_level.append(node.right_child)
# level_lst.append(curr_level)
# if next_level:
# stack.append(next_level)
# return level_lst
# root = self.root
# level_lst = []
# queue = []
# queue.append(root.value)
# heigh = self.height()
# while queue:
# count = len(queue)
# level_lst.append(root)
# queue.append(root.value)
# while count > 0:
# queue.append(root.value)
# queue.pop(root.value)
# level_lst.append(root.value)
# if root.left_child == None:
# if root.right_child != None:
# root = root.right_child
# queue.append(root.value)
# elif root.right_child == None:
# root = root.parent.right_child
# else:
# root = root.left_child
# queue.append(root.value)
# print(level_lst)
# def printLevelOrder(self,root):
# if self.root != root:
# h = tree.height()
# for i in range(1, h+1):
# self.printGivenLevel(self.root.value, i)
# def printGivenLevel(self, root , level):
# if root is None:
# return
# if level == 1:
# print(root,end=" ")
# elif level > 1:
# self.printGivenLevel(self.root.left_child , level-1)
# self.printGivenLevel(self.root.right_child , level-1)
#manually populate tree
tree = binary_search_tree()
#Fill tree with 100 random integers
def fill_tree(tree, num_elems, max_int):
from random import randint
for _ in range(num_elems):
cur_elem = randint(0, max_int)
tree.insert(cur_elem)
return tree
#function to draw the tree
def drawtree(root):
def height(root):
return 1 + max(height(root.left_child), height(root.right_child)) if root else -1
def jumpto(x, y):
t.penup()
t.goto(x, y)
t.pendown()
def draw(node, x, y, dx):
if node:
t.goto(x, y)
jumpto(x, y-20)
t.write(node.value, align='center', font=('Arial', 12, 'normal'))
draw(node.left_child, x-dx, y-60, dx/2)
jumpto(x, y-20)
draw(node.right_child, x+dx, y-60, dx/2)
import turtle
t = turtle.Turtle()
t.speed(0); turtle.delay(2)
h = height(root)
jumpto(0, 30*h)
draw(root, 0, 30*h, 40*h)
t.hideturtle()
turtle.mainloop()
####################################
#BUILD A TREE (manual or automatic)
####################################
#Automatic Fill
# tree = binary_search_tree()
# tree = fill_tree(tree,100,100)
# #manually populate tree
# tree = binary_search_tree()
#order of insertion matters in terms of the tree you get : monotonically decreasing insertions
# tree.insert(12)
# tree.insert(10)
# tree.insert(7)
# tree.insert(5)
# tree.insert(2)
# tree.insert(1)
# #tree.insert(0)
# #add some extras and see what happens
# # tree.insert(4)
# # tree.insert(3)
# # tree.insert(7)
# tree.insert(20)
#here's another order of insertion, more mixed - try both to see the result
tree.insert(5)
tree.insert(1)
tree.insert(3)
tree.insert(2)
tree.insert(10)
tree.insert(0)
tree.insert(20)
tree.insert(7)
tree.insert(4)
#query the tree (for monotonically decreasing insertions)
# print(tree.root)
# print(tree.root.left_child)
# print(tree.root.left_child.left_child)
# print(tree.root.left_child.left_child.left_child)
# print(tree.root.left_child.left_child.left_child.left_child)
# print(tree.root.left_child.left_child.left_child.left_child.left_child)
# print(tree.root.left_child.left_child.left_child.left_child.left_child.left_child)
#tree height
print("tree height: ",str(tree.height()))
# print("sibling of 10 is",tree.sibling(10))
#minimum element
print("minimum element in tree: ", tree.min())
print("maximum element in tree: ", tree.max_rec())
#print("maximum element in tree: ", tree.max())
print(tree.search_iter(1))
tree.printLevelOrder()
#print(tree.find(10))
#tree.delete_value(3)
#tree.delete_value(2)
#############
#DRAW A TREE
#############
drawtree(tree.root)
Upvotes: 0
Views: 110
Answers (1)
ikegami
Reputation: 386706
You simply need the following:
from collections import deque
def printLevelOrder(self):
queue = deque([ self.root ])
while len(queue):
node = queue.popleft()
print(node.value)
if node.left_child != None:
queue.append( ( node.left_child)
if node.right_child != None:
queue.append(node.right_child)
If you also want the level,
from collections import deque
def printLevelOrder(self):
queue = deque([ ( 0, self.root ) ])
while len(queue):
state = queue.popleft()
level = state[0]
node = state[1]
print(level, node.value)
if node.left_child != None:
queue.append( ( level+1, node.left_child ) )
if node.right_child != None:
queue.append( ( level+1, node.right_child ) )
It's yet another simple modification to return values grouped by level.
from collections import deque
def printLevelOrder(self):
grouped = []
queue = deque([ ( 0, self.root ) ])
while len(queue):
state = queue.popleft()
level = state[0]
node = state[1]
if len(grouped) == level:
grouped.append([])
grouped[level].append(node.value)
if node.left_child != None:
queue.append( ( level+1, node.left_child ) )
if node.right_child != None:
queue.append( ( level+1, node.right_child ) )
return grouped
Upvotes: 1
Related Questions
- Python Leetcode BST: Level Order Traversal
- Search Binary Tree in Python (In-order traversal error)
- Error while traversing binary search tree - Python
- Binary Tree Level Order Traversal in Python
- How can I make my Binary Tree's search/traversal method work?
- Breadth First Search does not return the correct ordering for nodes
- NameError When Implementing Inorder Traversal
- Traversing a binary tree in level order in python
- Level Order Traversal - Tree
- Inorder, Preorder, Postorder traversal not working