Code Brain

I’m writing a little module in python that contains lots of sorting algorithms (which can be found on my GitHub: here), and one i found particularly fun was the Binary Tree Sort.

This implements a “Node” Class to form the tree. Each Node has data and a left and right value. Left and Right should be other nodes or None. It has a “flatten” method that recursively flattens the tree into a sorted list. It makes use of a method, “_concatList”, that I had originally written for implementing the Quick Sort, but it ended up working quite well here too.

The sort itself is very simple. It loops through the list and inserts each element to a tree, and finally flattens it.

# Binary Tree Node
class Node:
	left, right, data = None, None, 0
	
	def __init__(self, data):
		self.left = None
		self.right = None
		self.data = data
		
	# add data to the tree
	def insert(self, data):
		# return false if the data is a duplicate
		if data == self.data:
			return false
			
		# if data is less than the current node go left
		elif data < self.data:
			# if no data here, make a new node
			if self.left == None:
				self.left = Node(data)
				
			# else try the same on its left child
			else:
				self.left.insert(data)
				
		# if its greater, go right
		else:
			# if no data here, make a new node
			if self.right == None:
				self.right = Node(data)
				
			# else try the same on its right child
			else:
				self.right.insert(data) 
				
	# flatten a node into a list
	def flatten(self):
		# if no children, return this nodes data as a list
		if self.left == None and self.right == None:
			return [self.data]
		# create empty list
		li = []
		
		# append the first list
		if self.left is not None:
			li.extend(self.left.flatten())
			
		# append data
		li.append(self.data)
		
		# append the second list
		if self.right is not None:
			li.extend(self.right.flatten())
			
		return li
		
# Binary Tree Sort
def BinaryTreeSort(li):
	# create the root node with the first element
	root = Node(li[0])
	
	# add each element to the tree
	for i in xrange(1, len(li)):
		root.insert(li[i])
		
	#flatten the tree
	return root.flatten()
		
# Concatenate two sorted lists
# used for Binary Search Tree and Quick Sort
def _concatList(l1, a, l2):
	# create a new list
	li = []
	if l1 is not None:
		# append each of the elements from l1
		for l in l1:
			li.append(l)
	else:
		pass
		
	if a is not None:
		# append the middle if there is one
		li.append(a)
	else:
		pass
		
		
	if l2 is not None:
		# append each of the elements from l2
		for l in l2:
			li.append(l)
	else:
		pass
		
	return li

Here’s my test:

>>> Disorder.BinaryTreeSort([5,2,3,8,1,9,15,4,18])
[1, 2, 3, 4, 5, 8, 9, 15, 18]