Demo entry 3818963

Derp

   

Submitted by anonymous on Feb 29, 2016 at 07:24
Language: Python. Code size: 7.9 kB.

#Generate Tree Class
class Tree:

    #Starts out as empty tree with no root
    def __init__(self, list_linked_nodes):
        
        self.nodes = list_linked_nodes
        self.root = None #([i for i in self.nodes if i.root == True])[0]
        
    def buildTree(self, value):
        if(self.root == None):
            self.root = Node(value)
            self.is_root = True
        else:
            self._buildTree(value, self.root)

    def _buildTree(self, value, node):
        if(value < node.v):
            if(node.L != False):
                self._buildTree(value, node.L)
            else:
                node.L = Node(value)
                node.L.lvl += 1
                node.noc += 1
                node.L.p = node
                node.L.rank = node.rank - 1
                
        else:
            if(node.R != False):
                self._buildTree(value, node.R)

            else:
                node.R = Node(value)
                node.R.lvl += 1
                node.noc += 1
                node.R.p = node
                node.R.rank = node.rank + 1


    def TraverseTree(self):
        if(self.root != None):
            #Run Once
            self.checktable = []
            self.inorder_first()
            
            #Run inorder_next through entire tree
            while True:
                if(self.inorder_next() == True):
                    #print("Successfully traversed tree of size %d."%len(self.nodes))
                    total_checks = sum(self.checktable)
                    #avg_checks = float(float(sum(self.checktable))/float(len(self.nodes)))
                    tree_size = len(self.nodes)
                    return([total_checks, tree_size])
                    break
                else:
                    pass
            
        else:
            pass
    
    def inorder_first(self):
        # Set 1 as the first principle node. Also set current node to 1 (pointer node)
        self.Pointer = self.find(1)
        self.EndPoint = len(self.nodes)
        self.NextNode = self.find(self.Pointer.v + 1)
        #print("Starting at node %d looking for node %d"%(self.Pointer.v, self.NextNode))

    
    def inorder_next(self):
        self.checks = 0
        
        # looks for the target value.
        # Check surroundings
        # If nextnode level is lower than current, prefer down.
        # if nextnode rank is less, should go down and left.
        # if nextnode rank is more, should go right.
        # should choose neighbor that does:
        # closer level
        # closer rank
        # closer value.
        #if going to neighbor 
        while True:
            #Determine where the NextNode is relative to the Pointer using rank and lvl.
            if self.do_Move(self.Pointer.L) == True:
                pass
            
            #Look right. If exists and unchecked, move pointer to it.
            elif self.do_Move(self.Pointer.R) == True:
                pass
            
            #After zig zagging to bottom, look at pointer value. 
            #If it's our target, traverse complete.
            elif self.do_Check(self.Pointer) == True:
                break
            #otherwise, mark it as "checked" and start going back up
            else:
                self.do_Move(self.Pointer.p)
        
        #When found value
        #print("Successfully found NextNode %d using %d operations."%(self.NextNode, self.checks))
        
        self.checktable.append(self.checks)
        if(self.Pointer.v == self.EndPoint):
            return(True)
        else:
            self.NextNode += 1
            return(False)


    def find(self, val):
        if(self.root != None):
            return self._find(val, self.root)
        else:
            return None

    def _find(self, val, node):
        if(val == node.v):
            return node
        else:
            left = 0
            right = 0
            parent = 0
            curr = node.v
            if(curr < val):
                pivot = 0
            elif(curr > val):
                pivot = 1
            
            if(node.L != False):
                if(node.L.v == val):
                    return(node.L)
                else:
                    left = node.L.v
            if(node.R != False):
                if(node.R.v == val):
                    return(node.R)
                else:
                    right = node.R.v
            if(node.p != False):
                if(node.p.v == val):
                    return(node.p)
                else:
                    parent = node.p.v
            
            if(left == 0 and right == 0):
                self._find(val, node.p)
            elif(pivot == 0):
                if(right < val):
                    self._find(val, node.p)
                else:
                    self._find(val, node.R)
    
            elif(pivot == 1):
                self._find(val, node.L)
            else:
                pass
                
                
        
            
    def do_Move(self, node):
        if node != False:
            if node.touched == False:
                self.Pointer = node
                return(True)
            else:
                return(False)
        else:
            return(False)
                
    def do_Check(self, node):
        node.touched = True
        self.checks += 1
        #is it the one?
        if node.v == self.NextNode:
            return(True)
        else:
            return(False)
        
    def uncheck_nodes(self):
        for i in self.nodes:
            i.touched = False
        #print("Reset nodes")
            
            
            
#### The rest of this is debugging ###
####
            
    def debugTree(self, debug = "touched"):
        if(self.root is not None):
            self._debugTree(self.root, debug)
        
    def _debugTree(self, node, debug):
        if(node != False):
            if(debug == "touched"):
                self._debugTree(node.L, debug)
                sys.stdout.write(" " + str(node.touched) + " ")
                self._debugTree(node.R, debug)
                
            elif(debug == "rank"):
                self._debugTree(node.L, debug)
                sys.stdout.write(" Rank:" + str(node.rank) + " " + " Level:" + str(node.lvl) + " ")
                self._debugTree(node.R, debug)
            
    def getTreeStructure(self):
        if(self.root is not None):
            self._getTreeStructure(self.root, 0)
            
    def _getTreeStructure(self, node, nest_lvl):
        if(node != False):
            it = 0
            nest_lvl_L = nest_lvl - 1
            nest_lvl_R = nest_lvl + 1
            current_node = node
            sys.stdout.write("[" + str(current_node.v))
            if current_node.L == False:
                sys.stdout.write('[,phantom]')
            self._getTreeStructure(current_node.L, nest_lvl_L)
            if current_node.R == False:
                sys.stdout.write('[,phantom]')
            self._getTreeStructure(current_node.R, nest_lvl_R)

            sys.stdout.write("]")
        else:
            return(False)
            
    def getDepth(self):
        if(self.root is not None):
            self._gettDepth(self.root, 0)
            
    def _getDepth(self, node, depth):
        if(node != False):
            depth_l = depth - 1
            depth_r = depth + 1
            current_node = node
            sys.stdout.write("[" + str(current_node.v))
            self._getTreeStructure(current_node.L, depth_l)
            self._getTreeStructure(current_node.R, depth_r)
            sys.stdout.write("]")

            

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).