classBinaryTree:
def__init__(self, root):
self.key=root
self.left_child=None
self.right_child=None
definsert_left(self, new_node):
ifself.left_child==None:
self.left_child=BinaryTree(new_node)
else:
t=BinaryTree(new_node)
t.left_child=self.left_child
self.left_child=t
definsert_right(self, new_node):
ifself.right_child==None:
self.right_child=BinaryTree(new_node)
else:
t=BinaryTree(new_node)
t.right_child=self.right_child
self.right_child=t
defget_right_child(self):
returnself.right_child
defget_left_child(self):
returnself.left_child
defset_root_val(self, obj):
self.key=obj
defget_root_val(self):
returnself.key
r=BinaryTree('a')
print(r.get_root_val())
print(r.get_left_child())
r.insert_left('b')
print(r.get_left_child())
print(r.get_left_child().get_root_val())
r.insert_right('c')
print(r.get_right_child())
print(r.get_right_child().get_root_val())
r.get_right_child().set_root_val('hello')
print(r.get_right_child().get_root_val())
# -*- coding: utf-8 -*-
# test tree as below:
''' 1 / \ / \ / \ / \ 2 3 / \ / \ / \ / \ 4 5 6 N / \ / \ / \ 7 N N N 8 9 / \ / \ / \ N N N N N N '''
fromcollectionsimportnamedtuple
fromioimportStringIO
#define the node structure
Node=namedtuple('Node', ['data','left','right'])
#initialize the tree
tree=Node(1,
Node(2,
Node(4,
Node(7,None,None),
None),
Node(5,None,None)),
Node(3,
Node(6,
Node(8,None,None),
Node(9,None,None)),
None))
#read and write str in memory
output=StringIO()
#read the node and write the node's value
#if node is None, substitute with 'N '
defvisitor(node):
ifnodeisnotNone:
output.write('%i '%node.data)
else:
output.write('N ')
#traversal the tree with different order
deftraversal(node, order):
ifnodeisNone:
visitor(node)
else:
op={
'N':lambda: visitor(node),
'L':lambda: traversal(node.left, order),
'R':lambda: traversal(node.right, order),
}
forxinorder:
op[x]()
#traversal the tree level by level
deftraversal_level_by_level(node):
ifnodeisnotNone:
current_level=[node]
whilecurrent_level:
next_level=list()
fornincurrent_level:
iftype(n)isstr:
output.write('N ')
else:
output.write('%i '%n.data)
ifn.leftisnotNone:
next_level.append(n.left)
else:
next_level.append('N')
ifn.rightisnotNone:
next_level.append(n.right)
else:
next_level.append('N ')
output.write('\n')
current_level=next_level
if__name__=='__main__':
fororderin['NLR','LNR','LRN']:
iforder=='NLR':
output.write('this is preorder traversal:')
traversal(tree, order)
output.write('\n')
eliforder=='LNR':
output.write('this is inorder traversal:')
traversal(tree, order)
output.write('\n')
else:
output.write('this is postorder traversal:')
traversal(tree, order)
output.write('\n')
output.write('traversal level by level as below:'+'\n')
traversal_level_by_level(tree)
print(output.getvalue())
