algorithms/binary_search_tree.py at master · farukara/algorithms · 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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#!python3
#implements binary search tree

import random

class BST():
    '''
    binary search tree implementaion
    '''

    def __init__(self):
        self.root = None

    def insert(self, value):

        item = bstnode(value)
        if self.root == None:
            self.root = item
            return
        node = self.root
        while True:
            if value == node.value:
                item.parent = node.parent
                item.rightchild = node
                node.parent = item
                break
            elif value < node.value:
                if node.leftchild:
                    if value > node.leftchild.value:
                        item.parent = node
                        item.leftchild = node.leftchild
                        node.leftchild.parent = item
                        node.leftchild = item
                        break
                    node = node.leftchild
                else:
                    node.leftchild = item
                    item.parent = node
                    break
            else:
                if node.rightchild:
                    if value < node.rightchild.value:
                        item.parent = node
                        item.rightchild = node.rightchild
                        node.rightchild.parent = item
                        node.rightchild = item
                        break
                    node = node.rightchild
                else:
                    node.rightchild = item
                    item.parent = node
                    break

    def find(self, value):
        node = self.root
        while node is not None:
            if node.value == value:
                return node
            elif node.value > value:
                node = node.leftchild
            else:
                node = node.rightchild
        return None

    def remove(self, value):
        pass

    def __str__(self):
        node = self.root
        def printnode(node):
            print(node.value)
            if node.leftchild:
                print(node.leftchild.value)
                printnode(node.leftchild)
            if node.rightchild:
                print(node.rightchild.value)
                printnode(node.rightchild)

        printnode(node)
        #while node is not None:
        #    if node.leftchild:
        #        print(node.leftchild.value, end=" ")
        #    if node.rightchild:
        #        print(node.rightchild.value)
        #    node = node.leftchild
        return "end"


class bstnode():
    '''
    creates a node with parent and childrens
    '''

    def __init__(self, value, parent=None, leftchild=None, rightchild=None):
        self.value = value
        self.parent = parent
        self.leftchild = leftchild
        self.rightchild = rightchild

    def disconnect(self):
        self.parent = None
        self.leftchild = None
        self.rightchild = None


if __name__ == "__main__":
    agac = BST()
    for i in range(10):
        agac.insert(i) #random.randrange(10))
    print(agac)