Welcome, guest | Sign In | My Account | Store | Cart

A simple example demonstrating the construction of binary trees.

Python, 120 lines
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 # A binary ordered tree example class CNode: left , right, data = None, None, 0 def __init__(self, data): # initializes the data members self.left = None self.right = None self.data = data class CBOrdTree: def __init__(self): # initializes the root member self.root = None def addNode(self, data): # creates a new node and returns it return CNode(data) def insert(self, root, data): # inserts a new data if root == None: # it there isn't any data # adds it and returns return self.addNode(data) else: # enters into the tree if data <= root.data: # if the data is less than the stored one # goes into the left-sub-tree root.left = self.insert(root.left, data) else: # processes the right-sub-tree root.right = self.insert(root.right, data) return root def lookup(self, root, target): # looks for a value into the tree if root == None: return 0 else: # if it has found it... if target == root.data: return 1 else: if target < root.data: # left side return self.lookup(root.left, target) else: # right side return self.lookup(root.right, target) def minValue(self, root): # goes down into the left # arm and returns the last value while(root.left != None): root = root.left return root.data def maxDepth(self, root): if root == None: return 0 else: # computes the two depths ldepth = self.maxDepth(root.left) rdepth = self.maxDepth(root.right) # returns the appropriate depth return max(ldepth, rdepth) + 1 def size(self, root): if root == None: return 0 else: return self.size(root.left) + 1 + self.size(root.right) def printTree(self, root): # prints the tree path if root == None: pass else: self.printTree(root.left) print root.data, self.printTree(root.right) def printRevTree(self, root): # prints the tree path in reverse # order if root == None: pass else: self.printRevTree(root.right) print root.data, self.printRevTree(root.left) if __name__ == "__main__": # create the binary tree BTree = CBOrdTree() # add the root node root = BTree.addNode(0) # ask the user to insert values for i in range(0, 5): data = int(raw_input("insert the node value nr %d: " % i)) # insert values BTree.insert(root, data) print BTree.printTree(root) print BTree.printRevTree(root) print data = int(raw_input("insert a value to find: ")) if BTree.lookup(root, data): print "found" else: print "not found" print BTree.minValue(root) print BTree.maxDepth(root) print BTree.size(root)

It's a toy example written years ago to implement a binary tree in Python. Useful for newbies or for a base for something else

Rodrigo Senra 17 years, 4 months ago

Small suggestion. Nice example. IMHO you should just change the B-Tree comment to binary tree, although this code can hold multiple info per node, it does not implement a B-Tree structure neither has its properties (like being balanced, having a maximum number of buckets per node and short in height).

Foo Bear (author) 17 years, 4 months ago

Fixed. thanks :)

Vicente Soler 11 years, 11 months ago

I can see, by running the example, that zero (0) is always a node. Can we get rid of it? How could it be done?

Why cannt feed letters (or texts) into the binary tree?

Thank you

Grant Jenks 7 years, 2 months ago

If you're looking for an API similar to that provided by a binary search tree, check out the sortedcontainers module. It implements sorted list, sorted dict, and sorted set data types in pure-Python and is fast-as-C implementations (even faster!). Learn more about sortedcontainers, available on PyPI and github.

 Created by Foo Bear on Tue, 13 Jul 2004 (PSF)

### Required Modules

• (none specified)