Python   6.2 Trees Using Pointers

Unlike the previous section (6.1), here the idea is to use a more-traditional approach with self-referential pointers to implement binary trees. In the example below, I started with an example binary search tree written in Java. I translated it into Python, and the surprise was that the translation was fairly straightforward. In both the Java version and the Python version each class is in a separate file. The separate pieces of code are quite similar considering that the languages differ so much.

Binary Search Trees Using Pointers
n	Python Code	Java Code
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	# treenode.py: node of binary tree class TreeNode(object): def __init__(self, d): self.data = d self.left = None self.right = None # binarytree.py: simple binary search tree import sys from treenode import * # for TreeNode(d) below class BinaryTree(object): def __init__(self): self.__root = None # hidden node def insert(self, d): if self.__root == None: # empty self.__root = TreeNode(d); return loc = self.__root # search from root while True: if d < loc.data: # look left if loc.left != None: loc = loc.left else: loc.left = TreeNode(d) return elif d > loc.data: # look right if loc.right != None: loc = loc.right else: loc.right = TreeNode(d) return else: # found! Don't insert return # inorderTraversal: need , root hidden def inorderTraversal(self): self.inorderT(self.__root) # inorderT: recursive function, does work def inorderT(self, t): if t != None: self.inorderT(t.left) sys.stdout.write(str(t.data)+' ') self.inorderT(t.right) # treetest.py: test the inorder traversal import sys import binarytree class TreeTest(object): def __init__(self): self.months = \ ["Jan","Feb","Mar","Apr","May","Jun", "Jul","Aug","Sep","Oct","Nov","Dec"] def runTest(self): tree = binarytree.BinaryTree() for i in range(0,len(self.months)): tree.insert(self.months[i]) tree.inorderTraversal(); sys.stdout.write('\n') t = TreeTest() t.runTest()	// TreeNode: node in binary tree public class TreeNode { public String data; // data at each node public TreeNode left, right; public TreeNode(String d) { // construct leaf node data = d; left = right = null; } } // Tree: simple binary search tree public class Tree { private TreeNode root; // hidden root node // insert: if new entry, insert in tree public void insert(String d) { if (root == null) { // do empty tree first root = new TreeNode(d); return; } TreeNode loc = root; // search down from root while (true) { if (d.compareTo(loc.data) < 0) { // look left if (loc.left != null) loc = loc.left; else { loc.left = new TreeNode(d); break; } } else if (d.compareTo(loc.data) > 0) { // right if (loc.right != null) loc = loc.right; else { loc.right = new TreeNode(d); break;} } else break; // found! Don't insert } } // inorderTraversal: need because root is hidden public void inorderTraversal() {inorderT(root); } // inorderT: recursive function that does the work private void inorderT(TreeNode t) { if (t != null) { inorderT(t.left); System.out.print(t.data + " "); inorderT(t.right); } } } // TreeTest: test the Tree class, a binary search tree public class TreeTest { public static void main(String[] argv) { String[] months = {"Jan","Feb","Mar","Apr","May","Jun", "Jul","Aug","Sep","Oct","Nov","Dec"}; Tree tree = new Tree(); for (int i = 0; i < months.length; i++) tree.insert(months[i]); tree.inorderTraversal(); System.out.println(); } }
Common Output
Apr Aug Dec Feb Jan Jul Jun Mar May Nov Oct Sep

In the Java code, the variable root is declared private, and in Python this is done by writing  __root.

Concordance Program Using Pointers
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	# binarytree.py: simple binary search tree import sys from treenode import * # for TreeNode(d) below class BinaryTree(object): def __init__(self): self.__root = None # hidden node def insert(self, d, num): # line num ref if self.__root == None: # empty self.__root = TreeNode(d, num); return loc = self.__root # search from root while True: if d < loc.data: # look left if loc.left != None: loc = loc.left else: # new TreeNode loc.left = TreeNode(d, num) return elif d > loc.data: # look right if loc.right != None: loc = loc.right else: # new TreeNode loc.right = TreeNode(d,num) return else: # found! Add num if num != loc.nums[-1]: loc.nums.append(num) return # inorderTraversal: need , root hidden def inorderTraversal(self): self.inorderT(self.__root) # inorderT: recursive function, does work def inorderT(self, t): if t != None: self.inorderT(t.left) sys.stdout.write(str(t.data)+' ') sys.stdout.write(' '*(20 - len(t.data)-1)) x = 0 for i in t.nums: x += len(str(i)) + 1 if x < 100: sys.stdout.write(str(i) + ' ') else: x = len(str(i)) sys.stdout.write('\n' + ' '*(20) + str(i) + " ") sys.stdout.write('\n') self.inorderT(t.right)	# treenode.py: node of binary tree class TreeNode(object): def __init__(self, d, n): self.data = d self.left = None self.right = None self.num = n self.nums = [self.num] # concordance.py: test the inorder traversal import sys import binarytree import string class Concordance(object): def __init__(self, fp, ind=20, numw=5, linel=50): self.tree = binarytree.BinaryTree() self.file_prefix = fp self.indent = ind # indent of line numbers self.num_width = numw # space for line #s self.line_length = linel # width of line # self.fsrc = open(fp + ".src.txt", 'r') # src self.flist = open(fp + ".list.txt", 'w') # l#s self.num = 0 # line # of source self.word_count = 0 # count of distinct words def runTest(self): for line in self.fsrc: if len(line) == 2: self.flist.write('\n') else: self.num += 1 # Produce a listing, numbered lines strfor = "%"+str(self.num_width)+"i" self.flist.write((strfor % self.num)+ " " + line) wp = line.split() for w in wp: w = w.strip(string.punctuation).\ lower() if len(w) > 0: self.tree.insert(w, self.num) self.tree.inorderTraversal() c = Concordance("emma5", 16, 5, 100) c.runTest()