PROBLEM: PREORDER TRAVERSAL OF A THREADED BINARY TREE

Write a function to traverse an inorder threaded binary tree in preorder.

Program

#include <stdio.h> #define SUCCESS 0 #define ERROR -1 typedef int type; typedef struct node node; typedef enum {FALSE, TRUE} bool; struct node { type data; node *lchild, *rchild; bool lthread, rthread; }; /* NOTE: since this is a threaded binary tree, there wont be any condition */ /* of type (ptr == NULL). */ node tree; void tInit() { tree.lchild = tree.rchild = &tree; tree.lthread = TRUE; tree.rthread = FALSE; tree.data = 99999999; } node *insucc( node *t ) { /* * find inorder successor of t. */ node *temp = t->rchild; if( t->rthread == FALSE ) while( temp->lthread == FALSE ) temp = temp->lchild; return temp; } node *inpred( node *t ) { /* * find inorder predecessor of t. */ node *temp = t->lchild; if( t->lthread == FALSE ) while( temp->rthread == FALSE ) temp = temp->rchild; return temp; } int tInsertRight( node *s, node *t ) { /* * insert t as right child of s. */ node *temp; t->rchild = s->rchild; t->rthread = s->rthread; t->lchild = s; t->lthread = TRUE; s->rchild = t; s->rthread = FALSE; if( t->rthread == FALSE ) { temp = insucc(t); temp->lchild = t; } return SUCCESS; } int tInsertLeft( node *s, node *t ) { /* * insert t as left child of s. */ node *temp; t->lchild = s->lchild; t->lthread = s->lthread; t->rchild = s; t->rthread = TRUE; s->lchild = t; s->lthread = FALSE; if( t->lthread == FALSE ) { temp = inpred(t); temp->rchild = t; } return SUCCESS; } node *tGetNewNode( type data ) { /* * returns a new node containing the data. */ node *ptr = (node *)malloc( sizeof(node) ); ptr->data = data; ptr->lchild = ptr->rchild = NULL; ptr->lthread = ptr->rthread = FALSE; return ptr; } int tInsert( node *t, type data ) { /* * insert data in t recursively. */ if( data < t->data ) if( t->lthread == TRUE ) tInsertLeft( t, tGetNewNode(data) ); else tInsert( t->lchild, data ); else if( t->rthread == TRUE ) tInsertRight( t, tGetNewNode(data) ); else tInsert( t->rchild, data ); return SUCCESS; } void tPrint( node *t ) { /* * prints t inorder recursively without using threads. */ if( t != &tree ) { if( t->lthread == FALSE ) tPrint( t->lchild ); printf( "%d\n", t->data ); if( t->rthread == FALSE ) tPrint( t->rchild ); } } void tPrintPreorder( node *t ) { /* * prints tree preorder (no use of threads). */ if( t != &tree ) { printf( "%d\n", t->data ); if( t->lthread == FALSE ) tPrintPreorder( t->lchild ); if( t->rthread == FALSE ) tPrintPreorder( t->rchild ); } } void tPrintInorder( node *tree ) { /* * prints tree inorder using threads. */ node *temp = tree; do { temp = insucc(temp); if( temp != tree ) printf( "%d\n", temp->data ); } while( temp != tree ); } int main() { tInit(); tInsert( &tree, 4 ); tInsert( &tree, 2 ); tInsert( &tree, 1 ); tInsert( &tree, 3 ); tInsert( &tree, 6 ); tInsert( &tree, 5 ); tInsert( &tree, 7 ); tPrint( tree.lchild ); printf( "\n" ); tPrintPreorder( tree.lchild ); return 0; }

Explanation

1. In a threaded binary tree, the NULL links of leaf nodes are replaced by pointers (called threads) to other nodes in the tree. If p rightchild is normally equal to NULL , it is replaced by a pointer to the node which would be printed after p when traversing the tree in inorder. A NULL leftchild link at node p is replaced by a pointer to the node that immediately precedes node p in inorder. The left link of the first node and the right link of the last node printed in the inorder traversal point to a dummy head node of the tree, and all the nodes appear in the left subtree of this head node. For example, in this representation, a tree such as the one shown next , where solid pointers are normal links and the dotted pointers are threads, t means TRUE and f means FALSE .

   

2. In the memory representation, we should be able to distinguish between threads and normal pointers. This is done by adding two Boolean fields to the structure: leftthread and rightthread . If tree leftthread==TRUE , then tree leftchild contains a thread; otherwise , it contains a pointer to the leftchild . Similarly, if tree rightthread == TRUE , then tree rightchild contains a thread. Otherwise it contains a pointer to the rightchild .

3. The function to traverse a threaded binary tree remains as simple as that for the normal binary tree. One simply needs to check for a link not that is not a thread, and traverse it. So the recursive function tPrintPreorder() is self-explanatory. For example, the preorder traversal of the tree above is 4, 2, 1, 3, 6, 5, 7.

Points to Remember

1. Some traversing algorithms are simplified by making a tree threaded.

2. Making a tree threaded makes insertions and deletions clumsy. Also, the node size increases . So this increased complexity should be taken into consideration when using a threaded binary tree for an application.

3. Keeping a dummy head node helps in easy insertions, deletions, and traversals.