Re: simplebinary tree
- From: CBFalconer <cbfalconer@xxxxxxxxx>
- Date: Sun, 11 Nov 2007 12:23:22 -0500
CBFalconer wrote:
sophia.agnes@xxxxxxxxx wrote:
this is a simple binary tree program done by me for learning node
deletions in a binary tree, how good is the deletion method ????
can anyone suggest corrections/improvements ????
These things are highly data and algorithm sensitive. For example,
you really want to keep such trees from degenerating into lists.
This involves various means of maintaining reasonable balance. So
the first thing to do is to settle this matter, and describe it in
words (including deciding to ignore the problem).
You have done a fairly good job of indenting etc, but far from
perfect. I recommend the use of 'indent' program, available (from
gnu) for everywhere. If I have time I will later apply it and
follow with some editing to illustrate some of my meanings.
Following is the rough rework I semi-promised. Note the following:
1. Prototypes are eliminated. Instead, functions are declared
at appropriate places, thus eliminating copying of headers.
2. I have reduced the excess vertical spaceing.
3. I have added clear inter-function markers.
In general you should also remove the 'assert' function. Learn to
detect and react to errors yourself. You should never use the
scanf function(s) without checking their return values. (This will
help removing the asserts). You should use function return values,
for example the search function should return either NULL (for
failure) or the appropriate pointer. Make sure every malloced
memory chunk is eventually freed, avoiding memory leaks.
A printf of nothing but a constant string can be replaced by a
puts, unless you don't want the terminal '\n'.
You show great promise. You do tend to over-complicate functions.
For example, the search has some sort of extra parameters to return
parentage. I haven't followed the usage, but I react to the
complexity of the resultant function and the excess parameters
needed.
You should look up AVR trees and red/black trees. This reflects my
original suggestions on adequate commenting. Also use more
descriptive variable names. Draw linkage pictures before and after
various operations to make the processes clear.
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef struct node {
struct node *left;
struct node *right;
int val;
} sn;
/* ---------------- */
sn *allocate(int n)
{
sn *node;
node = malloc(sizeof *node); /* note revision */
assert(node != NULL);
node->left = NULL;
node->right = NULL;
node->val = n;
return node;
} /* allocate */
/* ---------------- */
void insert(sn **sr, int num)
{
if (*sr == NULL) *sr = allocate(num);
else if (num < (*sr)->val) insert(&((*sr)->left), num);
else insert(&((*sr)->right), num);
} /* insert */
/* ---------------- */
void inorder(sn *root)
{
if (root != NULL) {
inorder(root->left);
printf("%d\t", root->val);
inorder(root->right);
}
} /* inorder */
/* ---------------- */
void search(sn **root, int num, sn **par, sn **x, int *found)
{
sn *q;
q = *root;
*par = NULL;
*found = 0;
while (q != NULL) {
if (q->val == num) { /* Should be third, not first */
*x = q;
*found = 1;
return;
}
*par = q;
if (q->val < num) q = q->right;
else q = q->left;
}
} /* search */
/* ---------------- */
void delete(sn **root, int num)
{
int found;
sn *parent, *x;
sn *temp, *temp1;
if ((*root)->val == num
&& (*root)->left == NULL && (*root)->right == NULL) {
*root = NULL;
return;
}
parent = x = NULL;
search(root, num, &parent, &x, &found);
if (found == 0) {
puts("Data to be deleted not found");
return;
}
/* if the node to be deleted has no child. */
if (x->left == NULL && x->right == NULL) {
if (parent->left == x) parent->left = NULL;
else parent->right = NULL;
free(x);
return;
}
/* if the node to be deleted has only right child */
if (x->left == NULL && x->right != NULL) {
if (parent == NULL) {
*root = x->right;
return;
}
if (parent->left == x) parent->left = x->right;
else parent->right = x->right;
free(x);
return;
}
/* if the node to be deleted has only left child */
if (x->left != NULL && x->right == NULL) {
if (parent == NULL) {
*root = x->left;
return;
}
if (parent->left == x) parent->left = x->left;
else parent->right = x->left;
free(x);
return;
}
/* if the node to be deleted have both child */
if (x->left != NULL && x->right != NULL) {
if (parent == NULL) {
temp1 = temp = (*root)->left;
while (temp->right != NULL) temp = temp->right;
temp->right = (*root)->right;
*root = temp1;
return;
}
temp1 = temp = x->left;
while (temp->right != NULL) temp = temp->right;
temp->right = x->right;
if (parent->left == x) parent->left = temp1;
else parent->right = temp1;
x->left = x->right = NULL;
free(x);
}
} /* delete */
/* ---------------- */
int main(void)
{
sn *bt;
int req, i = 1, num, dv;
bt = NULL;
printf("\n Enter the no: of nodes to be inserted:: ");
scanf("%d", &req);
assert(req > 0);
while (i++ <= req) {
printf("Enter the value of the node you want to insert:: ");
scanf("%d", &num);
insert(&bt, num);
}
printf("Enter the value of the node you want to delete:: ");
scanf("%d", &dv);
assert(dv > 0);
assert(bt != NULL);
delete(&bt, dv);
if (bt == NULL) {
puts("Tree empty");
exit(0);
}
puts(".............................");
printf("IN ORDER TRAVERSAL\n");
puts(".............................\n");
inorder(bt);
puts("");
return (EXIT_SUCCESS);
} /* main */
--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Try the download section.
--
Posted via a free Usenet account from http://www.teranews.com
.
- Follow-Ups:
- Re: simplebinary tree
- From: Richard
- Re: simplebinary tree
- References:
- simplebinary tree
- From: sophia . agnes
- Re: simplebinary tree
- From: CBFalconer
- simplebinary tree
- Prev by Date: Re: Problem when i pass pointers to functions
- Next by Date: Re: Problem when i pass pointers to functions
- Previous by thread: Re: simplebinary tree
- Next by thread: Re: simplebinary tree
- Index(es):
Relevant Pages
|
Loading
