solution_060a.py

#!/usr/bin/python3
# ====================================================================
# binary tree - display tree
# ====================================================================

alignment_guide = \
    '         1       2           3         4'        +\
    '         5       6           7         8' + '\n' +\
    '1234567890123456789012345678901234567890'        +\
    '1234567890123456789012345678901234567890'

# --------------------------------------------------------------------
# ---- tree node class
# --------------------------------------------------------------------

class Node:

    def __init__(self,value):
        self.value  = value     # node value
        self.parent = None      # parent node
        self.left   = None      # left child
        self.right  = None      # right child
        self.depth  = 0         # depth of node from tree root


# --------------------------------------------------------------------
# ---- display node
# --------------------------------------------------------------------

def display_node(node):
        
    print(f'------ node {node.value:<3}')
    if node.parent is None:
        print('parent None')
    else:
        print(f'parent {node.parent.value}')        
    if node.left is None:
        print('left   None')
    else:
        print(f'left   {node.left.value}')
    if node.right is None:
        print('right  None')
    else:
        print(f'right  {node.right.value}')
    print(f'depth  {node.depth}')
    print(f'---------------')

# --------------------------------------------------------------------
# ---- display tree nodes (for debugging)
# ---- (call support function recursively)
# --------------------------------------------------------------------

def display_nodes(tree):

    # ---- support function
    def traverse(node):
        display_node(node)        
        if node.right is not None:
            traverse(node.right)
        if node.left is not None:
            traverse(node.left)

    print()
    print('==============================')
    traverse(tree)
    print('==============================')

        
# --------------------------------------------------------------------
# ---- calculate the maximum height of the tree
# ---- (call function recursively)
# --------------------------------------------------------------------

def height(node):

    if node is None: return 0
    h_left  = height(node.left)
    h_right = height(node.right)
    if h_left > h_right:
        return h_left + 1
    return h_right + 1


# --------------------------------------------------------------------
# ---- calculate a node's depth from the root node
# --------------------------------------------------------------------

def node_depth(node):
    dep = 0
    while node.parent is not None:
        dep += 1
        node = node.parent
    return dep


# --------------------------------------------------------------------
# ---- add a node to a tree (below the parent node)
# ---- (call function recursively)
# --------------------------------------------------------------------

def add_node(node,parent):

    if node.value < parent.value:
        if parent.left == None:
            parent.left = node
            node.parent = parent
            node.depth = node_depth(node)
            return
        add_node(node,parent.left)
        return
    
    if parent.right == None:
        parent.right = node
        node.parent = parent
        node.depth = node_depth(node)
        return
    add_node(node,parent.right)
    return        


# --------------------------------------------------------------------
# ---- display a binary tree (horizontally)
# ---- (call function recursively)
# --------------------------------------------------------------------

def display_tree(max_width,tree,indent=0):

    if tree is None: return

    # ---- support function
    def print_line(max_width,node,indent):
        line = ' '*indent + '-'*(node.depth*4) + ' ' + str(node.value)
        if len(line) > max_width: return
        print(line)

    # ---- support function
    def traverse(max_width,node,indent):
        if node is None: return
        traverse(max_width,node.right,indent)
        print_line(max_width,node,indent)
        traverse(max_width,node.left,indent)
   
    traverse(max_width,tree,indent)      


# --------------------------------------------------------------------
# ---- display tree nodes in descending order (for debugging)
# ---- (call function recursively)
# --------------------------------------------------------------------

def visit_nodes_in_tree_order(tree):

    # ---- support function
    def display(node):
        print(f'node={node.value:<4}  depth={node.depth}')

    # ---- support function
    def traverse(node):
        if node is None: return
        traverse(node.right)
        display(node)
        traverse(node.left)

    traverse(tree)

# --------------------------------------------------------------------
# ---- main
# --------------------------------------------------------------------
 
if __name__ == '__main__':

    max_width = 79
    tree      = None
    ##values  = [1,2,3,4,5,6,7,8,9]
    values    = [23,11,8,12,45,456,40,500,499,501]

    # ---- build a tree
    
    tree = Node(values[0])      # root node
    
    for v in values[1:]:
        add_node(Node(v),tree)

    # ---- display tree 'stuff'

    #display_nodes(tree)

    #print('******************************')
    #visit_nodes_in_tree_order(tree)
    #print('******************************')

    display_tree(max_width,tree)