Problem-Solving-in-Data-Structures-Algorithms-using-Python/String/StringTree.py at master · hack121/Problem-Solving-in-Data-Structures-Algorithms-using-Python · 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
#!/usr/bin/env python
class StringTree(object):
    class Node(object):
        def __init__(self, v, cnt=1, l=None, r=None):
            self.value = v
            self.count = cnt
            self.lChild = l
            self.rChild = r

    def __init__(self):
        self.root = None

    # Other Methods.
    def printTree(self):
        self.printTreeUtil(self.root)

    def printTreeUtil(self, curr):
        #  pre order
        if curr != None:
            print "[",curr.value, ":" , curr.count,"]"
            self.printTreeUtil(curr.lChild)
            self.printTreeUtil(curr.rChild)


    def insert(self, value):
        self.root = self.insertUtil(value, self.root)


    def insertUtil(self, value, curr):
        if curr == None:
            curr = self.Node(value)
        else:
            compare = self.strcmp(curr.value, value)
            if compare == 0:
                curr.count += 1
            elif compare == 1:
                curr.lChild = self.insertUtil(value, curr.lChild)
            else:
                curr.rChild = self.insertUtil(value, curr.rChild)
        return curr

    def strcmp(self, first, second):
        if(first == second):
            return 0
        elif(first < second):
            return 1
        else:
            return -1

    def freeTree(self):
        self.root = None


    def find(self, value):
        ret = self.findUtil(self.root, value)
        print value , "found::" , ret
        return ret

    def findUtil(self, curr, value):
        if curr == None:
            return False
        compare = self.strcmp(curr.value, value)
        if compare == 0:
            return True
        elif compare == 1:
            return self.findUtil(curr.lChild, value)
        else:
            return self.findUtil(curr.rChild, value)


    def frequency(self, value):
        return self.frequencyUtil(self.root, value)

    def frequencyUtil(self, curr, value):
        if curr == None:
            return 0
        compare = self.strcmp(curr.value, value)
        if compare == 0:
            return curr.count
        elif compare > 0:
            return self.frequencyUtil(curr.lChild, value)
        else:
            return self.frequencyUtil(curr.rChild, value)


tt = StringTree()
tt.insert("banana")
tt.insert("apple")
tt.insert("mango")
tt.insert("banana")
tt.insert("apple")
tt.insert("mango")
tt.find("apple")
tt.find("banana")
tt.find("mango")
tt.find("banan")
tt.find("appletree")
tt.find("grapes")

tt.printTree()
print "apple::" , tt.frequency("apple")
print "banana::" , tt.frequency("banana")
print "mango::" , tt.frequency("mango")
print "android::" , tt.frequency("android")