Review the basic data structures implemented in Python, which includes:

  • Queue
  • Stack ……

These structures are constructed by basic data type (List) . In this section, we review Tree.

Trees are used in many areas of computer science, including operating systems, graphics, database systems, and computer networking.

  • Two Definitions of a tree:
    • involves nodes and edges, with the basic vocabulary like “sibling, leaf, level, height, subtree”;
    • a recursive definition: very useful, use “subtree” to abstractly define tree structure

The key decision of implementing a tree is choosing a good internal storage technique. Two techniques:

  • “list of lists”
  • “nodes and references”

See the example below:

list of lists

To create this simple tree structure, I can write the following Python function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def buildthistree(a,b,c,d,e,f):
    # start from the root
    r = binary_tree(a)
    
    insert_left(r,b)
    insert_right(r,c)
    
    l = get_left_child(r)
    insert_right(l,d)
    
    ri = get_right_child(r)
    insert_left(ri,e)
    insert_right(ri,f)
    
    return r

The basic building functions for defining a tree data structure are:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# define a tree
def binary_tree(r):
    return [r,[],[]]

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

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

def get_root_val(root):
    return root[0]

def set_root_val(root,new_val):
    root[0] = new_val
    
def get_left_child(root):
    return root[1]

def get_right_child(root):
    return root[2]

It’s quite straightforward, right? We got the output list structure of this tree as:

Implement this function:

1
r = buildthistree('a','b','c','d','e','f')

Output:

1
['a', ['b', [], ['d', [], []]], ['c', ['e', [], []], ['f', [], []]]]

nodes and references: this representation more closely follows the object-oriented programming paradigm

Both the left and right children of the root are themselves distinct instances of the BinaryTree class. Based on this recursive definition for a tree, it allows us to treat any child of a binary tree as a binary tree itself. The Python code for building a tree via “nodes and references” is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# object-oriented concept
class BinaryTree:
    def __init__(self,root):
        self.key = root
        self.left_child = None
        self.right_child = None
        
    def insert_left(self,new_node):
        if self.left_child == None:
            self.left_child = BinaryTree(new_node)
        else:
            t = BinaryTree(new_node)
            t.left_child = self.left_child
            self.left_child = t
            
    def insert_right(self,new_node):
        if self.right_child == None:
            self.right_child = BinaryTree(new_node)
        else:
            t = BinaryTree(new_node)
            t.right_child = self.right_child
            self.right_child = t
    
    def get_right_child(self):
        return self.right_child

    def get_left_child(self):
        return self.left_child
    
    def set_root_val(self,obj):
        self.key = obj
        
    def get_root_val(self):
        return self.key

Using the nodes and references implementation to build the tree shown above is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# For building a same tree as above, use "nodes and references" way
r= BinaryTree('a')
r.insert_left('b')
r.get_left_child().insert_right('d')

r.insert_right('c')
r.get_right_child().insert_left('e')
r.get_right_child().insert_right('f')

# check
print(r.get_root_val())
print(r.get_left_child().get_root_val())
print(r.get_right_child().get_root_val())

print(r.get_left_child().get_right_child().get_root_val())
print(r.get_right_child().get_left_child().get_root_val())
print(r.get_right_child().get_right_child().get_root_val())

Output is:

1
2
3
4
5
6
a
b
c
d
e
f

Compare the two approaches,