Created
December 9, 2011 08:29
-
-
Save thinkphp/1450738 to your computer and use it in GitHub Desktop.
Binary Search Tree implementation in Python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ''' | |
| by Adrian Statescu <adrian@thinkphp.ro> | |
| Twitter: @thinkphp | |
| G+ : http://gplus.to/thinkphp | |
| MIT Style License | |
| ''' | |
| ''' | |
| Binary Search Tree | |
| ------------------ | |
| Trees can come in many different shapes, and they can vary in the number of children allowed per node or in the way | |
| they organize data values within the nodes. One of the most commonly used trees in computer science is the binary tree. | |
| A binary tree is a tree in which each node can have at most two children. On child is identified as the left child and | |
| the other as the right child. The topmost node of the tree is known as the root node.It provides the single acccess point | |
| into the structure. The root node is the only node in the tree that does not have an incoming edge (an edge directed towart it) | |
| By definition every non=empty tree must have contain a root node. | |
| ''' | |
| class Node: | |
| def __init__(self,info): #constructor of class | |
| self.info = info #information for node | |
| self.left = None #left leef | |
| self.right = None #right leef | |
| self.level = None #level none defined | |
| def __str__(self): | |
| return str(self.info) #return as string | |
| class searchtree: | |
| def __init__(self): #constructor of class | |
| self.root = None | |
| def create(self,val): #create binary search tree nodes | |
| if self.root == None: | |
| self.root = Node(val) | |
| else: | |
| current = self.root | |
| while 1: | |
| if val < current.info: | |
| if current.left: | |
| current = current.left | |
| else: | |
| current.left = Node(val) | |
| break; | |
| elif val > current.info: | |
| if current.right: | |
| current = current.right | |
| else: | |
| current.right = Node(val) | |
| break; | |
| else: | |
| break | |
| def bft(self): #Breadth-First Traversal | |
| self.root.level = 0 | |
| queue = [self.root] | |
| out = [] | |
| current_level = self.root.level | |
| while len(queue) > 0: | |
| current_node = queue.pop(0) | |
| if current_node.level > current_level: | |
| current_level += 1 | |
| out.append("\n") | |
| out.append(str(current_node.info) + " ") | |
| if current_node.left: | |
| current_node.left.level = current_level + 1 | |
| queue.append(current_node.left) | |
| if current_node.right: | |
| current_node.right.level = current_level + 1 | |
| queue.append(current_node.right) | |
| print "".join(out) | |
| def inorder(self,node): | |
| if node is not None: | |
| self.inorder(node.left) | |
| print node.info | |
| self.inorder(node.right) | |
| def preorder(self,node): | |
| if node is not None: | |
| print node.info | |
| self.preorder(node.left) | |
| self.preorder(node.right) | |
| def postorder(self,node): | |
| if node is not None: | |
| self.postorder(node.left) | |
| self.postorder(node.right) | |
| print node.info | |
| tree = searchtree() | |
| arr = [8,3,1,6,4,7,10,14,13] | |
| for i in arr: | |
| tree.create(i) | |
| print 'Breadth-First Traversal' | |
| tree.bft() | |
| print 'Inorder Traversal' | |
| tree.inorder(tree.root) | |
| print 'Preorder Traversal' | |
| tree.preorder(tree.root) | |
| print 'Postorder Traversal' | |
| tree.postorder(tree.root) |
Could someone please help me understand code in line 51. Why could he have possibly used 1 in the while. Thanks in advance
@ajharry69 he uses breaks to break the while loop when necessary. It keeps looping until the break.
Could anyone can help me how to represent binary tree in graph please. :(
Your code is very nicely written and easy to follow.
Thanks for sharing it!
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I think it should be a method of the class searchTree @kikiliu