Python-Tutorial-5

Constructing Binary-Trees

In the previous tutorial we saw how we could structure a binary-tree in python, now we will see how we could create simple functions to build such a tree.

Why is it better to create functions to build a tree rather than to just write it as in the previous tutorial ?

This is because it will be easier to manipulate the tree when you need to use it for some application.


def make_leaf(value):
  return {'Leaf': {'Value': value} }

def build_tree(left, right):
  tree = {'Left': left, 'Right': right }
  return tree

def main():
  leaf_1 = make_leaf(23)
  leaf_2 = make_leaf(49)
  tree = build_tree(leaf_1, leaf_2)
  traverse_tree(tree)

main()

With these two additional functions make_leaf(), and build_tree(), it is possible to create the leaves, and to construct trees.

Here is a function which returns the size of a tree:


bin_tree_1 = {'Leaf': {'Value': 23} }
bin_tree_2 = {'Leaf': {'Value': 49} }
bin_tree_3 = {'Left': bin_tree_1, 'Right': bin_tree_2 }

bin_tree_4 = {'Leaf': {'Value': 159} }
bin_tree_5 = {'Leaf': {'Value': 389} }
bin_tree_6 = {'Left': bin_tree_4, 'Right': bin_tree_5 }

bin_tree_7 = {'Left': bin_tree_3, 'Right': bin_tree_6 }

def tree_size(tree):
  size = 0
  if 'Left' in tree:
    l_size = tree_size(tree['Left'])
    size += l_size
  if 'Right' in tree:
    r_size = tree_size(tree['Right'])
    size += r_size
  if 'Leaf' in tree:
    leaf = tree['Leaf']
    if 'Value' in leaf:
      return 1
  return size

t_size = tree_size(bin_tree_7)
print(f"tree-size = {t_size}")

Testing:

$ python3 bin3.py
tree-size = 4

Be carefull because this function really returns the number of leaves, and not the number of nodes.

So maybe this function should be called num_leaves(), instead of tree_size().

Here, for example, there are 4 leaves, but 3 nodes (the 'o' char.)

Going Further

You could try to write a function which count the number of nodes in stead of the number of leaves.

Usage Notice

License for the tutorial parts:

To the extent permitted by law:
license: FDL

License for the code parts:

To the extent permitted by law:
 spdx=any

back to the table of contents