printing binary search tree

nkhambal · #1 25-Mar-2005, 20:32

Hi,

I have a binary tree constucted based on following node

CPP / C++ / C Code:

struct node
{
	int id;
	char first[20];
	char last[20];
	char email[30];
	char address[50];
	char hometel[20];
	char cellphone[20];
	struct node *left;
	struct node *right;
};

I can add nodes to the tree and search through the tree. I am sorting based on lastname (last[20] variable in node). I am assuming that my tree is sorted and now I want to print my tree. I tried inorder travesal to print it but not seems to be working for me. I get segmentation fault.

Following is GDB output for 3 nodes list.

Quote:

>>>>>>>>>>Printing Full Tree<<<<<<<<<<<<<<<<<<<

Program received signal SIGSEGV, Segmentation fault.
0x08048b0f in print_tree ()
(gdb) where
#0 0x08048b0f in print_tree ()
#1 0x08048b1a in print_tree ()
#2 0x08048865 in main ()
#3 0x42015504 in __libc_start_main () from /lib/tls/libc.so.6
(gdb)

Following is the full program code.

CPP / C++ / C Code:

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

struct node
{
	int id;
	char first[20];
	char last[20];
	char email[30];
	char address[50];
	char hometel[20];
	char cellphone[20];
	struct node *left;
	struct node *right;
};

typedef enum {
	FALSE,
	TRUE
} boolean;

struct node * add_node (struct node *, struct node *);
struct node * search_node (struct node *, char *);
void print_node (struct node *);
void print_tree (struct node *);

int main(int argc, char *argv[])
{
	
	struct node temp;
	struct node *found=NULL;
	struct node *top=NULL;
	static int counter = 0;
	char line[100];
	char choice;
	char srchname[20];


	do
	{
	counter++;
	temp.id = counter;
	printf("First Name: ");
	fgets(line,sizeof(line),stdin);
	sscanf(line,"%s",temp.first);
	printf("Last Name: ");
	fgets(line,sizeof(line),stdin);
	sscanf(line,"%s",temp.last);
	printf("Email : ");
	fgets(line,sizeof(line),stdin);
	sscanf(line,"%s",temp.email);
	printf("Address : ");
	fgets(line,sizeof(line),stdin);
	line[strlen(line)-1] = '\0';
	strcpy(temp.address,line);
	printf("Telephone (home): ");
	fgets(line,sizeof(line),stdin);
	sscanf(line,"%s",temp.hometel);
	printf("Telephone (Cell): ");
	fgets(line,sizeof(line),stdin);
	sscanf(line,"%s",temp.cellphone);	
	top=add_node(top,&temp);
	printf("\nAdd another?(y/n): ");	
	fgets(line,sizeof(line),stdin);
	sscanf(line,"%c",&choice);
	}
	while (choice == 'y' || choice == 'Y');
	
	do
	{	
		printf("Enter the last name to search: ");
		fgets(line,sizeof(line),stdin);
		sscanf(line,"%s",srchname);
		
		if ((found=search_node(top,srchname)) == NULL)
		{
			printf("No Record found\n");
		} else {
			print_node(found);
		}

		printf("\nSearch another?(y/n): ");	
		fgets(line,sizeof(line),stdin);
		sscanf(line,"%c",&choice);
	}
	while (choice == 'y' || choice == 'Y');

	printf("\n>>>>>>>>>>Printing Full Tree<<<<<<<<<<<\n\n");
	print_tree(top);
	
	return 0;
}

struct node * add_node (struct node *top, struct node *temp)
{
	struct node *newNode;
	
	if (top == NULL)
	{
		//printf("Adding First node\n");
		newNode=(struct node *)malloc(sizeof(struct node));
		temp->left=NULL;
		temp->right=NULL;
		if (memcpy(newNode,temp,sizeof(struct node)) == NULL)
		{
			printf("Node addition failed\n");
			return NULL;
		} else {
			
			printf("Node added\n");
			//print_node(newNode);
			return newNode;
		}

	} else {
		
		//printf("Adding node\n");
		//printf("temp->last: %s\n",temp->last);
		//printf("top->last: %s\n",top->last);
		if (strcasecmp(temp->last,top->last) <= 0)
		{
			printf("left\n");
			top->left=add_node(top->left,temp);
		} else {
			printf("right\n");
			top->right=add_node(top->right,temp);
		}
		printf("Node added\n");
		//print_node(top);
		return top;
	}

	return NULL;
}

void print_node (struct node *top)
{
	if (top==NULL)
	{
		printf("Empty top\n");
		return;
	}
	printf("First Name: %s\n",top->first);
	printf("Last Name: %s\n",top->last);
	printf("Email: %s\n",top->email);
	printf("Address: %s\n",top->address);
	printf("Telephone (Home): %s\n",top->hometel);
	printf("Telephone (Cell): %s\n",top->cellphone);
}

struct node * search_node (struct node *top, char *last)
{
	if (top == NULL)
	{
		printf("Empty Tree\n");
		return NULL;
	} else {

		if (strcasecmp(last,top->last) == 0)
		{
			return top;
		} 
		
		if (strcasecmp(last,top->last) <= 0)
		{
			printf("left\n");
			return (search_node(top->left,last));
		} else {
			printf("right\n");
			return (search_node(top->right,last));
		}
		
		return NULL;
	}
}

void print_tree (struct node *top)
{
	
	print_tree(top->left);	
	print_node(top);
	print_tree(top->right);
}

Can someone suggest some algorithm to print the BST.?

Thanks,

Dr. Evil · #2 26-Mar-2005, 02:28

I think I found your problem. Within print_tree(), you call print_tree() again instantly without checking to first make sure you're not sending it a NULL node, so it will essentially go through infinite recursion until it tries to access a node that's not its. So, this worked for me:

CPP / C++ / C Code:

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

struct node
{
  int id;
  char first[20];
  char last[20];
  char email[30];
  char address[50];
  char hometel[20];
  char cellphone[20];
  struct node *left;
  struct node *right;
};

typedef enum {
  FALSE,
  TRUE
} boolean;

struct node * add_node (struct node *, struct node *);
struct node * search_node (struct node *, char *);
void print_node (struct node *);
void print_tree (struct node *);

int main(int argc, char *argv[])
{
  
  struct node temp;
  struct node *found=NULL;
  struct node *top=NULL;
  static int counter = 0;
  char line[100];
  char choice;
  char srchname[20];

	
  do
  {
	  counter++;
	  temp.id = counter;
	  printf("First Name: ");
	  fgets(line,sizeof(line),stdin);
	  sscanf(line,"%s",temp.first);
	  printf("Last Name: ");
	  fgets(line,sizeof(line),stdin);
	  sscanf(line,"%s",temp.last);
	  printf("Email : ");
	  fgets(line,sizeof(line),stdin);
	  sscanf(line,"%s",temp.email);
	  printf("Address : ");
	  fgets(line,sizeof(line),stdin);
	  line[strlen(line)-1] = '\0';
	  strcpy(temp.address,line);
	  printf("Telephone (home): ");
	  fgets(line,sizeof(line),stdin);
	  sscanf(line,"%s",temp.hometel);
	  printf("Telephone (Cell): ");
	  fgets(line,sizeof(line),stdin);
	  sscanf(line,"%s",temp.cellphone);  
	  top=add_node(top,&temp);
	  printf("\nAdd another?(y/n): ");  
	  fgets(line,sizeof(line),stdin);
	  sscanf(line,"%c",&choice);
  }
  while (choice == 'y' || choice == 'Y');
  
  do
  {  
    printf("Enter the last name to search: ");
    fgets(line,sizeof(line),stdin);
    sscanf(line,"%s",srchname);
    
    if ((found=search_node(top,srchname)) == NULL)
    {
      printf("No Record found\n");
    } else {
      print_node(found);
    }

    printf("\nSearch another?(y/n): ");  
    fgets(line,sizeof(line),stdin);
    sscanf(line,"%c",&choice);
  }
  while (choice == 'y' || choice == 'Y');

  printf("\n>>>>>>>>>>Printing Full Tree<<<<<<<<<<<\n\n");
  print_tree(top);
  
  return 0;
}

struct node * add_node (struct node *top, struct node *temp)
{
  struct node *newNode;
  
  if (top == NULL)
  {
    //printf("Adding First noden");
    newNode=(struct node *)malloc(sizeof(struct node));
    temp->left=NULL;
    temp->right=NULL;
    if (memcpy(newNode,temp,sizeof(struct node)) == NULL)
    {
      printf("Node addition failed\n");
      return NULL;
    } else {
      
      printf("Node added\n");
      //print_node(newNode);
      return newNode;
    }

  } else {
    
    //printf("Adding noden");
    //printf("temp->last: %sn",temp->last);
    //printf("top->last: %sn",top->last);
    if (stricmp(temp->last,top->last) <= 0)
    {
      printf("left\n");
      top->left=add_node(top->left,temp);
    } else {
      printf("right\n");
      top->right=add_node(top->right,temp);
    }
    printf("Node added\n");
    //print_node(top);
    return top;
  }

  return NULL;
}

void print_node (struct node *top)
{
  if (top==NULL)
  {
    printf("Empty top\n");
    return;
  }
  printf("First Name: %s\n",top->first);
  printf("Last Name: %s\n",top->last);
  printf("Email: %s\n",top->email);
  printf("Address: %s\n",top->address);
  printf("Telephone (Home): %s\n",top->hometel);
  printf("Telephone (Cell): %s\n",top->cellphone);
}

struct node * search_node (struct node *top, char *last)
{
  if (top == NULL)
  {
    printf("Empty Tree\n");
    return NULL;
  } else {

    if (stricmp(last,top->last) == 0)
    {
      return top;
    }
    
    if (stricmp(last,top->last) <= 0)
    {
      printf("left\n");
      return (search_node(top->left,last));
    } else {
      printf("right\n");
      return (search_node(top->right,last));
    }
    
    return NULL;
  }
}

void print_tree (struct node *top)
{
	print_node(top);
	if(top->left != NULL) print_tree(top->left); //check to make sure we're not sending it a NULL node
	if(top->right != NULL) print_tree(top->right); //ditto
}

nkhambal · #3 26-Mar-2005, 04:01

Yes, I guess you are right Dr. Evil. I was wondering about the same. Your solution worked. Except I used it in following way to print a sorted tree..

CPP / C++ / C Code:

void print_tree (struct node *top)
{
	
	if(top->left != NULL) print_tree(top->left);	
	print_node(top);
	if(top->right != NULL) print_tree(top->right);
}

Thanks for your response.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Using meta tags help in ranking on some search engine	pcx	Search Engine Optimization Forum	8	29-Mar-2005 16:42
Please help! Dynamic binary tree problem	robsmith	C Programming Language	3	15-Mar-2005 22:20
Displaying node attributes in an XML tree display	njp01u	MS Visual C++ / MFC Forum	2	07-Feb-2005 18:42
Search Engine Positioning 101 and 201 "How To" Tips...	000	Search Engine Optimization Forum	0	29-May-2003 11:34