exercises in c language. I need a person who know c language
mr.su
Chapter26.pdf
CHAPTER - 26
BINARY TREES
CHAPTER 26
BINARY TREES
INTRODUCTION (Reading)
BINARY TREE STRUCTURE
BUILDING A BINARY TREE
BINARY TREE IMPLEMENTATION
OTHER RECURSIVE TRAVERSALS
NON RECURSIVE TRAVERSALS
DELETING A NODE FROM BINARY SEARCH TREE
BINARY TREES
BINARY TREE STRUCTURE
BINARY TREES
BUILDING A BINARY TREE void printout (node * tree)
{
if (tree->left)
printout (tree->left);
printf ("%d\n", tree->val);
if (tree->right)
printout (tree->right);
}
void main()
{
node * curr, * root;
int i; root = NULL;
for (i = 1; i <=10; i++)
{
curr = (node *) malloc (sizeof (node));
curr->left = curr->right = NULL;
curr->val = rand();
insert (&root, curr);
}
printout (root);
}
#include<stdlib.h>
#include<stdio.h>
struct tree_el {
int val;
struct tree_el * left;
struct tree_el * right;
};
typedef struct tree_el node;
void insert (node ** tree, node * item)
{
if (!(*tree))
{
*tree = item;
return;
}
if (item->val<(*tree)->val)
insert (&(*tree)->left, item);
else if (item->val>(*tree)->val)
insert (&(*tree)->right, item);
}
BINARY TREES
#include <stdio.h>
#include <stdlib.h>
struct nodetype {
int info;
struct nodetype *left;
struct nodetype *right;
};
typedef struct nodetype *NODEPTR;
typedef struct nodetype NODE;
NODEPTR maketree (int);
void intrav (NODEPTR);
NODEPTR get_treenode ();
void setbintree (NODEPT, int);
NODEPTR ndptr;
NODE nd;
NODEPTR current_ptr;
NODE current_nd;
BINARY TREE IMPLEMENTATION
void main ()
{
NODEPTR btree = NULL;
int number;
printf ("please enter the next node info: ");
scanf ("%d", &number);
btree = maketree (number);
printf ("please enter the next node info: ");
while (scanf ("%d", &number) != EOF)
{
setbintree (btree, number);
printf ("please enter the next node info: ");
} /* end of while scanf */
printf ("\n\n inordered binary tree node info:\n");
intrav (btree);
printf ("\n end of inordered binary tree node
search\n");
return;
} /* end of main program */
BINARY TREES
BINARY TREE IMPLEMENTATION
void intrav (NODEPTR tree)
{
if (tree != NULL)
{
intrav (tree->left); /* traverse the left subtree */
printf ("%d \n", tree->info); /* visit the node */
intrav (tree->right);// traverse the right subtree
} /* end if not null */
return;
} /* end of function intrav */
NODEPTR get_treenode ()
{
NODEPTR p;
p = (NODEPTR) malloc (sizeof (struct
nodetype));
return (p);
} /* end of getnode function */
NODEPTR maketree (int x)
{
NODEPTR p;
p = get_treenode ();
p->info = x;
p->left = NULL;
p->right = NULL;
return (p);
} /* end of maketree function */
void setbintree (NODEPTR p, int x)
{
NODEPTR s = p;
while (s != NULL)
{
if (s->info == x)
{
printf ("\n duplicate entry \n");
return;
}
BINARY TREES BINARY TREE IMPLEMENTATION
if (s->info > x)
if (s->left == NULL)
{
s->left = maketree (x);
return;
}
else
s = s->left;
else
if (s->right == NULL)
{
s->right = maketree (x);
return;
}
else
s = s->right;
} /* end of while loop */
return;
} /* end of function setbintree */
Output of the above program:
please enter the next node info: 10
please enter the next node info: 6
please enter the next node info: 14
please enter the next node info: 5
please enter the next node info: 8
please enter the next node info: 11
please enter the next node info: 18
please enter the next node info: ^Z
inordered binary tree node info:
5 6 8 10 11 14 18
10
/ \
6 14
/ \ / \
5 8 11 18
BINARY TREES
OTHER RECURSIVE TRAVERSALS
intraversal algorithm:
intrav (NODEPTR tree)
{
if (it is not a NULL tree)
{
intrav (left subtree); //traverse the left subtree
print the node info /* visit the node */
intrav (right subtree);// traverse right subtree
}
}
pretraversal algorithm:
pretrav (NODEPTR tree)
{
if (it is not a NULL tree)
{
print the node info /* visit the node */
pretrav (left subtree);// traverse left subtree */
pretrav (right subtree);// traverse right subtree
}
}
posttraversal algorithm:
postrav (NODEPTR tree)
{
if (it is not a NULL tree)
{
postrav (right subtree);// traverse right */
postrav (left subtree);// traverse left subtree
print the node info /* visit the node */
}
}
Output of the pretarversal program:
10
6
5
8
14
11
18
BINARY TREES
NON RECURSIVE TRAVERSALS
• Non recursive tree traversals require
a stack or a queue implementation.
• For inordered, postordered, and
preordered traversals a tree stack is
required to hold the node which was
visited.
• When the traversal returns from
the previous visit, it will remember
which node was visited, and whose
child trees need to be visited
10
/ \
6 14
/ \ / \
5 8 11 18
To start an inordered traversal, first the
root is visited, and root node is
stacked. The order is shown below:
1. Stack the root node
2. Unstack --> 10
3. Stack the left and right child nodes of
node 10 (6, 14)
4. Unstack --> 6
5. Stack the left and right child nodes of
node 6 (5, 8)
6. Unstack --> 5
7. Stack the left and right child nodes of
node 5 (NULL, NULL)
8. Unstack --> NULL
9. NO stacking when the child is null
BINARY TREES
There are three cases to be considered in
deleting a node with key key from a binary
search tree. If the node to be deleted has no
children, it may be deleted without further
adjustment to the tree. If the node to be
deleted has only one sub tree, its only child
can be moved up to take its place. If,
however, the node p to be deleted has two
sub trees, its inorder successor s must take
its place.
Considering the inorder successor to be left
most node from the right sub tree. The
inorder successor cannot have a left sub
tree. Thus right child of s can be moved up
to take the place of s. If no node with key
key exists in the tree, the tree is left
unchanged.
Algorithm for deleting nodes:
p = tree;
q = null;
/* Search for the node with the key key,
set p to point to the node and q to its
parent, if any. */
while ( p != null && k (p) != key)
{
q = p;
p = ( key < k (p) ) ? Left (p) :
right (p);
} /* end of while */
if (p == null)
/* The key does not exists in the tree,
leave the tree unchanged */
return;
DELETING A NODE FROM BINARY SEARCH TREE
BINARY TREES
/*set the variable rp to the node that will replace node (p).
first two cases: the node to be deleted has at most one child. */
if (left (p) == null )
rp = right (p);
else
if (right (p) == null )
rp = left (p);
else
{/* third case: node(p) has two children. Set rp to the
inorder successor of p and f to the parent of rp. */
f = p;
rp = right (p);
s = left (rp); // s is left child of rp */
while (s != null)
{
f = rp;
rp = s;
s = left (rp);
} /* end of while */
if (f != p) // at this point, rp is the
inorder successor of p */
{
left (f ) = right (rp); /*p is not
parent of rp, set it to left(p) */
right (rp) == right (p);
/* remove node rp and replace */
} /* end of if (f != p) */
left (rp) = left (p); /* set left child
of rp, rp takes place of p */
} /* end of else */
/* insert node(rp) into position formerly
occupied by node(p) */
if (q == null) // node(p) was the root
tree = rp;
else
(p == left (q) ) ? left(q) = rp :
right (q) = rp;
freenode (p);
return;
DELETING A NODE FROM BINARY SEARCH TREE
BINARY TREES
Three cases will be considered here which
represent most cases the keys are deleted.
Case 1:
The node with the key has no
children, no left or right child of
the node to be deleted (easy).
Deleting Node with key 15
Case 2:
The node with search key has only
one child, either left or right child.
Deleting Node with key 5
Case 3:
Left subtree and right subtree of
the node to be deleted to be taken
care (hard).
Deleting Node with key 11
DELETING A NODE FROM BINARY SEARCH TREE
BINARY TREES DELETING A NODE FROM BINARY SEARCH TREE
