| btree_a | index /home/tom/py/btree_a.py |
# ===================================================================
# The balance algorithem start a the bottom of the tree (leaf nodes)
# and proceeds up the tree towards the root node
# ===================================================================
# create a sort of balanced 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.
# ===================================================================
# Tree Functions...
# tree.debug set debug flag
# tree.blance balance the tree (sort of)
# tree.count_nodes return the number of nodes in the tree
# tree.max_height return the max depth (levels) in the tree
# tree.avg_height return average search depth in the tree
# tree.insert insert node into tree
# tree.search search for a value (node) in the tree
# tree.remove_leaf_node remove a leaf node from the tree
# (a leaf nodes have no right or left links)
# tree.print_tree_nodes print the tree node information
# tree.print_tree_values print the tree node values
# tree.Print_tree_structure print the tree structure
# ===================================================================
# Note about the code:
# a. curnode is the current working node
# b. newnode is the node being added to the tree
# c. parnode is the parent node of current working node
# d. chdnode is a child node of the current working node
# e. the tree root node may be modified but not replaced
# ===================================================================
#
# Testing:
#
# from random import randint
# from random import sample
# import btree_9 as bt9
#
# # ---- function - create random node values -----------------------
# # ---- with potential duplicates -----------------------
#
# def create_random_node_values_dups(elms=20,maxint=100):
# values = []
# for _ in range(elms):
# values.append(randint(1,maxint))
# return values
#
# # ---- function - create random node values -----------------------
# # ---- with no duplicates ------------------------------
#
# def create_random_node_values(elms=20,maxint=100):
# values = sample(range(1,maxint),elms)
# return values
#
# #---- function - fill a tree with nodes (values) ------------------
#
# def fill_tree(tree,values):
# for i in values:
# tree.insert(bt9.Node(i))
#
# # ---- test values ------------------------------------------------
#
# ##values = [30,20,10,5,1,40,50,60,70]
# ##values = [30,40,50,60,70]
# ##values = [30,20,10,5,1]
# ##values = [10,9,8,7,6,5,4,3,2,1,11,12,13,14,15,16,17,18,19]
#
# values = create_random_node_values(100,10000)
#
# print('\n---- create tree (un-balanced) ------------------------')
#
# tree = bt9.BinaryTree()
# tree.set_debug(False)
# fill_tree(tree,values)
# ##tree.print_tree_values()
# ##tree.print_tree_nodes()
# tree.print_tree_structure()
# print("Maximum height of tree is {}".format(tree.max_height()))
# print("Average height of tree is {:.2f}".format(tree.avg_height()))
#
# print('\n---- create a sort of balanced tree -------------------')
#
# tree.balance()
# ##tree.print_tree_values()
# ##tree.print_tree_nodes()
# tree.print_tree_structure()
# print("Maximum height of tree is {}".format(tree.max_height()))
# print("Average height of tree is {:.2f}".format(tree.avg_height()))
#
# ===================================================================
| Modules | ||||||
| ||||||
| Classes | ||||||||||||||||
|
| ||||||||||||||||