btree_7.py

#! /usr/bin/python3
# ==================================================================
# create an binary search tree - show tree depth
#
# Notes:
# 1. To simplify the code, all of the nodes have a common key
#    (an integer) for node comparison/insertion. (A sophisticated
#    comparison method could be developed.)
# 2. Nodes are created outside of the binary tree code and inserted
#    into the tree. Thus, The binary tree code is not responsible
#    for the node's correctness.
# 3. Perhaps one way to make the code less confusing to read
#    is for each node have a method to get it's key?
# ==================================================================

class Node:
    def __init__(self, data):
        self.data                    = data
        self.left                    = None
        self.right                   = None
        self.parent                  = None
        self.left_max_subtree_depth  = 0
        self.right_max_subtree_depth = 0

class BinaryTree:

    # ---- init object ------------------------------------

    def __init__(self):
        self.root = None

    # ---- find maximum tree height -----------------------

    def height(self):
        if self.root != None:
            return self._height(self.root,0)
        else:
            return 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
        else:
            self._insert(newnode,self.root)
        if (self.root.left_max_subtree_depth < 0 or
            self.root.right_max_subtree_depth < 0):
            return False
        else:
            return True

    def _insert(self,newnode,curnode):
        if newnode.data < curnode.data:
            if curnode.left == None:
                newnode.parent = curnode
                ##newnode.left_max_subtree_depth = 0
                curnode.left = newnode
                curnode.left_max_subtree_depth = 1
            else:
                d = self._insert(newnode,curnode.left)
                if d < 0: return d
                curnode.left_max_subtree_depth = d + 1
        elif newnode.data > curnode.data:
            if curnode.right == None:
                newnode.parent = curnode
                ##newnode.right_max_subtree_depth = 0
                curnode.right = newnode
                curnode.right_max_subtree_depth = 1
            else:
                d = self._insert(newnode,curnode.right)
                if d < 0: return d
                curnode.right_max_subtree_depth = d + 1
        else:
            print("Tree node " + str(curnode.data) +
                  " already in the tree")
            return -1
        return max(curnode.left_max_subtree_depth,
                   curnode.right_max_subtree_depth)


    # ---- 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)
        if curnode.parent:
            print('{} {}   (p={},ld={},rd={})'.format('---'*n,
                str(curnode.data),
                str(curnode.parent.data),
                str(curnode.left_max_subtree_depth),
                str(curnode.right_max_subtree_depth)))
        else:
            print('{} {}   (p=None,ld={},rd={})'.format('---'*n,
                str(curnode.data),
                str(curnode.left_max_subtree_depth),
                str(curnode.right_max_subtree_depth)))
        if curnode.left:
            self._PrintTreeStructure(curnode.left,n+1)


# ------------------------------------------------------------------
# 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

print("----create-tree--------------------------------------")

tree = BinaryTree()
worst_case_tree(tree)

print("----print-tree-(in-order)----------------------------")

tree.PrintTree()
print("Maximum height of tree is {}".format(tree.height()))

print("----print-tree-structure-(view-it-sideways)----------")

tree.PrintTreeStructure()

print("-----------------------------------------------------")