createtree.py

# ==================================================================
# create a tree
# ==================================================================
#
# The "less" link points to (references) nodes in a sub-tree that
# contain values less that a node's value. The "more" link points
# to (references) a sub-tree that contains values greater than a
# node's value.
#
# "None" is used for links that do not point to (reference) a node.
# ==================================================================
#
#                                              (node)
#                                             +-------+
#                                             | more  |
#                                         +-->| value |
#                               (node)    |   | less  |
#                              +-------+  |   +-------+
#                              | more  |--+
#                          +-->| value |
#                (node)    |   | less  |--+    (node)
#   (tree)      +-------+  |   +-------+  |   +-------+
#  +------+     | more  |--+              |   | more  |
#  | tree |---->| value |                 +-->| value |
#  +------+     | less  |--+    (node)        | less  |
#               +-------+  |   +-------+      +-------+
#                          |   | more  |
#                          +-->| value |
#                              | less  |--+    (node)
#                              +-------+  |   +-------+
#                                         |   | more  |
#                                         +-->| value |
#                                             | less  |
#                                             +-------+
#
#      Note: parent links not show in this diagram.
#
# ==================================================================

import sys

# ------------------------------------------------------------------
# define tree node class
#
# data   - node's data value
# less   - link to nodes with values less than the node's value
# more   - link to nodes with values greater than the node's value
# parent - link to parent node
# ------------------------------------------------------------------

class Node:
    def __init__(self,parent,data):
        self.data   = data
        self.less   = None
        self.more   = None
        self.parent = parent

    def getData(self):
        return self.data

    def setData(self,data):
        self.data = data
        return

    def getLess(self):
        return self.less

    def setLess(self,node):
        self.less = node
        return

    def getMore(self):
        return self.more

    def setMore(self,node):
        self.more = node
        return

    def getParent(self):
        return self.parent

    def setParent(self,node):
        self.parent = node
        return

# ------------------------------------------------------------------
# define tree class
#
# root - root node of tree
# ------------------------------------------------------------------

class Tree:
    def __init__(self):
        self.root = None

    def getRoot(self):
        return self.root

    def setRoot(self,node):
        self.root = node
        return

    def addNodeToTree(self,data):

        def addNodeToSubTree(rootnode,data):
            rootdata  = rootnode.getData()  # sub-tree root node data
            lessnode  = rootnode.getLess()  # sub-tree root node less link
            morenode  = rootnode.getMore()  # sub-tree root node more link

            if rootdata == data:            # data equal to root node data?
                return                      # don't do anything (no duplicates)
            if data < rootdata:             # data less than root node data?
                if lessnode != None:        # yes, less node exists?
                    addNodeToSubTree(lessnode,data)
                else:                       # no, less node does not exists
                    rootnode.setLess(Node(rootnode,data))
            if data > rootdata:             # data greater than root node data?
                if morenode != None:        # yes, more node exists?
                    addNodeToSubTree(morenode,data)
                else:                       # no, more node does not exists
                    rootnode.setMore(Node(rootnode,data))
            return

        if self.root == None:               # tree empty?
            self.root = Node(None,data)     # yes, add a tree root node
        else:                               # no, the tree's root node exists
            addNodeToSubTree(self.root,data)# add a new node to a sub-tree
        return

# --------------------------------------------------------------
# create a test tree
# --------------------------------------------------------------

def createTree(tree):

    tree.addNodeToTree(200)
    tree.addNodeToTree(300)
    tree.addNodeToTree(310)
    tree.addNodeToTree(100)
    tree.addNodeToTree(290)
    tree.addNodeToTree(110)
    tree.addNodeToTree(90)
    tree.addNodeToTree(10)
    return

if __name__ == "__main__":

    # --------------------------------------------------------------
    # main - create tree
    # --------------------------------------------------------------

    theTree = Tree()

    createTree(theTree)