using c language In a Binary Tree, each node has two children at most. To elimin

Question

using c language

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.

Explanation / Answer

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

typedef enum { SNL_INTERGER, SNL_CHAR, SNL_ARRAY, SNL_RECORD, SNL_REVERSE_WORD, SNL_ID, SNL_SYMBOL } SNL_TYPE;

typedef enum { ProK, PheadK, TypeK, VarK, ProcDecK, StmLK, DecK, StmtK, ExpK } NodeKind;

typedef enum { ArrayK, CharK, IntegerK, RecordK, IdK } dec;

typedef enum { IfK, WhileK, AssignK, ReadK, WriteK, CallK, ReturnK } stmt;

typedef enum { OpK, ConstK, IdEK } exp;

typedef enum { valparamtype, varparamtype } ProcAttrType;

typedef enum { IdV, ArrayMembV, FieldMembV } varKind;

typedef enum { Void, Integer, Boolean } ExpType;

typedef struct array {

int low;

int up;

dec childType;

} ArrayAttr;

typedef struct proc {

ProcAttrType paramt;

} procAttr;

typedef struct expAttr {

char op;

int val;

varKind varkind;

ExpType type;

} ExpAttr;

typedef struct node {

struct node * child[3];

struct node * Sibling;

int Lineno;

NodeKind nodeKind;

char nodeKindStr[30];

union k {

dec d;

stmt s;

exp e;

char name[30];

} kind;

int idnum;

char name[10][30];

//table

char type_name[30];

union a {

ArrayAttr a_attr;

ExpAttr e_attr;

procAttr p_attr;

} attr;

} TreeNode;

extern FILE * fp;

extern SNL_TYPE tokenType;

extern char tokenValueBuffer[30];

extern int i_tokenValueBuffer;

extern char unReadTokenBuffer[30];

extern SNL_TYPE unReadTokenType;

extern int hasUnReadToken;

void lexical_main(FILE * fp);

void printf_syntax_tree(TreeNode * root, int dep);

TreeNode * DeclarePart();

TreeNode * ProgramBody();

int is_reversed_word(const char * );

int is_not_reversed_word(const char * );

SNL_TYPE ReadToken();

void UnReadToken();

TreeNode * TypeDec();

TreeNode * typeDeclaration();

TreeNode * VarDec();

void TypeDef(TreeNode * t);

TreeNode * TypeDecList();

TreeNode * TypeDecMore();

TreeNode * VarDecList();

void VarIdList(TreeNode * t);

int is_reversed_word(const char * chs);

int is_not_reversed_word(const char * chs);

int is_symbol(const char * chs);

int is_not_symbol(const char * chs);

TreeNode * ProcDec();

void FormList(TreeNode * t);

TreeNode * ParamDecList();

TreeNode * StmList();

TreeNode * ActParamList();

TreeNode * Exp();

#define token_is_id ( tokenType == SNL_ID )

#define token_is_not_id ( !token_is_id )

#define token_is_eof ( strcmp("EOF", tokenValueBuffer) == 0 )

#define token_is_integer ( tokenType == SNL_INTERGER )

#define pct ( printf("ct = %s ", tokenValueBuffer) )

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.