aboutsummaryrefslogtreecommitdiff
path: root/source/binarytree.py
blob: 036e89bafe888fde25d309a21b0559a79b4c4aa5 (plain)
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#! /usr/bin/env python
#-*- coding: utf-8 -*-

# A binary ordered tree example

class CNode(object):
    """
    Represent a node.
    """
    def __init__(self, data):
        """
        Initialization.
        """
        self.left = None
        self.right = None
        self.data = data

class CBOrdTree(object):
    """
    Represent a binary ordered tree.
    """
    def __init__(self):
        """
        Initializes the root member.
        """
        self.root = None

    def addNode(self, data):
        """
        Creates a new node and returns it.
        """
        return CNode(data)

    def insert(self, root, data):
        """
        Inserts a new data.
        """
        if root == None:
            # it there isn't any data
            # adds it and returns
            return self.addNode(data)
        else:
            # enters into the tree
            if data['article_date'] <= root.data['article_date']:
                # if the data is less than the stored one
                # goes into the left-sub-tree
                root.left = self.insert(root.left, data)
            else:
                # processes the right-sub-tree
                root.right = self.insert(root.right, data)
            return root

    def lookup(self, root, target):
        """
        Looks for a value into the tree.
        """
        if root == None:
            return 0
        else:
            # if it has found it...
            if target == root.data:
                return 1
            else:
                if target['article_date'] < root.data['article_date']:
                    # left side
                    return self.lookup(root.left, target)
                else:
                    # right side
                    return self.lookup(root.right, target)

    def minValue(self, root):
        """
        Goes down into the left
        arm and returns the last value.
        """
        while(root.left != None):
            root = root.left
        return root.data

    def maxValue(self, root):
        """
        Goes down into the right
        arm and returns the last value.
        """
        while(root.right != None):
            root = root.right
        return root.data

    def maxDepth(self, root):
        """
        Return the maximum depth.
        """
        if root == None:
            return 0
        else:
            # computes the two depths
            ldepth = self.maxDepth(root.left)
            rdepth = self.maxDepth(root.right)
            # returns the appropriate depth
            return max(ldepth, rdepth) + 1

    def size(self, root):
        if root == None:
            return 0
        else:
            return self.size(root.left) + 1 + self.size(root.right)

    def printTree(self, root):
        """
        Prints the tree path.
        """
        if root == None:
            pass
        else:
            self.printTree(root.left)
            print(root.data, end=' ')
            self.printTree(root.right)

    def printRevTree(self, root):
        """
        Prints the tree path in reverse order.
        """
        if root == None:
            pass
        else:
            self.printRevTree(root.right)
            print(root.data, end=' ')
            self.printRevTree(root.left)

if __name__ == "__main__":
    # Point of entry in execution mode.
    # create the binary tree
    BTree = CBOrdTree()
    # add the root node
    root = BTree.addNode(0)
    # ask the user to insert values
    for i in range(0, 5):
        data = int(input("insert the node value nr %d: " % i))
        # insert values
        BTree.insert(root, data)

    BTree.printTree(root)
    print()
    BTree.printRevTree(root)
    print()
    data = int(input("Insert a value to find: "))
    if BTree.lookup(root, data):
        print("found")
    else:
        print("not found")

    print(BTree.minValue(root))
    print(BTree.maxDepth(root))
    print(BTree.size(root))
bgstack15