Representing Lists As Binary Trees in C

Case 1:

A list could be represented as a Binary Tree with all the list elements along with their information at the leaf nodes. For example, the linked list

->[A| ]->[B| ]->[C| ]-> ………[I| ] could be represented as following Binary Tree –

                       5
                    /     \
                   2        2
                 /  \     /   \
                1    2   1     1
               / \  / \ / \   / \
              A  B 1  E F  G  H  I
                  / \
                 C   D

The list elements are represented by alphabets and the numbers represent the number of list elements to the left of that node. The list elements are numbered according to their inorder traversal in the tree.

C Routine to find Kth element of the above Tree represented list

The algorithm would be as follows –

r = K;

p = tree; /* tree is the root node*/

while(p ! a leaf){

if(r <= lcount)

p = left(p);

else{

r -= lcount;

p = right(p);

}

}

find = p;

Case 2:

Now consider a scenario where all list elements are at each node of an AC Binary Tree and list elements are placed or numbered according to their inorder traversal.

->[S| ]->[T| ]->[R| ]-> ………[E| ] could be represented as following Binary Tree –

                    6 T
                    /   \
                 4 U   8  R
                 /  \    /   \
             2  T  5 C 7 U  9 E
              /   \  
            1 S   3 R 

Finding K^th element and deleting K^th element of such a list is very easy since it could be done along with the inorder traversal of such a tree. For example, we are to find the 8th element i.e R. Now, start inorder traversal from element 1. Set a counter to 1 and increment it as we proceed the traversal. While traversing, we check the counter with the value of K if they matches, we stop traversing and thus when counter = k = 8, we find the 8th element R. This could be implemented easily as a C routine for recursive inorder traversal of a Binary Tree.

C Routine to find K^th element of the above Tree represented list

The algorithm would be as follows –

scanf("%d", &K);
counter = 1;

void intravfork(NODEPTR tree){
     if(tree != NULL){
         intravfork(p->left); /* traverse left subtree*/
         printf("%d", p->info); /* visit root */
         if(counter == K){
             printf("\nThe %d element is %d", K, p->info);
             return;
         }
         counter++;
         intravfork(p->right);/* traverse rightsubtree*/
     }
}

Note: To Delete K^th element –

       if(counter == K){
           freenode(p);
           return;
       }