Question

Subject: Homework - Family Trees

please give me C codes, thanks
FAMILY TREE
In a Binary Tree, each node has two children at most. To eliminate the restriction by linking the children
together to form a list. In this design, each node in the tree needs to contain only two pointers: one to its eldest
child and one to its next younger sibling.
Using this representation, in each node, the pointer on the left always points down to child; the pointer on the
right indicates the next sibling in the same generation.
struct node
{
char name[32];
struct node *child;
struct node *sibling;
};
typedef struct node NODE;
Using the above linked design to implement the following two functions.
1) NODE* SearchMember(NODE *tree, char *target);
that searches a node in a family tree. If it finds it, then it returns the address of the node. If not, it returns
NULL.
2) NODE* InsertMember(NODE *ptree, char *newName, char *parentName);
that searches the parent node with parentName. If found, add a new node with newName to its child list.
3) NODE* ReadFamilyTree(char *filename);
that reads in a family tree from a data file whose name is supplied as the argument to the call. The first line of
the file should contain a name corresponding to the root of the tree. All subsequent lines in the data file should
have the following form:
child:patent
where child is the name of the new individual being entered and parent is the name of that child's parent, which
must appear earlier in the data file. For example,
William I
Pobert:William I
William II:William I
Anna:William I
Henry I:William I
Steven:Anna
William:Henry I
Matilda:Henry I
Henry II:Matilda
4) void DisplayFamilyTree(NODE *tree);

that displays all the individuals in a family tree. To record the hierachy of tree, the output of your program
should ident each generation so that the name of each child appears two spaces to the right of the
corresponding parent, as shown in the following:
William I
Pobert
William II
Anna
   Steven
Henry I
   William
   Matilda
   Henry II

5) Write a test program that tests all the functions above.

Answer 1

N.B. In your problem, in the binary tree each node has two children at most. The data file should have the following form:
child:patent. But in the given data file has four children of William I. That is why output is mismatch with the desired result.

William I
Pobert:William I [ 1 child ]
William II:William I    [ 1 child ]
Anna:William I    [ 1 child ]
Henry I:William I   [ 1 child ]
Steven:Anna
William:Henry I
Matilda:Henry I
Henry II:Matilda

Program

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

//structure definition
struct node
{
char name[32];
struct node *child;
struct node *sibling;
};
typedef struct node NODE;

NODE* SearchMember(NODE *tree, char *target);
NODE* InsertMember(NODE *ptree, char *newName, char *parentName);
NODE* ReadFamilyTree(char *filename);
void DisplayFamilyTree(NODE *tree);

NODE *tree = NULL;

//main function
int main()
{
   char filename[] = "familytree.txt";
  
   tree = ReadFamilyTree(filename);
  
   DisplayFamilyTree(tree);
  
   return 0;  
}

//search a node
NODE* SearchMember(NODE *tree, char *target)
{
   if (tree == NULL)
return NULL;
  
if (strcmp(tree->name, target) == 0)
return tree;
  
/* search on the left sutree */
   return SearchMember(tree->child, target);
  
/* search on the right subtree */
return SearchMember(tree->sibling, target);
}

//insert a node
NODE* InsertMember(NODE *ptree, char *newName, char *parentName)
{
   NODE *t = SearchMember(ptree, parentName);
  
   if(t==NULL)
       return NULL;
  
   NODE *newnode = (NODE*) malloc(sizeof(NODE));
   newnode->child = NULL;
   newnode->sibling = NULL;
   strcpy(newnode->name,newName);
  
   if(t->child==NULL)
       t->child = newnode;
   else if(t->sibling==NULL)
       t->sibling = newnode;
      
   return ptree;
}

//function to read file and create the tree
NODE* ReadFamilyTree(char *filename)
{
   FILE *f;
   char pname[20], cname[20], ch;
  
   f = fopen(filename, "r");
   if(f==NULL)
   {
       printf("File not open!!");
       exit(1);
   }
  
   fscanf(f, "%[^\n]", pname);
   fscanf(f,"%c", &ch);

   NODE *newnode = (NODE*) malloc(sizeof(NODE));
   newnode->child = NULL;
   newnode->sibling = NULL;
   strcpy(newnode->name,pname);
  
   if(tree==NULL) tree = newnode;
  
   while(!feof(f))
   {
       fscanf(f, "%[^:]", cname);
       fscanf(f,"%c", &ch);
       fscanf(f, "%[^\n]", pname);
       fscanf(f,"%c", &ch);
       InsertMember(tree, cname, pname);  
   }
  
   fclose(f);
  
   return tree;
}

//display the tree
void DisplayFamilyTree(NODE *tree)
{
   if(tree ==NULL)
       return;
   printf("%s\n", tree->name);

   printf(" ");
   DisplayFamilyTree(tree->child);
   DisplayFamilyTree(tree->sibling);  
}

Output:

William I
Pobert
William II

N.B. Even, if you face any problem regarding this problem, then share with me, I'll help you.