-
-
Save thinkphp/1450738 to your computer and use it in GitHub Desktop.
| ''' | |
| by Adrian Statescu <[email protected]> | |
| 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) |
@jtempela: No. The idea is that if the value to be added is less than the node (line 53), it is recursively added to the left child . If the value is greater than the root (line 61), it is recursively added to the right of the current node. If the value to be added is equal to the current node (line 69), we do not do anything as the design does not permit duplicate values in the tree.
Allowing duplicate values or not in a binary tree is a design choice and the choice depends on the use-case. There might be cases when you actually need duplicate keys, while most of the time they are not necessary
great job! :D
great example! I'm looking for some examples for insert method. Do you think insert should be a method of class Node or of class searchTree?
this code is so great, i'll send it to mars.
I think it should be a method of the class searchTree @kikiliu
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!
On line 53 shouldn't this be:
val <= current.info: