CS 3723
  Programming Languages  
  6.2 Trees Using Pointers   

6.2. Using Pointers to Represent Trees: For this page's inspiration, see especially: Nodes and References, which is a part of: Python Data Structures.

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
nPython CodeJava 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.

(Revision date: 2015-03-01. Please use ISO 8601, the International Standard.)