macdevcenter.com
oreilly.comSafari Books Online.Conferences.

advertisement

AddThis Social Bookmark Button

Scripting a Binary Tree Using Tcl

by Michael J. Norton
01/28/2005

I tend to use Tcl extensively because I look at this scripting language as a big tub of Lego bricks. Who doesn't like to play with Legos? To me, Tcl is Legos for the computer programmer. It comes with lots of bricks that snap together, enabling you to build something incredible.

But here's a thought that will surely make the pragmatic C programmer's head spin. I'm going to put the Tcl language to work with managing binary trees. I hope that concept didn't give any of you compiler pilots whiplash.

In my graphics programming dabbling, I want to experiment with storing sorted line segments in a tree structure. Before I even considered tackling that tall order, I decided to investigate if a simple binary tree could be scripted using Tcl. I knew the task was well within the means of the powerful little language. I just had to pick out the right bricks--so to speak--that would make this happen.

A Binary Tree Takes Root

In C, a binary tree is coded using a struct with a data element and two pointers: a left child pointer and a right child pointer. It would look something like this:

struct node {
	int element
	node* leftChildPtr
	node* rightChildPtr
} 

The challenge here is to determine if the Tcl extensions packages provide us with the right bricks we need to meet the task. After dumping the Tcl bricks on the floor, I saw the keyed list extensions. Bingo! If you are unfamiliar with Tcl keyed lists. you may want to check out a previous article, "Playing with Keyed Lists on Mac OS X Tcl/Tk Aqua," on the Mac DevCenter. Please note that Apple currently ships the Tcl extension Expect installed in OS X. If you don't have Tcl/Tk Aqua, you can play along in a UNIX terminal window using the Expect interpreter.

Scripting the Root Node

Keyed lists provide C-struct-like flexibility to the Tcl scripting language. I can manually create a root node in Tcl in the following manner:

set binary_tree {\
root {{name root} \
{element empty} \
{leftChild NULL} \
{rightChild NULL}}}	 

This would provide you with a simple binary tree you could use. Manually creating the tree makes absolutely no sense at all. As more items are inserted in the tree the uglier the tree becomes to the human eye. More than two elements in the tree will make the tree visually difficult to manage. We're going to need to write some tools to maintain the tree for us. This is how we'll create the binary tree in Tcl.

package require Tclx

# bt_create_root
# 
# create a new binary tree
#
# Returns:
# --------
# new binary tree
#{root {{name root} {element empty} {leftChild NULL} {rightChild NULL}}}
#
proc bt_create_root {} {
    set node "root"
    keylset binary_tree $node.name "root" 
    keylset binary_tree $node.element "empty"
    keylset binary_tree $node.leftChild {NULL}
    keylset binary_tree $node.rightChild {NULL}
    return $binary_tree
}

Cutting and pasting this script snippet into the interpreter, you can create a binary tree like this:

expect1.15> set binary_tree [bt_create_root]
{root {{name root} {element empty} {leftChild NULL} {rightChild NULL}}}
expect1.16>

Pretty straightforward, huh? We have a basic binary tree we can use with Tcl.

Checking for an Empty Tree

The classic case for inserting into a binary tree is to check if the tree is empty. If the binary tree is empty, then we are inserting the first data element into the tree data structure. Here's how we check to see if the tree is empty.

# bt_is_tree_empty
#
# Empty tree: <from bt_create_root>
#{root {{name root} {element empty} {leftChild NULL} {rightRight NULL}}}
proc bt_is_tree_empty {binary_tree} {
    
    set node_name [keylkeys binary_tree]
    set element [keylget binary_tree $node_name.element]
    if {$element == "empty"} {
        return 1
    }
    return 0
}

We can check to see if our newly created binary tree is empty like this:

expect1.21> bt_is_tree_empty $binary_tree
1

As we can see, our expected result is the binary tree is empty, the procedure returned the value of 1 for true.

Inserting Elements into the Binary Tree

We previously discussed the simplest case for inserting into a binary tree, the case when the tree is empty. We will use our procedure bt_is_tree_empty for this task.

# bt_insert_element
# 
#
proc bt_insert_element { node element } {

    # get the root node
    set root_node [keylkeys node]
    # 1. handle condition for tree is empty
    if {[bt_is_tree_empty $node] == 1} {
        keylset node $root_node.element $element
        return $node
    }
    # 2. handle insertion into tree
    #set node [bt_recurse_insert $node $element]
    return $node
}

Trying this out in the expect interpreter, you'll see the following results.

expect1.29> set binary_tree [bt_insert_element $binary_tree 5]
{root {{name root} {element 5} {leftChild NULL} {rightChild NULL}}}
expect1.30>

Our binary tree is now non-empty and has a data element integer value of 5. We have the not-so-trivial case of data element insertion now.

Our Old Friend Recursion

In the procedure above, I commented out one line of the script, it calls the procedure bt_recurse_insert. This procedure handles the less trivial case of when the first element in our tree is non-empty.

From your CS101 course, you know that elements inserted into a tree must examine the first non-empty element in the tree. If the new element to be inserted into the tree is greater than the first element, try inserting the new element to the right node of the tree. If the element to be inserted is less than the first element in the tree, try inserting the element to the left node of the tree. If the elements being inserted are the second element in the tree, then this operation too is trivial. It would look like this:

    # inserting larger value element to rightChild
    if { $element > $node_element } {
        # check right leaf
        set rightChild [keylget node $node_name.rightChild]

        # i. simple case where node checked has a NULL
        #    rightChild, simply insert the element
        if {$rightChild == "NULL"} {
            set this_right_child [bt_create_leaf "rightChild" $element]
            keylset node $node_name.rightChild $this_right_child 
            return $node
        } 
}

This would handle this case of tree insertion:

Insert element: 7

Before:
          5
        /   \
     NULL  NULL

After:
         5
       /   \
     NULL   7
           / \
       NULL  NULL

The scenario for inserting an element to the left of 5 is equally as trivial, and we would replace the above code snippet with a less-than-operator. We would also change all rightChild references to leftChild. Now this ends the trivial case for building a simple balanced binary tree. Assuming we inserted the values {5,7,3} into our tree structure:


              5
           /    \
        3	 7
      /   \     /  \
     +     +   +    +      (+: NULL)

Our insertion algorithm becomes slightly more complicated. We're going to have to examine the contents of our tree in order to perform any further insertions. The procedure I commented out above, bt_recurse_insert, handles this for us.

Let's examine how we recursively insert into the rightChild. The same operation is mirrored for the leftChild, only we decide if the element being inserted is less-than (<insert left>) or greater-than (<insert right>) in comparison in the sub-tree. Here is what the code snippet for a recursive right insertion looks like.

    if { $element > $node_element } {
        # check right leaf
        set rightChild [keylget node $node_name.rightChild]
  
        # case i. simple case where node checked has a NULL
        #    rightChild, simply insert the element
        if {$rightChild == "NULL"} {
            
            set this_right_child [bt_create_leaf "rightChild" $element]
            keylset node $node_name.rightChild $this_right_child 
            
            return $node
        } 

        # case ii. None-trivial look for a node recursively
        set this_right_child [bt_recurse_insert $rightChild $element]
        
        keylset node $node_name.rightChild $this_right_child 
        return $node
    }
    #### END check right leaf

This snippet handles, again, two basic cases for insertion. Case 1: is the rightChild leaf pointer NULL? If so, insert the element into this leaf. For Case 2, I am comparing with an element that is already in populated node. I need to recursively call the procedure bt_recurse_insert to search for a free node in the tree.

Here are the three procedures used to insert into the binary tree. The third procedure, bt_create_leaf, is simply a helper function to create empty nodes to insert data element values into. As a side experiment, rewrite bt_create_root to call bt_create_leaf. It's pretty trivial.

# bt_create_leaf
#
#
# bt_create_leaf  rightChild 7
#
#rightChild {{name rightChild} {element 7} {leftChild NULL} {rightRight NULL}}}
# 
proc bt_create_leaf { leaf_name element } {
    keylset leaf $leaf_name.name $leaf_name
    keylset leaf $leaf_name.element $element
    keylset leaf $leaf_name.leftChild {NULL}
    keylset leaf $leaf_name.rightChild {NULL}
    return $leaf
}

# bt_insert_element
# 
#
proc bt_insert_element { node element } {

    # get the root node
    set root_node [keylkeys node]
    # 1. handle condition for tree is empty
    if {[bt_is_tree_empty $node] == 1} {
        keylset node $root_node.element $element
        return $node
    }
    # 2. handle insertion into tree
    set node [bt_recurse_insert $node $element]
    return $node
}

# bt_recurse_insert
#
proc bt_recurse_insert { node element } {
    set node_name [keylkeys node]
    set node_element [keylget node $node_name.element]
    # inserting larger value element to rightChild
    if { $element > $node_element } {
        # check right leaf
        set rightChild [keylget node $node_name.rightChild]
        # i. simple case where node checked has a NULL
        #    rightChild, simply insert the element
        if {$rightChild == "NULL"} {
            
            set this_right_child [bt_create_leaf "rightChild" $element]
            keylset node $node_name.rightChild $this_right_child 
            
            return $node
        } 
        # case ii. recurse to find an empty node
        set this_right_child [bt_recurse_insert $rightChild $element]
        keylset node $node_name.rightChild $this_right_child 
        return $node
    }
    #### END check right leaf

    # inserting larger value element to rightChild
    if { $element < $node_element } {
        # check left leaf
        set leftChild [keylget node $node_name.leftChild]
        # case i. simple case where node checked has a NULL
        #    leftChild, simply insert the element
        if {$leftChild == "NULL"} {
            
            set this_left_child [bt_create_leaf "leftChild" $element]
            keylset node $node_name.leftChild $this_left_child 
            
            return $node
        } 
	  # case 11. recurse to find an empty node
        set this_left_child [bt_recurse_insert $leftChild $element]
        keylset node $node_name.leftChild $this_left_child 
        return $node
    }
    #### END check left leaf
       
}
# END of procedure 

Now let's experiment with the data element insertion. Cut and paste the above procedures into your Expect interpreter. Try inserting the value 7 into the tree.

expect1.45> set binary_tree [bt_insert_element $binary_tree 7]
{root {{name root} {element 5} {leftChild NULL} {rightChild {{rightChild 
{{name rightChild} {element 7} {leftChild NULL} {rightChild NULL}}}}}}}
expect1.46>

Just as we predicted, the value of 7 was inserted into the rightChild of the tree and the leftChild is NULL. Let's see what happens when we insert the value of 3.

expect1.46> set binary_tree [bt_insert_element $binary_tree 3]
{root {{name root} {element 5} {leftChild {{leftChild {{name leftChild} 
{element 3} {leftChild NULL} {rightChild NULL}}}}} {rightChild {{rightChild 
{{name rightChild} {element 7} {leftChild NULL} {rightChild NULL}}}}}}}
expect1.47>

Another result as we expected. But we only tested the trivial cases. What happens when we insert the element value of 4? Let's dry lab it.


               5
             /   \
            3     7
          /  \   /  \
         +   4  +    +

We insert the value of 4, which is less than 5, so we insert the value to the left sub-tree. Recursing down the left sub-tree, we find that 3 is inserted here. The value of 4 is greater than 3, so we will recurse down the tree to the right of 3. From our current data, we know that the node containing the element 3 has a NULL pointer here. So we will call bt_create_leaf to create a node and insert it to the right of 3, as shown.

expect1.47> set binary_tree [bt_insert_element $binary_tree 4]
{root {{name root} {element 5} {leftChild {{leftChild {{name leftChild} 
{element 3} {leftChild NULL} {rightChild {{rightChild {{name rightChild} 
{element 4} {leftChild NULL} {rightChild NULL}}}}}}}}} {rightChild {{rightChild 
{{name rightChild} {element 7} {leftChild NULL} {rightChild NULL}}}}}}}
expect1.48>

Didn't I warn you the binary tree gets ugly real fast in Tcl? Well, I guess it could be worse, and we could be staring at memory values instead in a debugger.

Printing the Binary Tree Inorder

We can't discuss trees and recursion without providing a means to retrieve data from the tree. One common use of binary trees is to maintain sorted information. We sorted data elements as we inserted them into the tree. We can use recursion to display the contents of the tree using an inorder traversal algorithm.

The following procedure, bt_print_tree_inorder, walks the tree recursively and prints out the values in order for us.

proc bt_print_tree_inorder { node } {
    if { $node == "NULL"} {
        return
    }
    set node_name [keylkeys node]
    set node_element [keylget node $node_name.element]
   
    set rightChild [keylget node $node_name.rightChild]
    set leftChild [keylget node $node_name.leftChild]
    # is this a leaf node
    if {($rightChild == "NULL") && ($leftChild == "NULL")} {
        puts "\(bt_printTree)\t leaf node: $node_element\n"
        return
    }
    bt_print_tree_inorder $leftChild
    puts "(bt_printTree)\t node: $node_element\n"
    bt_print_tree_inorder $rightChild
}

A quick execution of the procedure looks like this:

expect1.7> bt_print_tree_inorder $binary_tree
(bt_printTree)   node: 3

(bt_printTree)   leaf node: 4

(bt_printTree)   node: 5

(bt_printTree)   leaf node: 7

Pretty cool, huh? Check out the leaf node values. It's just as we predicted with our previous tree graph, albeit the Tcl storage format is a little bit more complicated to the human eye. Now do you have any doubts on the power of Tcl?

Some Armchair Quarterbacking with Data Structures

I can still sense some tension out there as to why I didn't use in C in the first place. I think one thing programming mentors don't emphasize enough to younger programmers is that it's OK to use an interpreted language. It's also OK to loosen the button on the top collar and have some fun with programming.

Tcl is a serious language used extensively in automated testing of network hardware as well as real-time imaging in the medical field. The big plus for Tcl is that it is machine-independent. I can run my script on my Sun workstation, my PC laptop, and my Macintosh PowerBook with no modifications to the code.

Tcl is also my box of Legos, and this binary tree project was a proof of concept that I can create a complicated tree data structure. Now I need to work on this more complicated project and take a close look at which Tcl bricks snap together to store line segments in a tree. Go out there and have some fun with programming--I am!

Michael J. Norton is a software engineer at Cisco Systems.


Return to the Mac DevCenter