tree.py

#  ~  Trees  ~  
#  This Gist focuses on the Tree datastructure, 
#  generation of random trees by encoded distribution,
#  verbose printing and visual display of tree,
#  and the ability to check the deepest-rightmost node.








import random

seed = random.randint(0, 1000000)

setSeed = 0

if setSeed != 0:
	seed = setSeed

random.seed(seed)
print("\nSeed: " + str(seed) + "\n")


class Node:

	def __init__(self, value, label="", children=[]):
		self.value = value
		self.label = label
		self.children = children

	def __repr__(self):
		return "[" + str(self.label) + ":" + str(self.value) + "]"


def printTree(root, indent=0):

	if (indent != 0):
		print(" " * (indent - 5) + "|")
		print(" " * (indent - 5) + "+ -- " + str(root))
	else:
		print(str(root))

	for c in reversed(root.children):
		printTree(c, indent + 5)


def printTreeFull(root, indent=0):

	order = []

	def compute(root, indent=0):

		if (indent != 0):
			string1 = " " * (indent - 5) + "|"
			string2 = " " * (indent - 5) + "+ -- " + str(root)

			order.append(string1)
			order.append(string2)
		else:
			order.append(str(root))

		for c in reversed(root.children):
			compute(c, indent + 5)

	compute(root, indent)

	order = order[::-1]

	def find(s, ch):
		return [i for i, ltr in enumerate(s) if ltr == ch]

	for r in range(len(order) - 1):

		row = order[r]

		if ('|' in row):
			inx = find(row, '|')

			string = ""
			l = 0

			for i in inx:

				if (i < len(order[r + 1])):

					if (order[r + 1][i] == " "):

						string += order[r + 1][l:i] + "|"
						l = i + 1

			string += order[r + 1][l:]
			order[r + 1] = string

	order = order[::-1]

	for o in order:
		print(o)




L = []
maxDepth = -1

def bottomRightMost(root=None, depth=0):

	global maxDepth

	if len(root.children) == 0:
		return True

	for c in root.children:
		Valid = bottomRightMost(c, depth + 1)

		if depth >= maxDepth:
			maxDepth = depth
			if Valid:
				L.append(c)
	return False





def random3Letters():
	return "".join(
	 [random.choice([chr(i).upper() for i in range(65, 91)]) for i in range(3)])


structure = [2, 2, 2] + [random.choice([0, 1, 2]) for _ in range(20)]
index = 0

def nextChildCount():
	global index

	if (index >= len(structure)):
		return 0

	index += 1

	return structure[index - 1]


def buildRandomTree(threshold=20):

	root = Node(0, random3Letters())
	Q = [root]

	while (index < threshold):

		if (len(Q) == 0):
			break

		current = Q.pop(0)
		childCount = nextChildCount()
		current.children = [Node(0, random3Letters()) for _ in range(childCount)]

		Q.extend(current.children)

	def assign(root):

		if (len(root.children) == 0):
			return root, 1

		C = 0
		for child in root.children:
			_, c = assign(child)
			C += c

		root.value = C

		return root, root.value + 1

	root, _ = assign(root)

	return root


Root = buildRandomTree()
printTreeFull(Root)
print("\n")
bottomRightMost(Root)
print("Bottom Right-Most Node:", L[-1])