#include <stdio.h>
#include <string.h>
#define MAXLEN 100
struct node {
int serialNo;
char label[MAXLEN];
struct node *L;
struct node *R;
};
typedef struct {
int dim;
int **element;
} adjMatrix;
int nodeNumber;
void readTree ( struct node *T )
/* Recursive routine for constructing the equivalent binary tree */
{
int nc, i;
struct node *np;
printf("Number of children of %s : ",(*T).label);
scanf("%d",&nc);
/* Now there is a problem here... The above scanf reads the integer
* and leaves the following white characters (including the newline)
* that you entered. This creates trouble for the next fgets. So just
* read off whatever is pending in stdin, till the newline. */
while (getchar()!='\n');
if (nc > 0) {
np = T;
for (i=1;i<=nc;i++) {
/* Create the node for the i-th child */
if (i==1) {
/* The first child must come out of the left link */
(*np).L = (struct node *)malloc(sizeof(struct node));
np = (*np).L;
} else {
/* Other children (siblings of the first) come out of the right link */
(*np).R = (struct node *)malloc(sizeof(struct node));
np = (*np).R;
}
/* Now np points to the node representing the child just created */
/* Read the label */
printf("Enter the label of child %d of %s : ",i,(*T).label);
fgets((*np).label,MAXLEN,stdin);
/* fgets saves the trailing new-line also. Delete it. */
(*np).label[strlen((*np).label)-1] = '\0';
/* Initialize the L and R pointers of the new child node */
(*np).L = (*np).R = NULL;
/* Assign the serial number to the new child node */
(*np).serialNo = nodeNumber++;
}
/* Recursively construct the subtrees rooted at the children nodes created above */
for (np=(*T).L,i=1;i<=nc;i++) {
readTree(np);
np = (*np).R;
}
}
}
void displayTree ( struct node *T )
/* Display the binary tree created by readTree */
{
if (T == NULL) return;
printf("Label : %s, Left child : %s, Right child : %s.\n",
(*T).label,
((*T).L==NULL)?"NULL":(*((*T).L)).label,
((*T).R==NULL)?"NULL":(*((*T).R)).label);
/* Recursively call the display function on the left and right sub-trees */
displayTree((*T).L);
displayTree((*T).R);
}
void retrieveTree ( struct node *T )
/* print a description of the original tree using the binary tree representation */
{
struct node *np;
if (T == NULL) return; /* Nothing to do */
printf("Label : %s, Children : ",(*T).label);
np = (*T).L; /* The first child */
while (np != NULL) {
printf("%s%c",(*np).label,((*np).R==NULL)?'.':',');
np = (*np).R; /* The next sibling */
}
printf("\n");
/* Recursive calls on the two subtrees */
retrieveTree((*T).L);
retrieveTree((*T).R);
}
void allocMatrix ( adjMatrix *A )
/* Allocate memory for the adjacency matrix */
{
int i,j;
/* Store the dimension */
(*A).dim = nodeNumber;
/* Allocate memory to element. Note that element is a pointer
* to an int pointer. Carefully handle the number of stars. */
(*A).element = (int **)malloc(nodeNumber * sizeof(int *));
/* Now allocate memory to each int pointer of element */
for (i=0;i<nodeNumber;i++) {
/* Each element[i] is an int pointer. Allocate nodeNumber int's
* to each of them. */
(*A).element[i] = (int *)malloc(nodeNumber * sizeof(int));
/* Initialize all entries of the matrix to zero */
for (j=0;j<nodeNumber;j++) (*A).element[i][j] = 0;
}
}
void genMatrix ( adjMatrix *A , struct node *T )
/* Set to 1 the appropriate entry of the ajacency matrix
* for each parent-child relation */
{
struct node *np;
int i,j;
if (T == NULL) return; /* Nothing to do */
i = (*T).serialNo; /* Record parent's serial number */
np = (*T).L; /* The first child */
while (np != NULL) {
j = (*np).serialNo; /* The child's serial number */
(*A).element[i][j] = 1; /* Set the ij-th entry in the adjacency matrix */
genMatrix(A,np); /* Recursively call the routine on this child */
np = (*np).R; /* The next sibling */
}
}
void printOrder ( struct node *T )
/* Print the orders assigned to the nodes in the tree */
{
struct node *np;
if (T == NULL) return; /* Nothing to do */
np = (*T).L; /* The first child */
while (np != NULL) {
printf("%3d : %s\n",(*np).serialNo,(*np).label);
np = (*np).R; /* The next sibling */
}
/* Recursive calls */
np = (*T).L; /* The first child */
while (np != NULL) {
printOrder(np); /* Recursive call on this child */
np = (*np).R; /* The next sibling */
}
/* Note that both the above loops run on all the children of T. The
* loops could have been clubbed together. Separating them ensures
* that the serial numbers will be printed in the order they have
* been assigned, i.e., in the strictly increasing order. Printing
* the serial number of a child followed immediately by the recursive
* call on this child will produce all the information, but not, in
* general, in the neat sorted order (with respect to the serial number.) */
}
void printMatrix ( adjMatrix A )
/* Formatted printing the two-dimensional adjacency matrix */
{
int i,j;
for (i=0;i<nodeNumber;i++) {
for (j=0;j<nodeNumber;j++) printf("%2d",A.element[i][j]);
printf("\n");
}
}
int main ()
{
struct node *root;
adjMatrix A;
/* Assign the fields of the root node */
root = (struct node *)malloc(sizeof(struct node));
printf("Label of root : ");
fgets((*root).label,MAXLEN,stdin);
(*root).label[strlen((*root).label)-1] = '\0';
(*root).L = (*root).R = NULL;
(*root).serialNo = 0;
nodeNumber = 1;
/* Recursive call to generate the subtrees rooted at the children of the root */
readTree(root);
printf("\nEquivalent binary tree :\n");
displayTree(root);
printf("\nThe original tree :\n");
retrieveTree(root);
printf("\nAdjacency matrix representation :\n");
A.element = NULL;
allocMatrix(&A); /* Allocate memory and initialize to zero */
genMatrix(&A,root); /* Set the 1 entries */
printf("The following node ordering is used :\n");
printf("%3d : %s\n",(*root).serialNo,(*root).label);
printOrder(root);
printf("The adjacency matrix with respect to this ordering is :\n");
printMatrix(A);
}
Label of root : Babar Number of children of Babar : 5 Enter the label of child 1 of Babar : Humayun Enter the label of child 2 of Babar : Kamran Enter the label of child 3 of Babar : Askari Enter the label of child 4 of Babar : Hindal Enter the label of child 5 of Babar : Gulbadan Number of children of Humayun : 2 Enter the label of child 1 of Humayun : Akbar Enter the label of child 2 of Humayun : Hakim Number of children of Akbar : 3 Enter the label of child 1 of Akbar : Jahangir (Salim) Enter the label of child 2 of Akbar : Murad Enter the label of child 3 of Akbar : Daniyal Number of children of Jahangir (Salim) : 4 Enter the label of child 1 of Jahangir (Salim) : Khusrau Enter the label of child 2 of Jahangir (Salim) : Parwiz Enter the label of child 3 of Jahangir (Salim) : Shah Jahan (Khurram) Enter the label of child 4 of Jahangir (Salim) : Shahriyar Number of children of Khusrau : 0 Number of children of Parwiz : 0 Number of children of Shah Jahan (Khurram) : 7 Enter the label of child 1 of Shah Jahan (Khurram) : Dara Shukoh Enter the label of child 2 of Shah Jahan (Khurram) : Shah Shuja Enter the label of child 3 of Shah Jahan (Khurram) : Aurangzeb Enter the label of child 4 of Shah Jahan (Khurram) : Murad Baksh Enter the label of child 5 of Shah Jahan (Khurram) : Jahanara Enter the label of child 6 of Shah Jahan (Khurram) : Roshanara Enter the label of child 7 of Shah Jahan (Khurram) : Gauharara Number of children of Dara Shukoh : 0 Number of children of Shah Shuja : 0 Number of children of Aurangzeb : 6 Enter the label of child 1 of Aurangzeb : Mohammed Sultan Enter the label of child 2 of Aurangzeb : Mohammed Muazzam Enter the label of child 3 of Aurangzeb : Azam Enter the label of child 4 of Aurangzeb : Akbar (Jr) Enter the label of child 5 of Aurangzeb : Kam Bakhsh Enter the label of child 6 of Aurangzeb : Zeb-un-nissa Number of children of Mohammed Sultan : 0 Number of children of Mohammed Muazzam : 0 Number of children of Azam : 0 Number of children of Akbar (Jr) : 0 Number of children of Kam Bakhsh : 0 Number of children of Zeb-un-nissa : 0 Number of children of Murad Baksh : 0 Number of children of Jahanara : 0 Number of children of Roshanara : 0 Number of children of Gauharara : 0 Number of children of Shahriyar : 0 Number of children of Murad : 0 Number of children of Daniyal : 0 Number of children of Hakim : 0 Number of children of Kamran : 0 Number of children of Askari : 0 Number of children of Hindal : 0 Number of children of Gulbadan : 0 Equivalent binary tree : Label : Babar, Left child : Humayun, Right child : NULL. Label : Humayun, Left child : Akbar, Right child : Kamran. Label : Akbar, Left child : Jahangir (Salim), Right child : Hakim. Label : Jahangir (Salim), Left child : Khusrau, Right child : Murad. Label : Khusrau, Left child : NULL, Right child : Parwiz. Label : Parwiz, Left child : NULL, Right child : Shah Jahan (Khurram). Label : Shah Jahan (Khurram), Left child : Dara Shukoh, Right child : Shahriyar. Label : Dara Shukoh, Left child : NULL, Right child : Shah Shuja. Label : Shah Shuja, Left child : NULL, Right child : Aurangzeb. Label : Aurangzeb, Left child : Mohammed Sultan, Right child : Murad Baksh. Label : Mohammed Sultan, Left child : NULL, Right child : Mohammed Muazzam. Label : Mohammed Muazzam, Left child : NULL, Right child : Azam. Label : Azam, Left child : NULL, Right child : Akbar (Jr). Label : Akbar (Jr), Left child : NULL, Right child : Kam Bakhsh. Label : Kam Bakhsh, Left child : NULL, Right child : Zeb-un-nissa. Label : Zeb-un-nissa, Left child : NULL, Right child : NULL. Label : Murad Baksh, Left child : NULL, Right child : Jahanara. Label : Jahanara, Left child : NULL, Right child : Roshanara. Label : Roshanara, Left child : NULL, Right child : Gauharara. Label : Gauharara, Left child : NULL, Right child : NULL. Label : Shahriyar, Left child : NULL, Right child : NULL. Label : Murad, Left child : NULL, Right child : Daniyal. Label : Daniyal, Left child : NULL, Right child : NULL. Label : Hakim, Left child : NULL, Right child : NULL. Label : Kamran, Left child : NULL, Right child : Askari. Label : Askari, Left child : NULL, Right child : Hindal. Label : Hindal, Left child : NULL, Right child : Gulbadan. Label : Gulbadan, Left child : NULL, Right child : NULL. The original tree : Label : Babar, Children : Humayun,Kamran,Askari,Hindal,Gulbadan. Label : Humayun, Children : Akbar,Hakim. Label : Akbar, Children : Jahangir (Salim),Murad,Daniyal. Label : Jahangir (Salim), Children : Khusrau,Parwiz,Shah Jahan (Khurram),Shahriyar. Label : Khusrau, Children : Label : Parwiz, Children : Label : Shah Jahan (Khurram), Children : Dara Shukoh,Shah Shuja,Aurangzeb,Murad Baksh,Jahanara,Roshanara,Gauharara. Label : Dara Shukoh, Children : Label : Shah Shuja, Children : Label : Aurangzeb, Children : Mohammed Sultan,Mohammed Muazzam,Azam,Akbar (Jr),Kam Bakhsh,Zeb-un-nissa. Label : Mohammed Sultan, Children : Label : Mohammed Muazzam, Children : Label : Azam, Children : Label : Akbar (Jr), Children : Label : Kam Bakhsh, Children : Label : Zeb-un-nissa, Children : Label : Murad Baksh, Children : Label : Jahanara, Children : Label : Roshanara, Children : Label : Gauharara, Children : Label : Shahriyar, Children : Label : Murad, Children : Label : Daniyal, Children : Label : Hakim, Children : Label : Kamran, Children : Label : Askari, Children : Label : Hindal, Children : Label : Gulbadan, Children : Adjacency matrix representation : The following node ordering is used : 0 : Babar 1 : Humayun 2 : Kamran 3 : Askari 4 : Hindal 5 : Gulbadan 6 : Akbar 7 : Hakim 8 : Jahangir (Salim) 9 : Murad 10 : Daniyal 11 : Khusrau 12 : Parwiz 13 : Shah Jahan (Khurram) 14 : Shahriyar 15 : Dara Shukoh 16 : Shah Shuja 17 : Aurangzeb 18 : Murad Baksh 19 : Jahanara 20 : Roshanara 21 : Gauharara 22 : Mohammed Sultan 23 : Mohammed Muazzam 24 : Azam 25 : Akbar (Jr) 26 : Kam Bakhsh 27 : Zeb-un-nissa The adjacency matrix with respect to this ordering is : 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Note that the adjacency matrix is very sparse. In fact any tree on n nodes has exactly n-1 edges implying that out of the n2 entries in the adjacency matrix only n-1 are non-zero. If one maintains only the (i,j) pairs for which the ij-th entries are 1, one requires O(n) space. The adjacency matrix requires O(n2) space. However, the equivalent binary tree, though a bit complex, also requires O(n) space, since there is exactly one struct node for each node in the tree.
[Course home] [Home]