# 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

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.