From 2c294a9947d67df29d556bb98ba55605bdb95ced Mon Sep 17 00:00:00 2001
From: Cédric Bonhomme <kimble.mandel@gmail.com>
Date: Mon, 18 Mar 2013 15:22:11 +0100
Subject: Experience: test to load all articles in an ordered binary tree.

---
 source/binarytree.py | 128 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 128 insertions(+)
 create mode 100644 source/binarytree.py

(limited to 'source/binarytree.py')

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
-- 
cgit