#! /usr/bin/python3
# ==================================================================
# create a binary tree
#
# The node class in this code has only one data item. It is the
# node's data and also is the node's unique key. In the
# "real world" a node would contain much more data and perhaps
# have a unique key that is seperate from the node's data.
#
# Note: A node's unique key is used to position a node's place
# in the tree.
# ==================================================================
import numpy as np
from random import randint
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.parent = None
def PrintNode(self,single_line = True):
d = 'None' if self.data == None else self.data
l = 'None' if self.left == None else self.left.data
r = 'None' if self.right == None else self.right.data
p = 'None' if self.parent == None else self.parent.data
if single_line:
print('(d={},l={},r={},p={})'.format(d,l,r,p))
else:
print('data = {}'.format(d))
print('left = {}'.format(l))
print('right = {}'.format(r))
print('parent = {}'.format(p))
class BinaryTree:
# ---- init object ------------------------------------
def __init__(self):
self.root = None
# ---- find maximum tree height -----------------------
def height(self):
return self._height(self.root,0)
def _height(self,curnode,curheight):
if curnode == None: return curheight
left_height = self._height(curnode.left,curheight+1)
right_height = self._height(curnode.right,curheight+1)
return max(left_height,right_height)
# ---- insert object into tree ------------------------
def insert(self,newnode):
if self.root == None:
self.root = newnode
return True
else:
return self._insert(newnode,self.root)
def _insert(self,newnode,curnode):
if newnode.data < curnode.data:
if curnode.left == None:
newnode.parent = curnode
curnode.left = newnode
return True
else:
return self._insert(newnode,curnode.left)
elif newnode.data > curnode.data:
if curnode.right == None:
newnode.parent = curnode
curnode.right = newnode
return True
else:
return self._insert(newnode,curnode.right)
else:
print("Tree node {} already in tree".format(curnode.data))
return False
# ---- print tree -------------------------------------
def PrintTree(self):
if self.root == None:
print("tree empty")
else:
self._PrintTree(self.root)
def _PrintTreeNode(self,node):
print("{}".format(str(node.data)))
def _PrintTree(self,curnode):
if curnode.left:
self._PrintTree(curnode.left)
print("{}".format(curnode.data))
if curnode.right:
self._PrintTree(curnode.right)
# ---- print tree structure ---------------------------
def PrintTreeStructure(self):
if self.root == None:
print("tree empty")
else:
self._PrintTreeStructure(self.root,1)
def _PrintTreeStructure(self,curnode,n):
if curnode.right:
self._PrintTreeStructure(curnode.right,n+1)
pd = 'None' if curnode.parent == None else curnode.parent.data
print('{} {} (p={})'.format('---'*n,curnode.data,pd))
if curnode.left:
self._PrintTreeStructure(curnode.left,n+1)
# ---- count all tree nodes ---------------------------
def count_nodes(self):
return self._count_nodes(self.root)
def _count_nodes(self,curnode):
if curnode == None:
return 0
return 1 + self._count_nodes(curnode.left) + \
self._count_nodes(curnode.right)
# ------------------------------------------------------------------
# main testing
# ------------------------------------------------------------------
if __name__ == '__main__':
# ---- create a worst case tree
def worst_case_tree(tree):
values = [10,9,7,5,4,3,2,1,11,12,13,14,15,16,17]
print(values)
for v in values:
tree.insert(Node(int(v)))
return tree
# ---- create the tree from my documentation
def my_doc_tree(tree):
values = [30,40,50,55]
print(values)
for v in values:
tree.insert(Node(int(v)))
return tree
# ---- create a tree with random nodes
def random_nodes(tree,elms=20,maxint=99):
for _ in range(elms):
i = randint(1,maxint)
##print('RandomInt = {}'.format(i))
tree.insert(Node(i))
# ---- create a tree with no root node
def no_root_node(tree):
pass
# ---- create a tree wih only a root node
def only_root_node(tree):
tree.insert(Node(100))
# ---- create a tree wih two nodes
def root_node_plus_one(tree):
tree.insert(Node(100))
tree.insert(Node(200))
# ---- print all tree nodes
def print_all_nodes(tree):
if tree.root == None:
print("tree empty")
else:
_print_all_nodes(tree.root)
def _print_all_nodes(curnode):
if curnode.right:
_print_all_nodes(curnode.right)
curnode.PrintNode()
if curnode.left:
_print_all_nodes(curnode.left)
print("\n----create-tree--------------------------------------")
tree = BinaryTree()
##no_root_node(tree)
##only_root_node(tree)
##root_node_plus_one(tree)
#my_doc_tree(tree)
worst_case_tree(tree)
##random_nodes(tree,20,99)
print("\n----print-tree-(in-order)----------------------------")
tree.PrintTree()
print("\n----max-tree-height----------------------------------")
print("Maximum height of tree is {}".format(tree.height()))
print("\n----print-tree-structure-(view-it-sideways)----------")
tree.PrintTreeStructure()
print("\n----print-all-nodes----------------------------------")
print_all_nodes(tree)
print("\n----count-nodes--------------------------------------")
print('number of tree nodes = {}'.format(tree.count_nodes()))