Hey there... can anyone suggest code for deleting a term from a tree.. I have a base code for searching the tree... we have to take into account whether or not the term to be deleted has children or not...
Printable View
Hey there... can anyone suggest code for deleting a term from a tree.. I have a base code for searching the tree... we have to take into account whether or not the term to be deleted has children or not...
If what you are going to delete has no children, then the pointer to the node you are deleting should be set to NULL. If the node you are deleting has one child node/subtree, then the pointer to the node you are deleting should be set to the node/subtree. If the what you are deleting has two child nodes/subtrees, then the pointer to the node you are deleting can be set to one of the subtrees, left or right it doesn't matter, and you can then reinsert the remaining node/subtree back into the root of the tree using whatever add/insert function you have created to insert a new node into the tree.
Any suggested code for that? just not sure how to do it code wise... thanks for replying!
Try This one:
see youCode:tree dtree(tree root,int key)
{
tree p,p2;
if(!root) return root;
if((root->e.id)==key) /* delete root */
{
if(root->lift == root->right)
{
free(root);
return NULL;
}
/* or if one subtree is null */
else if(root->lift ==NULL)
{
p=root->right;
free(root);
return p;
}
else if(root->right ==NULL)
{
p= root->lift;
free(root);
return p;
}
/* or if both subtree are ther */
else
{
p2=root->right;
p=root->right;
while(p->lift) p=p->lift;
p->lift = root->lift;
free(root);
return p2;
}
}
if(root->e.id < key) root->right = dtree(root->right,key);
else root->lift= dtree(root->lift,key);
return root;
}
how would you write it if you were using strings and files in the tree?
i.e. if the actual nodes of the tree contains a string of words
if you know what i mean. :(
here's a program i wrote but i need help correcting it
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 40
typedef struct treenode
{
char word[SIZE];
int count;
struct treenode *left;
struct treenode *right;
} treenode; //structure
treenode* insert(treenode*, char*);
void inorder(treenode*);
void preorder(treenode*, FILE*);
void menu();
void check_choice(treenode* tree, char);
void freetree(treenode*);
int deletenode(treenode*, char);
//begin main function
int main()
{
char str[30];
FILE* fptr;
int check =0;
char ch;
treenode* root =NULL;
if ( (fptr = fopen("btree.txt","r")) == NULL)
{
fprintf(stderr, "Error in opening file test.txt");
return(0);
}
while(fscanf(fptr, "%s", str) != EOF)
root = insert(root, str);
menu();
scanf(" %c", &ch);
while ((ch != 'e') && (ch != 'E'))
{
check_choice(root, ch);
menu();
scanf(" %c", &ch);
}
fclose(fptr);
if ( (fptr = fopen("btree.txt","w")) == NULL)
{
fprintf(stderr, "Error in opening file test.txt for writing");
return(0);
}
preorder(root, fptr);
return(1);
}
treenode* insert(treenode* root, char word[30])
{
if(root == NULL)
{
root = (treenode *) malloc(sizeof(treenode));
strcpy(root->word, word);
root->left = NULL;
root->right = NULL;
root->count = 1;
}
else
{
if((strcmp(word,root->word))==0)
{
root->count++;
}
else if((strcmp(word,root->word)) < 0)
{
root->left = insert(root->left, word);
}
else if((strcmp(word,root->word)) > 0)
{
root->right = insert(root->right, word);
}
}
return(root);
}
void search(treenode *root, char *term)
{
int l;
if (root == NULL)
{
printf("Term not found\n");
return;
}
else if ((l = strcmp (root->word, term)) == 0)
{
printf("Term found in tree\n");
return;
}
else if (l > 0)
search(root->left, term);
else
search(root->right, term);
}
void inorder(treenode* root)
{
if(root != NULL)
{
inorder(root->left);
printf("\n %s %d",root->word, root->count);
inorder(root->right);
}
}
void preorder(treenode *root, FILE *fptr)
{
if (root != NULL)
{
preorder(root->left, fptr);
fprintf(fptr, "%s ",root->word);
preorder(root->right, fptr);
}
}
void menu()
{
printf("\n\tExit program (e)\n");
printf("\tDisplay tree (d)\n");
printf("\tSearch tree for string (s)\n");
printf("\tAdd new string to tree (a)\n");
return;
}
void check_choice(treenode *tree, char choice)
{
char term[WORD_SIZE];
switch(choice)
{
case 'e' : printf("Exiting ...\n");
break;
case 'd' : inorder(tree);
break;
case 's' : printf("Please enter search term\n");
scanf ("%s", term);
search(tree, term);
break;
case 'a' : printf("Please enter term to be added\n");
scanf ("%s", term);
tree = insert(tree, term);
break;
case 'b' : printf("please enter a term to be deleted\n");
scanf("%s" , term);
del(tree, term);
break;
}
}
//begin function to delete a value from the tree
treenode* del(treenode* tree, char tofind)
{
char term=0;
treenode* parent=NULL, *deleted=NULL, *suc, *word;
if (tree=NULL)
printf("tree empty\n");
term= search(tree, term);
if(!term)
printf("string %s is not in tree\n", term);
else
{
if(root->leftptr==NULL && root->rightptr==NULL)
{
if(parent==NULL)
tree=parent;
else if(parent->leftptr==deleted)
parent->leftptr=NULL;
else
parent->rightptr=NULL;
free(deleted);
}
else if (deleted->leftptr==NULL && deleted->rightptr!=NULL)
{
if(parent==NULL)
tree=deleted->rightptr;
else if (parent->leftptr==deleted)
parent->leftptr=deleted->rightptr;
else
parent->rightptr=deleted->leftptr;
free(deleted);
}
else if(deleted->leftptr!=NULL && deleted-.rightptr==NULL)
{
if (parent==NULL)
tree=deleted->leftptr;
else if(parent->leftptr==deleted->leftptr)
parent->leftptr=deleted->leftptr;
else
parent->rightptr=deleted->leftptr;
free(deleted);
}
else
{
parent=deleted;
suc=deleted->rightptr;
while(suc->leftptr!=NULL)
{
parent=suc;
suc=suc->leftptr;
}
strcpy(deleted->word,suc->word);
deleted=suc;
parent->rightptr=suc->rightptr;
parent->leftptr=suc->leftptr;
free(suc);
}
}
return(tree);
}
the program is right without the delete function,so can anyone correct it for me?:confused:
I'm not sure why but you end up searching for term=0 here andCode:char term=0;
treenode* parent=NULL, *deleted=NULL, *suc, *word;
if (tree=NULL)
printf("tree empty\n");
term= search(tree, term);
I don't understand why toFind is a charecter and not a c style string when your tree holds strings.
The easiest way to delete from a tree is to do it recursivly.
So you have have a prototype for your function like
treenode* del(treenode** tree, char* toFind);
And then you will probably have a line such as
Code:int t = strcmp(toFind, (*tree)->word);
if (t < 0)
*tree = del((*tree)->left, toFind);
else if (t > 0)
*tree = del((*tree)->right, toFind);
else {
/* handle the three cases */
Probably the easiest way is to draw a picture of each one
the only real tough one is when (*tree)->left != NULL and
(*tree)->right != NULL and for that one you want to change
*tree to the least valued node from the right tree
(the successor) and then delete successor of the
right tree.
}