#!/usr/bin/python3 # ================================================================ # display a tree structure # ================================================================ import random # ---------------------------------------------------------------- # ---- class definition: tree node # ---------------------------------------------------------------- class Node: def __init__(self,parent,sym): self.parent = parent self.sym = sym self.left = None self.right = None def __str__(self): return str(self.sym) # ---------------------------------------------------------------- # ---- add a node to a sub tree below a parent node # ---------------------------------------------------------------- def add_node(node,parent): if node.sym < parent.sym: if parent.left == None: parent.left = node node.parent = parent return add_node(node,parent.left) return if parent.right == None: parent.right = node node.parent = parent return add_node(node,parent.right) return # ---------------------------------------------------------------- # ---- traverse a tree - results is a list of tree nodes # ---------------------------------------------------------------- def traverse_tree(node,nodes): if node is None: return traverse_tree(node.left,nodes) if nodes is not None: nodes.append(node) traverse_tree(node.right,nodes) return # ---------------------------------------------------------------- # ---- create a balanced tree # ---------------------------------------------------------------- def construct_balanced_tree(root): def balanced_tree_util(nodes,start,end,parent): if start > end: return None mid = (start + end)//2 node = nodes[mid] if parent.sym is None: parent.sym = node.sym parent.parent = None else: add_node(Node(None,node.sym),parent) balanced_tree_util(nodes,start,mid-1,parent) balanced_tree_util(nodes,mid+1,end,parent) return nodes = [] traverse_tree(root,nodes) sorted_nodes = sorted(nodes,key=lambda node:node.sym) new_root = Node(None,None) n = len(sorted_nodes) balanced_tree_util(sorted_nodes,0,n-1,new_root) return new_root # ---------------------------------------------------------------- # ---- print node # ---------------------------------------------------------------- def print_node(node,title=None): if title is None: title = 'Node: ' if node is None: print(f'{title}None'); return print(f'{title}sym={node.sym} ' +\ f'parent={node.parent} ' +\ f'left={node.left} ' +\ f'right={node.right}') return # ---------------------------------------------------------------- # ---- print a "new fashion" fancy tree # ---------------------------------------------------------------- def print_fancy_tree(node): elbow = '+--' pipe = '| ' tee = '|--' blank = ' ' def print_fancy_tree_util(node,header): if node.left is not None: if node.right is not None: print(header+tee+node.left.sym) l_header = header + pipe else: print(header+elbow+node.left.sym) lheader = header + blank print_fancy_tree_util(node.left,lheader) if node.right is not None: if node.left is not None: print(header+elbow+node.right.sym) r_header = header + blank else: print(header+elbow+node.right.sym) rheader = header + blank print_fancy_tree_util(node.right,r_header) return if node is None: return print(node) print_fancy_tree_util(node,'') return # ---------------------------------------------------------------- # ---- print an "old fashion" dash tree # ---------------------------------------------------------------- def print_dash_tree(node, dash='-', level=0): if node is None: return print(f'[{level}] ' + dash*(level*3) +\ '(' + str(node.sym) + ')') level += 1 print_dash_tree(node.left,dash,level) print_dash_tree(node,dash,level) return # ---------------------------------------------------------------- # ---- build random test tree of symbols # ---------------------------------------------------------------- def build_random_test_tree(symbols:list): if len(symbols) < 1: return None root = Node(None,symbols[0]) if len(symbols) > 1: build_random_sub_trees(root,symbols,0) return root def build_random_sub_trees(parent:Node, symbols:list, idx:int) -> int: if parent is None: return idx # no parent node? if idx+1 >= len(symbols): return idx # any symbol remaining? nleft = nright = False if random.randint(0,100) < 50: nleft = True if random.randint(0,100) < 50: nright = True if nleft and not nright: if idx+1 < len(symbols): idx += 1 node = Node(parent,symbols[idx]) parent.right = node elif nright and not nleft: if idx+1 < len(symbols): idx += 1 node = Node(parent,symbols[idx]) parent.left = node else: if idx+1 < len(symbols): idx += 1 node = Node(parent,symbols[idx]) parent.left = node if idx+1 < len(symbols): idx += 1 node = Node(parent,symbols[idx]) parent.right = node if random.randint(0,100) < 50: if parent.left is not None: idx = build_random_sub_trees(parent.left,symbols,idx) if parent.right is not None: idx = build_random_sub_trees(parent.right,symbols,idx) else: if parent.right is not None: idx = build_random_sub_trees(parent.right,symbols,idx) if parent.left is not None: idx = build_random_sub_trees(parent.left,symbols,idx) return idx # last symbol to be used # ---------------------------------------------------------------- # ---- main # ---------------------------------------------------------------- if __name__ == '__main__': symbols = [ 'a','b','c','d','e','f','g','h','i','j' ] ##random.seed(20011944) # ---- create a random test tree ----------------------------- print() print('------------ Root Node -----------------') # ---- print "old fashion" dash tree print() print('-------------- Dash Tree ---------------') # ---- print "new fashion" fancy tree print() print('------------ Fancy Dash Tree -----------') # ---- create a balanced tree from the random tree print() print('---------- Dash Balanced Tree ----------') print() print('---------- Fancy Balanced Tree ---------')