diff options
| -rw-r--r-- | source/binarytree.py | 128 | ||||
| -rw-r--r-- | source/testbinarytree.py | 37 |
2 files changed, 165 insertions, 0 deletions
diff --git a/source/binarytree.py b/source/binarytree.py new file mode 100644 index 00000000..48b8ba4e --- /dev/null +++ b/source/binarytree.py @@ -0,0 +1,128 @@ +# -*- coding: utf-8 -*- +# A binary ordered tree example + +class CNode(object): + left , right, data = None, None, 0 + + def __init__(self, data): + # initializes the data members + self.left = None + self.right = None + self.data = data + +class CBOrdTree(object): + 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 left + # arm and returns the last value + while(root.right != None): + root = root.right + return root.data + + def maxDepth(self, root): + 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, + 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, + self.printRevTree(root.left) + +if __name__ == "__main__": + # 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(raw_input("insert the node value nr %d: " % i)) + # insert values + BTree.insert(root, data) + print + + BTree.printTree(root) + print + BTree.printRevTree(root) + print + data = int(raw_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)
\ No newline at end of file diff --git a/source/testbinarytree.py b/source/testbinarytree.py new file mode 100644 index 00000000..27245a68 --- /dev/null +++ b/source/testbinarytree.py @@ -0,0 +1,37 @@ +# -*- coding: utf-8 -*- + +import time +import sys +import resource +# Increases Python's recursion limit and the size of the stack. +resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1)) +sys.setrecursionlimit(10**6) + +import mongodb +import binarytree + +print("Loading articles from the database...") +database = mongodb.Articles() +articles = database.get_articles() +print("Articles loaded ({}).".format(len(articles))) + +print("Generating the binary tree...") +begin = time.time() +BTree = binarytree.CBOrdTree() +# add the root node (first article of the list) +root = BTree.addNode(articles[0]) +for article in articles[1:]: + BTree.insert(root, article) +end = time.time() +print("Generation done ({0:2f} seconds).".format(end-begin)) + +print "Maximum depth of the tree:" +print BTree.maxDepth(root) +print "Oldest article:" +oldest_article = BTree.minValue(root) +print(oldest_article["article_date"].strftime('%Y-%m-%d %H:%M') + \ + " - " + oldest_article["article_title"]) +print "Newest article:" +newest_article = BTree.maxValue(root) +print(newest_article["article_date"].strftime('%Y-%m-%d %H:%M') + \ + " - " + newest_article["article_title"])
\ No newline at end of file |