Tree as a very common and useful data structure is worth extensive study. Years after I took the Data-structure lesson when I was in school, for the last few days, I regrab the knowledge of how to implement and tranversing a binary tree in servral ways. Besides of the old ways such as preorder/indorder/postorder to traversing a tree, I learnt new knowledge of ways to traversing a tree: level order traversing. Further more, I knew how to print the graph of the tree using graphviz.
The graph above is drawn by
graphviz using the output data by our traverse program list below. You can easily figure out the several ways of how to traverse such a binary tree:
As you might have seen, the root-second or the inorder traverse way of such a binary search tree is ordered. In the following section, I will try to (1) constructing a binary tree using basic C structs and pointers. (2) implement different ways of how to traversing a tree.
In many books, the
Node structure often share the same defination. However, it is much more clear if you store them seperatly in two different struct. Therefore, you can store additional info in
Tree structure inaddtion to
Node structure. Currently, the
Tree structure only has a member
struct _node * which point to the root of the tree. So, I decided to use the following basic data-structure as the fondation brick of my implementation.
Tree * new_tree() return an empty tree whose root point to
Here we’ll insert values in order so we have a binary search tree. In binary search, lookup and other operations can use the principle of binary search. They allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that allow finding an item by its key.
The insert interface is defined as
void insert(Tree *tree, int value), which we insert an int value into the tree. However, a more portable interface is
void insert(Tree *tree, void *ptr) which allowing to store a pointer value in the tree. The pointer can point to any other value/struct.
In order to call the insert function recursivily we have a workhorse function
insert_internal to do most of the inserting job. Since we have to alter the
tree->root pointer when new node is added into the tree, the working horse function’s defination is
static void insert_internal(Node **node, int value) in which the address of
tree->root is passed as the first argument.
This part of code is below. When inserting a value, if the current position is pointing to NULL we have to allcate a Node structure and store value in it. Else we compare the value against the current node and insert the smaller value into the left part of the tree and the bigger value into the right part of the tree.
Pre-order traversing, also known as root-first traversing(which is more clear), is done by visiting the root first, then the left child, the the right child.
Recursive make the preorder traversing much simpler and more clear to implement. Much the same as inserting we have two separte functions to do the job. The latter one
print_internal is mainly used for recurse purposes.
If we are not using recursive ways, we can also use stack to do the same. This saves lots of function calls which is likely to be much more faster.
It is worth noticing, we have to push right part of the tree first and left part of the tree last, since the stack is LIFO data structure. So the left part is poped out first in the next loop. When the left part is poped out, its value is printed and the right/left part is pushed on the top of the stack. So, always the root first then the left part then the right part.
The inorder traversing is done by visiting the left child first, then the root, then the right child last.
A queue(FIFO) can be used to do the level traversing of a tree. By put the root in queue, then the left child of the root in queue, then the right child of the tree in queue.
This algorithm is worth much thinking to have a full understanding of how it works.
Any of the above traversing algorithm can be modified to print the edge between the parent and child. Making it much easy to adapt to the
One sample of the Fig1 converted to graphviz format is following. Each line representing either a vertex of the tree or the edge of the tree.
It is done by the following code:
Later, issue command
dot -Tjpg file.dot -o file.jpg to draw the actual graph as shown in figure1.