Running the code

This is part four in a series of blog posts for my ‘IT Professional Skills’ module

In my previous post, I provided the core of my sorting program. There’s still a couple of loose ends to tie up, which I will do before demonstrating the program in action.

Firstly, my program must print out its sorted tree before it exits. I do this using the treeprint () function. This function, like addtree (), is recursive. If you remember, in my main function I pass it root, which is the pointer to the root of my completed tree.

Inside the function, treeprint () is first called recursively on each left-sided Node. The data in each Node is printed to the screen only after the bottom of the current left-sided path is reached. It is only then that the corresponding right-sided path is traversed.

This results in my tree being printed out in alphabetical order. The function is written:

void
treeprint (Node *n)
{
  if (n != NULL)
    {
      treeprint (n->left);
      printf ("%s\n", n->data);
      treeprint (n->right);
    }
}

As a simple thought exercise, how would you modify this function so that the words are printed out in reverse alphabetical order?

Finally, I call my function treefree (), which frees the memory I allocated for my tree. This is not important to understand, but I’ve included it for completeness. Building a habit of freeing memory is vital when working in C.

void
treefree (Node *n)
{
  if (n != NULL)
    {
      treefree (n->left);
      free (n->data);
      free (n);
      treefree (n->right);
    }
}

Notice something familiar with this function? Binary trees lend themselves well to recursion.

Now, our program is essentially complete. I’ve built and tested it with gcc on Linux, but it should work in your C environment of choice. For ease of access, I’ve created a git repository for my example program[0]. If you have access to the Meson build system on your machine, building it is as easy as:

meson builddir
cd builddir/
ninja

Accounting for the fact that you’re still reading at this point in this blog series, I think I can safely assume your interest in seeing the program in action. In the demonstration screencast below, I sort the words in the last stanza of John Keats' poem “Ode on a Grecian Urn”:

I hope this series has been successful in providing both a basic understanding of binary trees and a clear, readable implementation of one to reference.

[0] https://gitlab.com/leesonwai/binary-tree-example