CDSusingPython/traversals.py at master · rishabkatta/CDSusingPython · GitHub

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
"""
CSCI-603: Trees (week 10)
Author: Sean Strout @ RIT CS

This is an implementation of three recursive traversals
(preorder, inorder, postorder, on a binary tree composed of BTNode's.
"""

from btnode import BTNode

def preorder(node):
    """
    A preorder traversal has a visitation order of parent,
    left and then right.
    :param node: The current node in the traversal (BTNode)
    :return: None
    """
    if node != None:
        print(node.val, end=' ')
        preorder(node.left)
        preorder(node.right)

def inorder(node):
    """
    An inorder traversal has a visitation order of left,
    parent and then right.
    :param node: The current node in the traversal (BTNode)
    :return: None
    """
    if node != None:
        inorder(node.left)
        print(node.val, end=' ')
        inorder(node.right)

def postorder(node):
    """
    A postorder traversal has a visitation order of left,
    right and then parent.
    :param node: The current node in the traversal (BTNode)
    :return: None
    """
    if node != None:
        postorder(node.left)
        postorder(node.right)
        print(node.val, end=' ')

def traverse(node):
    """
    A function that performs all three traversals
    :param node: The root of the tree (BTNode)
    :return: None
    """
    print('Traversing...')
    print('preorder:', end= ' ')
    preorder(node)
    print()
    print('inorder:', end= ' ')
    inorder(node)
    print()
    print('postorder:', end= ' ')
    postorder(node)
    print()

def testTraversals():
    """
    A function to test the traversals over different binary trees.
    :return: None
    """
    # single node
    traverse(BTNode(10))

    # A parent node (20), with left (10) and right (30) children
    traverse(BTNode(20, BTNode(10), BTNode(30)))

    # from lecture notes: tree.png
    traverse(BTNode('A',
            BTNode('B',
                   None,
                   BTNode('D')),
            BTNode('C',
                   BTNode('E',
                          BTNode('G'),
                          None),
                   BTNode('F',
                          BTNode('H'),
                          BTNode('I')))))

if __name__ == '__main__':
    testTraversals()