CIE Computer Science Binary Tree Code

*** This is a slightly modified python code from the Cambridge coursebook as the pseudo code provided by the book does not work ***

class TreeNode: # object for each node
    def __init__(self):
        self.Data = ""
        self.LeftPointer = -1
        self.RightPointer = -1
        
class BinaryTree:
    def __init__(self, n): # initialisation with list length n
        self.null = -1
        self.RootPointer = self.null
        self.FreePointer = 0
        self.Tree = []
        for i in range (0, n):
            self.Tree.append(TreeNode())
            self.Tree[i].LeftPointer = i + 1
        self.Tree[n-1].LeftPointer = self.null

    def display(self): # print a display in order of index positions
        print("{0:^5}|{1:^10}|{2:^10}|{3:^10}|".format("", "Left", "Data", "Right"))
        for i in range (0, len(self.Tree)):
            index = "[" + str(i) + "]"
            print("{0:^5}|{1:^10}|{2:^10}|{3:^10}|".format(index, self.Tree[i].LeftPointer, self.Tree[i].Data, self.Tree[i].RightPointer))
        print("RootPointer:", self.RootPointer)
        print("FreePointer:", self.FreePointer)

    def insert(self, item): # insert item, returns true if inserted and false if set full
        if self.FreePointer == self.null:
            return False
        NewNodePointer = self.FreePointer
        self.FreePointer = self.Tree[self.FreePointer].LeftPointer
        self.Tree[NewNodePointer].Data = item
        self.Tree[NewNodePointer].LeftPointer = self.null
        self.Tree[NewNodePointer].RightPointer = self.null
        if self.RootPointer == self.null:
            self.RootPointer = NewNodePointer
        else:
            ThisNodePointer = self.RootPointer
            while ThisNodePointer != self.null:
                self.PreviousNodePointer = ThisNodePointer
                if self.Tree[ThisNodePointer].Data > item:
                    self.TurnedLeft = True
                    ThisNodePointer = self.Tree[ThisNodePointer].LeftPointer
                else:
                    self.TurnedLeft = False
                    ThisNodePointer = self.Tree[ThisNodePointer].RightPointer
            if self.TurnedLeft:
                self.Tree[self.PreviousNodePointer].LeftPointer = NewNodePointer
            else:
                self.Tree[self.PreviousNodePointer].RightPointer = NewNodePointer
        return True

    def find(self, item): # returns position of an item, -1 if not found
        ThisNodePointer = self.RootPointer
        while ThisNodePointer != self.null and self.Tree[ThisNodePointer].Data != item:
            if self.Tree[ThisNodePointer].Data > item:
                ThisNodePointer = self.Tree[ThisNodePointer].LeftPointer
            else:
                ThisNodePointer = self.Tree[ThisNodePointer].RightPointer
        return ThisNodePointer

#######################
## Examples commands ##
#######################
    
MyTree = BinaryTree(6) # Create a tree of length 6
MyTree.display() # display tree in a table
MyTree.insert(10) # insert number 10
MyTree.insert(40)
MyTree.insert(30)
MyTree.insert(50)
MyTree.insert(60)
MyTree.display()
print("Item found at position", MyTree.find(30)) # print the position of number 30

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s