need help in my program in "ADT Tree"

[thefalcon79]

hi all

any one plz can help me with my prog.

i'm trying to create Searching(), Insert(), Delete() and View() functions for ADT Tree.
i got the main() function as an assignment, and i need to create the above functions for it i got blue trying!!!
plz some help, guys

here is my code:

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

typedef int Boolean;
typedef char KeyType[20];
typedef struct tree_entry
{
	KeyType name;
	int phone;
}TreeEntry;

typedef struct treenode
{
	TreeEntry entry;
	struct treenode *left;
	struct treenode *right;
}TreeNode;

void CreateTree(TreeNode **root)
{
	*root = NULL;
}
TreeNode *MakeTreeNode(TreeEntry x)
{
	TreeNode *p;
	p = (TreeNode *) malloc(sizeof(TreeNode));
	if(!p)
		printf("Failed to allocate space for tree node");
	else
	{
		p->left = NULL;
		p->right = NULL;		
		strcpy(p->entry.name, x.name);
		p->entry.phone = x.phone;
	}
	return p;
}

TreeNode *InsertNode (TreeNode *root, TreeNode *newnode)
{
	if (root == NULL) {
		root = newnode;
		root->left = root->right = NULL;
	}
	else if (newnode->entry < root->entry)
		root->left = InsertNode(root->left, newnode);
	else
		root->right = InsertNode(root->right, newnode);
	return root;
}
void GetData(TreeNode **root)
{
	TreeEntry data;
	TreeNode *newnode;
	int i, n;
	printf("Enter how many records do you want to  key in: ");
	scanf("%d", &n);
	for(i=1;i<=n;i++)
	{
		printf("\nEnter name and telephone number for record # %d: ", i);
		scanf("%s %d", data.name, &data.phone);
		newnode = MakeTreeNode(data);
		*root = InsertNode(*root,newnode);//!!!!!!!!!!!!!!!
	}
}
TreeNode * TreeSearch(TreeNode *root, KeyType target)
{
	if(root)
	{
		if(target < root->entry.name)
			root = TreeSearch(root->left,target);
		else if(target > root->entry.name)
			root = TreeSearch(root->right,target);
	}
	return root;
}



Boolean TreeEmpty(TreeNode *root)
{
	return root == NULL;
}

void DeleteNodeTree(TreeNode **p)
{
	TreeNode *r,*q;
	r = *p;
	if(r == NULL)
		printf("Attempt to delete nonexistent node from binary tree");
	else if(r->right == NULL)
	{
		*p = r->left;
		free(r);
	}
	else if(r->left == NULL)
	{
		*p = r->right;
		free(r);
	}
	else
	{
		for(q = r->right; q->left; q = q->left)
		{
			q->left = r->left;
			*p = r->right;
			free(r);
		}
	}
}
void Inorder(TreeNode *root)
{
	if(root)
	{
		Inorder(root->left);
		printf("%c", root->entry.name);
		Inorder(root->right);
	}
}
void PrintEntry(TreeEntry *entry)
{	
	printf("%s\n%d",entry->name,entry->phone);
}
void Menu(void)
{
	printf("\nSelect your choice:\n");
	printf("1. Searching for data\n");
	printf("2. Insert new data\n");
	printf("3. Delete a data\n");
	printf("4. View phone list\n");
	printf("5. Quit\n");
	printf("Choice: ");
}


void main()
{
	TreeNode *root, *searchnode=NULL, *deletenode=NULL, *newnode, tnode;
	int choice, cont=1;
	KeyType nama;
	TreeEntry newentry;
	CreateTree(&root);
	GetData(&root);
	while(cont==1)
	{
		Menu();
		scanf("%d", &choice);
		switch (choice)
		{
		case 1:
			printf("Enter your friend's name: ");
			fflush(stdin);
			gets(nama);
			searchnode=TreeSearch(root,nama);
			if(searchnode!=NULL)
				PrintEntry(&searchnode->entry);
			else
				printf("Not found.\n");
				break;
			case 2:
				printf("Enter your friend's name: ");
				scanf("%s",newentry.name);
				printf("Enter your friend's phone number: ");
				scanf("%d", &newentry.phone);
				newnode=MakeTreeNode(newentry);
				root=InsertNode(root,newnode);
				break;
			case 3:
				printf("Enter your friend's name: ");
				scanf("%s", nama);
				deletenode=TreeSearch(root,nama);
				if(!deletenode)
				printf("Entry does not exist in the phonebook.\n");
				else
				{
					printf("Are you sure want to delete %s entry in thephonebook? Yes=1, No=0: ",deletenode->entry.name);
					fflush(stdin);
					if(getchar()=='1')
					{
						//DeleteKeyTree(&root,&tnode,nama);
						DeleteNodeTree(&root);
						printf("%s is already deleted from the phonebook.\n", nama);
					}
					else
						printf("%s is not deleted from the phonebook.\n", nama);
				}
				break;
			case 4:
				printf("My telephone book\n");
				Inorder(root);
				break;
			case 5:
				cont=0;
				break;
			default:
				printf("Invalid choice\n");
		}
	}
}

my problem is to create MakeTreeNode(), InsertNode(), TreeSearch() and DeleteNodeTree() functions for this main() function and structures mentioned in the code.

i'm beginer in tree prog. and need ur help, guys

thnx

[MK27]

i'm trying to create Searching(), Insert(), Delete() and View() functions for ADT Tree.
i got the main() function as an assignment, and i need to create the above functions for it i got blue trying!!!

Rather than explain what you have to do (there is a post asking about how to insert, delete, etc with a tree or linked list here almost daily), you might have more luck if you explain specifically what you tried and how it made you blue Few people will look thru 100+ lines of code and point all your errors out wholesale.

[thefalcon79]

i can now inter/add and print out the node's, but still have troubles with TreeSearch() and delete() functions..
and as i mentioned before, i have this assignment to write these functions for function main().. if u read the main function then u will understand what i want to do for each operation in linked tree library, it's clear in the code.

i tried to search in this board and got nothing similar for these operations!!! + i said: i'm new in Tree porg. :-S

thnx

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

typedef int Boolean;
typedef char KeyType[20];
typedef struct tree_entry
{
	KeyType name;
	int phone;
}TreeEntry;

typedef struct treenode
{
	TreeEntry entry;
	struct treenode *left;
	struct treenode *right;
}TreeNode;

void CreateTree(TreeNode **root)
{
	*root = NULL;
}
TreeNode *MakeTreeNode(TreeEntry x)
{
	TreeNode *p;
	p = (TreeNode *) malloc(sizeof(TreeNode));
	if(!p)
		printf("Failed to allocate space for tree node");
	else
	{
		p->left = NULL;
		p->right = NULL;		
		strcpy(p->entry.name, x.name);
		p->entry.phone = x.phone;
	}
	return p;
}

TreeNode *InsertNode (TreeNode *root, TreeNode *newnode)
{
	if (root == NULL) {
		root = newnode;
		root->left = root->right = NULL;
	}
	else if (newnode->entry.name < root->entry.name)
		root->left = InsertNode(root->left, newnode);
	else
		root->right = InsertNode(root->right, newnode);
	return root;
}
void GetData(TreeNode **root)
{
	TreeEntry data;
	TreeNode *newnode;
	int i, n;
	printf("Enter how many records do you want to  key in: ");
	scanf("%d", &n);
	for(i=1;i<=n;i++)
	{
		printf("\nEnter name and telephone number for record # %d: ", i);
		scanf("%s %d", data.name, &data.phone);
		newnode = MakeTreeNode(data);
		*root = InsertNode(*root,newnode);
	}
}
TreeNode * TreeSearch(TreeNode *root, KeyType target)
{
	if(root)
	{
		if(target < root->entry.name)
			root = TreeSearch(root->left,target);
		else if(target > root->entry.name)
			root = TreeSearch(root->right,target);
	}
	return root;
}



Boolean TreeEmpty(TreeNode *root)
{
	return root == NULL;
}

void DeleteNodeTree(TreeNode **p)
{
	TreeNode *r,*q;
	r = *p;
	if(r == NULL)
		printf("Attempt to delete nonexistent node from binary tree");
	else if(r->right == NULL)
	{
		*p = r->left;
		free(r);
	}
	else if(r->left == NULL)
	{
		*p = r->right;
		free(r);
	}
	else
	{
		for(q = r->right; q->left; q = q->left)
		{
			q->left = r->left;
			*p = r->right;
			free(r);
		}
	}
}
void Inorder(TreeNode *root)
{
	if(root)
	{
		Inorder(root->left);
		printf("%s\n", root->entry.name);
		Inorder(root->right);
	}
}
void PrintEntry(TreeEntry entry)
{	
	printf("%s\n%d",entry.name,entry.phone);
}
void Menu(void)
{
	printf("\nSelect your choice:\n");
	printf("1. Searching for data\n");
	printf("2. Insert new data\n");
	printf("3. Delete a data\n");
	printf("4. View phone list\n");
	printf("5. Quit\n");
	printf("Choice: ");
}


void main()
{
	TreeNode *root, *searchnode=NULL, *deletenode=NULL, *newnode, tnode;
	int choice, cont=1;
	KeyType nama;
	TreeEntry newentry;
	CreateTree(&root);
	GetData(&root);
	while(cont==1)
	{
		Menu();
		scanf("%d", &choice);
		switch (choice)
		{
		case 1:
			printf("Enter your friend's name: ");
			fflush(stdin);
			gets(nama);
			searchnode=TreeSearch(root,nama);
			if(searchnode!=NULL)
				PrintEntry(searchnode->entry);
			else
				printf("Not found.\n");
				break;
			case 2:
				printf("Enter your friend's name: ");
				scanf("%s",newentry.name);
				printf("Enter your friend's phone number: ");
				scanf("%d", &newentry.phone);
				newnode=MakeTreeNode(newentry);
				root=InsertNode(root,newnode);
				break;
			case 3:
				printf("Enter your friend's name: ");
				scanf("%s", nama);
				deletenode=TreeSearch(root,nama);
				if(!deletenode)
				printf("Entry does not exist in the phonebook.\n");
				else
				{
					printf("Are you sure want to delete %s entry in thephonebook? Yes=1, No=0: ",deletenode->entry.name);
					fflush(stdin);
					if(getchar()=='1')
					{
						//DeleteKeyTree(&root,&tnode,nama);
						DeleteNodeTree(&root);
						printf("%s is already deleted from the phonebook.\n", nama);
					}
					else
						printf("%s is not deleted from the phonebook.\n", nama);
				}
				break;
			case 4:
				printf("My telephone book\n");
				Inorder(root);
				break;
			case 5:
				cont=0;
				break;
			default:
				printf("Invalid choice\n");
		}
	}
}

anybody plz can check for me the function TreeSearch() ?

[thefalcon79]

any one can review the code for me plz

thnx

[Adak]

Let me preface by saying I know less than you do about ADT tree's.

In your treesearch function, you have this:

TreeNode * TreeSearch(TreeNode *root, KeyType target)
{
	if(root)
	{
		if(target < root->entry.name)
			root = TreeSearch(root->left,target);
		else if(target > root->entry.name)
			root = TreeSearch(root->right,target);
	}
	return root;
}

It looks like you're trying to compare strings directly, instead of using strcmp().

if((strcmp(target, root->entry.name)) == 0)

A direct comparison works with numbers and with a char, but not with strings, in C

[thefalcon79]

thnx man for ur respond
i though no one gonna help me here :-s

u r right, man
i tried ur idea and it's almost work. but i do need to check the node in the tree if > or < to move inside the tree. so i cannt use only if the string1 == string2
i need to check > or <

any idea's, dude

thnx again

[Adak]

You're welcome.

The strcmp() function will give you > == or < by the digit it returns. If string1 > string2 you get 1 returned. If string 1 < string 2 you get -1 returned. Identical stings, get 0 as the return value from strcmp().

[thefalcon79]

yeah dude
i just tried it and it's working thnx a lot
just still have problem with the delete function, and working it

thnx alot man