I wrote a binary search tree in python, explaining as I was doing it how and why I did it. I am very interested in receiving comments on the code, process, and anything else that will improve my coding or writing.
I wrote this all up in my blog at: http://kasterma.wordpress.com/2008/06/15/implementing-a-binary-search-tree/ The code of the class has been copied below, but the description of the process (mostly an attempt at approaching test driving development for as far as I understand the term) has not been copied. Any and all comments are appreciated. Best, Bart *********** python code ************************ import re class BSTree: def __init__ (self, value = None): self.value = value self.left = None self.right = None def __str__ (self): string = "(" if not self.value == None: string += str (self.value) if not (self.left == None and self.right == None): if self.left != None: string += str (self.left) else: string += "()" if self.right != None: string += str (self.right) else: string += "()" string += ")" return string def FromString (self, string): """ parses the string and builds the corresponding tree. If the parsing fails we print an error message and make no guarantees about the state of the tree. """ def readNumber (string, index): """ reads the number starting at index. Returns the number (as a string) that starts at index and the index that is just after the number. It expects the index to point to the first numberal. """ isdigit = re.compile ("\d") number = "" while isdigit.match (string [index]): number += string[index] index += 1 return number, index def FromString_Help (string, index): """ The function that actually does the parsing of the string. Variable index indicates where in the string we start working, it should be pointing to an open paren, and in returning point to just after the corresponding closing paren. """ if not string [index] == "(": print "FromString_Help: ERROR: no opening paren", print string, index tree = BSTree () tree.value, index = readNumber (string, index + 1) if string [index] == "(": tree.left, index = FromString_Help (string, index) tree.right, index = FromString_Help (string, index) if not string[index] == ")": print "FromString_Help: ERROR: no closing paren" print string, index if tree.value == '' and tree.left == None and tree.right == None: return None, index + 1 else: tree.value = int (tree.value) return tree, index + 1 index = 0 tree, index = FromString_Help (string, index) if tree == None: print "FromString: ERROR: empty tree passed" return self.value = tree.value self.left = tree.left self.right = tree.right def inOrder (self): """ gives a generator that runs through the tree inOrder """ values = [] if self.left != None: values += self.left.inOrder () if self.value != None: values.append (self.value) if self.right != None: values += self.right.inOrder () return values def Insert (self, value): """ add value to the tree in BSTree fashion. We add the value so that the values of the tree will be in order. We do not duplicate values in the tree. """ if self.value == None: # first value added to this tree self.value = value if self.value < value: if self.right == None: self.right = BSTree (value) else: self.right.Insert (value) if self.value > value: if self.left == None: self.left = BSTree (value) else: self.left.Insert (value) def Delete (self, value, parent = None, RL = None): """ remove value from the tree in BSTree fashion. Note: we might end up with an empty tree. """ if self.value == value: if self.left == None and self.right == None: if parent != None: if RL == "right": parent.right = None else: parent.left = None else: self.value = None # created an empty tree, note only # happens at the root. return if self.left == None: self.value = self.right.value self.left = self.right.left self.right = self.right.right elif self.left.right == None: self.value = self.left.value self.left = self.left.left else: moveup = self.left while moveup.right != None: # note that by the elif above at least one step is taken # we are here looking for the node to move up to the root moveup_parent = moveup moveup = moveup.right moveup_parent.right = moveup.left self.value = moveup.value return if self.value < value: self.right.Delete (value, self, "right") if self.value > value: self.left.Delete (value, self, "left") def Search (self, value): if self.value == value: return "yes" if self.value < value: if self.right == None: return "no" else: return self.right.Search (value) if self.value > value: if self.left == None: return "no" else: return self.left.Search (value) -- http://mail.python.org/mailman/listinfo/python-list