General Tree Operations in C Assignment Sample
You need to write a series of functions to build a tree and navigate it. Rather than a binary tree, there can be multiple values associated with each node. So for a given node, you can add a child, or add a sibling. You can also delete an entire subtree from a node. You also need to have code that visits all the nodes using depth-first recursion. Each value of the tree should store at least a char* string, and an integer, you can store other values as well. For more C programming assignments contact us for details.
Solution:
main. c
#include
#include
//Auxiliary value used in BFS
int MAX_LEVEL=0;
//Struct for Node
struct Node {
char *txt;
int len;
int tok;
//Useful for BFS printing
int level;
//A pointer to the list of children
struct Node * children;
//A pointer to the next sibling
struct Node * next;
//A pointer to the previous sibling. It’s useful for deleting a node.
struct Node * prev;
};
/*
*
*Useful function for allocating memory to a node. It allocates memory and returns a pointer to that direction.
*
*/
struct Node * new_node(char* txt, int len, int tok)
{
struct Node *new_node = malloc(sizeof(struct Node));
if ( new_node ) {
new_node->prev = NULL;
new_node->next = NULL;
new_node->children = NULL;
new_node->txt = txt;
new_node->tok = tok;
new_node->len = len;
new_node->level = 0;
}
return new_node;
}
/*
*
*Method to add a sibling to the current node. It itereates over the list of siblings until the last spot is found
*it then calls new_node method and allocates the sibling.
*
*/
struct Node *add_sibling(struct Node *n, char *txt, int len, int tok)
{
struct Node * prev=n;
if ( n == NULL )
return NULL;
while (n->next){
prev=n;
n = n->next;
}
n->next = new_node(txt,len,tok);
n->next->prev=prev;
return n->next;
}
/*
*
*Method add_sibling alternative that takes a node as an input and not the raw data. Therefore, the memory allocation
*is not needed.
*
*/
struct Node *add_sibling2(struct Node *n,struct Node *sibling)
{
struct Node * prev=n;
if ( n == NULL )
return NULL;
while (n->next){
prev=n;
n = n->next;
}
sibling->prev=prev;
return (n->next = sibling);
}
/*
*
*add_child method. It uses the add_sibling method to add a sibling to the list of children.
*
*/
struct Node *add_child(struct Node *parent, char *txt, int len, int tok)
{
if ( parent == NULL ){
return (parent= new_node(txt,len,tok));
}
if (parent->children )
return add_sibling(parent->children, txt,len,tok);
else
return (parent->children = new_node(txt,len,tok));
}
/*
*
*Similar to method add_child but it takes a previously constructed node.
*
*/
struct Node *add_child2(struct Node *parent, struct Node *child)
{
if ( parent == NULL )
return NULL;
if ( parent->children )
return add_sibling2(parent->children, child);
else
return (parent->children = child);
}
/*
*
*Method to print a node
*
*/
void print_node(struct Node *n) {
printf(“node:%s\n”,n->txt);
}
/*
*
*Function to delete a sub tree. It takes the root of the sub tree to be deleted. First, the list of siblings
*must retain consistency, therefore, the tree must be separated. Then, a recursive call to each children is made
*before freeing memory.
*
*/
void del_sub_tree(struct Node *tree)
{
if(tree->prev!=NULL)
tree->prev->next=tree->next;
if( tree != NULL ) {
struct Node * cursor=tree->children;
while(cursor!=NULL){
del_sub_tree(cursor);
cursor=cursor->next;
}
free(tree->children);
tree->children=0;
free(tree->next);
tree->next=0;
free(tree);
tree=0;
}
}
/*
*
*Depth first print of the tree in pre-order (See post-order for more information)
*
*/
void traverse_depth_first(void (*fun)(struct Node *),struct Node * tree){
if(tree!=NULL){
(*fun)(tree);
struct Node * children=tree->children;
while(children!=NULL){
traverse_depth_first(fun,children);
children=children->next;
}
}
}
/*
*
*Auxiliary function to set the level of each node. This function is used in the Breadth First traverse function.
*
*/
void traverse(void (*fun)(struct Node *),struct Node * tree, int level){
if(level>MAX_LEVEL)
MAX_LEVEL=level;
if(tree!=NULL){
tree->level=level;
struct Node * children=tree->children;
while(children!=NULL){
traverse(fun,children,level+1);
children=children->next;
}
}
}
/*
*
*Similarly to previous function, this is an auxiliary function that prints nodes only in the given level.
*
*/
void print_by_level(void (*fun)(struct Node *),struct Node * tree, int level){
if(level>MAX_LEVEL)
MAX_LEVEL=level;
if(tree!=NULL){
if(tree->level==level)
print_node(tree);
struct Node * children=tree->children;
while(children!=NULL){
print_by_level(fun,children,level);
children=children->next;
}
}
}
/*
*
*Breadth First traverse function. It sets level of all tree in the nodes and register the MAX_LEVEL reached by the tree.
*Then, it prints the nodes in each level.
*
*/
void traverse_breadth_first(void (*fun)(struct Node *),struct Node * tree){
traverse(fun,tree,0);
int current_level=0;
while(current_level<=MAX_LEVEL){
print_by_level(fun,tree,current_level);
current_level=current_level+1;
}
}
int main()
{
struct Node *root = add_child(0 , “top_root”, 8, 3) ;
struct Node *c1_1 = add_child(root , “X_1” , 3, 3);
struct Node *c1_1_d = add_child(root , “gone1”, 5, 23);
struct Node *c1_1_1_d = add_child(c1_1_d, “gone2”, 5, 3);
struct Node *c1_1_1 = add_child(c1_1 , “Y_1_1”, 5, 0);
struct Node *c1_1_2 = add_sibling(c1_1_1, “Z_1_2”, 5, 3);
del_sub_tree(c1_1_d);
struct Node *c1_2 = add_child(root , “A_77” , 4, 1);
struct Node *c1_2_1 = add_child(c1_2 , “B_2_1”, 5, 3);
traverse_breadth_first(&print_node,root);
return 0;
}
tree.h
#include
#include
//Struct for Node
struct Node {
char *txt;
int len;
int tok;
//Useful for BFS printing
int level;
//A pointer to the list of children
struct Node * children;
//A pointer to the next sibling
struct Node * next;
//A pointer to the previous sibling. It’s useful for deleting a node.
struct Node * prev;
};
/*
*
*Useful function for allocating memory to a node. It allocates memory and returns a pointer to that direction.
*
*/
struct Node * new_node(char* txt, int len, int tok);
/*
*
*Method to add a sibling to the current node. It itereates over the list of siblings until the last spot is found
*it then calls new_node method and allocates the sibling.
*
*/
struct Node *add_sibling(struct Node *n, char *txt, int len, int tok);
/*
*
*Method add_sibling alternative that takes a node as an input and not the raw data. Therefore, the memory allocation
*is not needed.
*
*/
struct Node *add_sibling2(struct Node *n,struct Node *sibling);
/*
*
*add_child method. It uses the add_sibling method to add a sibling to the list of children.
*
*/
struct Node *add_child(struct Node *parent, char *txt, int len, int tok);
/*
*
*Similar to method add_child but it takes a previously constructed node.
*
*/
struct Node *add_child2(struct Node *parent, struct Node *child);
/*
*
*Method to print a node
*
*/
void print_node(struct Node *n);
/*
*
*Function to delete a sub tree. It takes the root of the sub tree to be deleted. First, the list of siblings
*must retain consistency, therefore, the tree must be separated. Then, a recursive call to each children is made
*before freeing memory.
*
*/
void del_sub_tree(struct Node *tree);
/*
*
*Depth first print of the tree in pre-order (See post-order for more information)
*
*/
void traverse_depth_first(void (*fun)(struct Node *),struct Node * tree);
/*
*
*Auxiliary function to set the level of each node. This function is used in the Breadth First traverse function.
*
*/
void traverse(void (*fun)(struct Node *),struct Node * tree, int level);
/*
*
*Similarly to previous function, this is an auxiliary function that prints nodes only in the given level.
*
*/
void print_by_level(void (*fun)(struct Node *),struct Node * tree, int level);
/*
*
*Breadth First traverse function. It sets level of all tree in the nodes and register the MAX_LEVEL reached by the tree.
*Then, it prints the nodes in each level.
*
*/
void traverse_breadth_first(void (*fun)(struct Node *),struct Node * tree);
tree.c
#include
#include
#include “tree.h”
//Auxiliary value used in BFS
int MAX_LEVEL=0;
/*
*
*Useful function for allocating memory to a node. It allocates memory and returns a pointer to that direction.
*
*/
struct Node * new_node(char* txt, int len, int tok)
{
struct Node *new_node = malloc(sizeof(struct Node));
if ( new_node ) {
new_node->prev = NULL;
new_node->next = NULL;
new_node->children = NULL;
new_node->txt = txt;
new_node->tok = tok;
new_node->len = len;
new_node->level = 0;
}
return new_node;
}
/*
*
*Method to add a sibling to the current node. It itereates over the list of siblings until the last spot is found
*it then calls new_node method and allocates the sibling.
*
*/
struct Node *add_sibling(struct Node *n, char *txt, int len, int tok)
{
struct Node * prev=n;
if ( n == NULL )
return NULL;
while (n->next){
prev=n;
n = n->next;
}
n->next = new_node(txt,len,tok);
n->next->prev=prev;
return n->next;
}
/*
*
*Method add_sibling alternative that takes a node as an input and not the raw data. Therefore, the memory allocation
*is not needed.
*
*/
struct Node *add_sibling2(struct Node *n,struct Node *sibling)
{
struct Node * prev=n;
if ( n == NULL )
return NULL;
while (n->next){
prev=n;
n = n->next;
}
sibling->prev=prev;
return (n->next = sibling);
}
/*
*
*add_child method. It uses the add_sibling method to add a sibling to the list of children.
*
*/
struct Node *add_child(struct Node *parent, char *txt, int len, int tok)
{
if ( parent == NULL ){
return (parent= new_node(txt,len,tok));
}
if (parent->children )
return add_sibling(parent->children, txt,len,tok);
else
return (parent->children = new_node(txt,len,tok));
}
/*
*
*Similar to method add_child but it takes a previously constructed node.
*
*/
struct Node *add_child2(struct Node *parent, struct Node *child)
{
if ( parent == NULL )
return NULL;
if ( parent->children )
return add_sibling2(parent->children, child);
else
return (parent->children = child);
}
/*
*
*Method to print a node
*
*/
void print_node(struct Node *n) {
printf(“node:%s\n”,n->txt);
}
/*
*
*Function to delete a sub tree. It takes the root of the sub tree to be deleted. First, the list of siblings
*must retain consistency, therefore, the tree must be separated. Then, a recursive call to each children is made
*before freeing memory.
*
*/
void del_sub_tree(struct Node *tree)
{
if(tree->prev!=NULL)
tree->prev->next=tree->next;
if( tree != NULL ) {
struct Node * cursor=tree->children;
while(cursor!=NULL){
del_sub_tree(cursor);
cursor=cursor->next;
}
free(tree->children);
tree->children=0;
free(tree->next);
tree->next=0;
free(tree);
tree=0;
}
}
/*
*
*Depth first print of the tree in pre-order (See post-order for more information)
*
*/
void traverse_depth_first(void (*fun)(struct Node *),struct Node * tree){
if(tree!=NULL){
(*fun)(tree);
struct Node * children=tree->children;
while(children!=NULL){
traverse_depth_first(fun,children);
children=children->next;
}
}
}
/*
*
*Auxiliary function to set the level of each node. This function is used in the Breadth First traverse function.
*
*/
void traverse(void (*fun)(struct Node *),struct Node * tree, int level){
if(level>MAX_LEVEL)
MAX_LEVEL=level;
if(tree!=NULL){
tree->level=level;
struct Node * children=tree->children;
while(children!=NULL){
traverse(fun,children,level+1);
children=children->next;
}
}
}
/*
*
*Similarly to previous function, this is an auxiliary function that prints nodes only in the given level.
*
*/
void print_by_level(void (*fun)(struct Node *),struct Node * tree, int level){
if(level>MAX_LEVEL)
MAX_LEVEL=level;
if(tree!=NULL){
if(tree->level==level)
print_node(tree);
struct Node * children=tree->children;
while(children!=NULL){
print_by_level(fun,children,level);
children=children->next;
}
}
}
/*
*
*Breadth First traverse function. It sets level of all tree in the nodes and register the MAX_LEVEL reached by the tree.
*Then, it prints the nodes in each level.
*
*/
void traverse_breadth_first(void (*fun)(struct Node *),struct Node * tree){
traverse(fun,tree,0);
int current_level=0;
while(current_level<=MAX_LEVEL){
print_by_level(fun,tree,current_level);
current_level=current_level+1;
}
}