|
printing binary search tree
Hi,
I have a binary tree constucted based on following node
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.
#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,
|
25-Mar-2005, 19:32
Developing GUIs with wxPython (Part 4) by crystalattice
Similar Threads
