Binary Tree Using Lists

In [1]:
def binary_tree(r):
    return [r, [], []]
In [2]:
def insert_left(root, new_branch):
    t = root.pop(1)
    
    if len(t) > 1:
        root.insert(1, [new_branch, t, []])
    else:
        root.insert(1, [new_branch, [], []])
        
    return root
In [3]:
def insert_right(root, new_branch):
    t = root.pop(2)
    
    if len(t) > 1:
        root.insert(2, [new_branch, [], t])
    else:
        root.insert(2, [new_branch, [], []])
        
    return root
In [4]:
def get_root_val(root):
    return root[0]
In [5]:
def set_root_val(root, new_val):
    root[0] = new_val
In [6]:
def get_left_child(root):
    return root[1]
In [7]:
def get_right_child(root):
    return root[2]

Testing Its Use

In [8]:
r = binary_tree(3)
In [9]:
r
Out[9]:
[3, [], []]
In [10]:
insert_left(r, 4)
Out[10]:
[3, [4, [], []], []]
In [11]:
insert_right(r, 6)
Out[11]:
[3, [4, [], []], [6, [], []]]
In [12]:
l = get_left_child(r)
In [13]:
l
Out[13]:
[4, [], []]
In [14]:
set_root_val(l, 9)
In [15]:
l
Out[15]:
[9, [], []]
In [16]:
r
Out[16]:
[3, [9, [], []], [6, [], []]]
In [17]:
insert_left(l, 12)
Out[17]:
[9, [12, [], []], []]
In [18]:
l
Out[18]:
[9, [12, [], []], []]
In [19]:
r
Out[19]:
[3, [9, [12, [], []], []], [6, [], []]]
In [20]:
from graphviz import Digraph
from pythonds9.basic.stack import Stack
In [21]:
def viz_tree(r):
    """Visualize a list-based tree data structure
    
    1) Create an empty stack S.
    2) Initialize current node as root
    3) Push the current node to S and set current = current->left until current is NULL
    4) If current is NULL and stack is not empty then 
         a) Pop the top item from stack.
         b) Print the popped item, set current = popped_item->right 
         c) Go to step 3.
    5) If current is NULL and stack is empty then we are done.
    """
    stack = Stack()
    g = Digraph(node_attr={'shape': 'record', 'height': '.1'})
    _id = 0
    current_node = r
    leftward = True
    current_root_num = 0
    
    while True:
        if current_node:
            stack.push((_id, current_node))
            
            g.node('node{0}'.format(_id), '<f0> |<f1> {0} (#{1})|<f2> '.format(current_node[0], _id))
            if _id >= 1:
                g.edge('node{0}:f{1}'.format(current_root_num, 0 if leftward else 2),
                       'node{0}:f1'.format(_id))
                
            leftward = True
            current_node = current_node[1]  # left
            current_root_num = _id
            _id += 1

        if current_node == [] and not stack.is_empty():
            count, popped_node = stack.pop()
            if popped_node[2]:
                current_root_num = count
                current_node = popped_node[2]  # right
                leftward = False
            
        if current_node == [] and stack.is_empty():
            break      

    return g    
In [22]:
g = viz_tree(r)
In [23]:
r
Out[23]:
[3, [9, [12, [], []], []], [6, [], []]]
In [24]:
g
Out[24]:
node0 3 (#0) node1 9 (#1) node0:f0->node1:f1 node3 6 (#3) node0:f2->node3:f1 node2 12 (#2) node1:f0->node2:f1

Importing viz_tree_list from our pythonds9 package

In [25]:
from pythonds9.tree.utils import viz_tree_list
In [26]:
g2 = viz_tree_list(r)
In [27]:
g2
Out[27]:
node0 3 (#0) node1 9 (#1) node0:f0->node1:f1 node3 6 (#3) node0:f2->node3:f1 node2 12 (#2) node1:f0->node2:f1