trie.py

'''
A python representation of a Trie data structure.
'''

class trie_node:

    def __init__(self):
        self.value = None
        self.children = dict()


class trie:

    def __init__(self):
        self.root = trie_node()

    def insert(self, value):
        node = self.root
        i = 0
        n = len(value)

        while i < n:
            child = node.children.get(value[i])
            if  child is not None:
                node = child
                i += 1
            else:
                break

        while i < n:
            child = node.children.get(value[i])
            node.children[value[i]] = trie_node()
            node = node.children[value[i]]
            i += 1

        node.value = value

    def search(self, value):
        node = self.root
        i = 0
        n = len(value)

        while i < n:
            child = node.children.get(value[i])
            if  child is not None:
                node = child
                i += 1
            else:
                return None
        if node.value is not None:
            return node.value
        else:
            return None


    def parse_tree(self, node = None):
        if node is None:
            node = self.root

        for child in node.children.keys():
            #print child
            self.parse_tree(node.children[child])

        if node.value is not None:
            print node.value