Hello
I have written a program for a binary tree. On compiling one has to
first chose option 1 and then delete or search. Im having some trouble
with the balancing function. It seems to be going into an infinite
loop, i think im messing up with the pointers.
Heres the code.
//press 1, first, Do not press it a second time!!!
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
const int size = 15;
int a[size] =
{800,400,600,300,500,350,450,550,700,650,750,730,900,720,740};
//int a[size] = {800, 700, 750,720,770};
int counter1, counter2; //for traverse
//int a[size];
// "node" is a struct for a binary tree.
struct node{
int number;
char direction;
struct node *left, *right, *parent;
};
node *tmp =NULL;
// node pointers
node *p, *root; //p = current node (temp node)
void make_tree(node *p, int num);
void search_tree();
node* search_pos(node* p ,int num); //search tree looks for the return
//void add_element();
void delete_node(node *current);
void delet();
void balance_tree(node *tmp);
void print_tree( node *tmp, int w, int z, int t);
int get_choice();
void add2tree();
int left_trav(node *p);
int right_trav(node *p);
int x, y;
int w=32,z=2, t=32; //t responsible for offset (spread)
int del_element=0;
//int choice;
int main()
{
int choice;
/*
for (int k=0; k < size; k++)
a[k] = random(1000);
*/
while(1) {
choice = get_choice();
switch(choice){
case 1: add2tree(); break;
case 2: clrscr(); print_tree(root, w, z, t);delet();break;
case 3: search_tree();break;
case 4: balance_tree(root); break;
case 5: clrscr(); print_tree(root, w, z, t); getch(); break;
case 6: break;
default: break;
} // switch
if (choice == 6) break;
} // while
// getch();
return 0;
} // main
int get_choice() {
int choice;
clrscr();
gotoxy(15,5);
cout<<"\n1. Add to Tree";
cout<<"\n2. Delete from Tree";
cout<<"\n3. Search the Tree";
cout<<"\n4. Balance the Tree";
cout<<"\n5. Print the Tree";
cout<<"\n6. Quit ";
cout<<"Enter your choice ( 1 - 6) : ";
int x= wherex();
int y = wherey();
while(1) {
gotoxy(x,y);
clreol();
cin >> choice;
if ( ( choice >0 ) && ( choice <=6 ) )
return choice;
putch(7);
}
}
void add2tree() {
int num;
for ( int i =0; i < size; i++) {
num = a[i];
node *p = new node;
if ( p == NULL ) {
cout << "cannot assign memory" << endl;
exit(1);
}
p -> number = num;
p -> right = NULL;
p -> left = NULL;
p -> parent = NULL;
make_tree(p, num);
} //for
getch();
}
void print_tree(node *temp, int w, int z, int t){
t=t/2; // t =32 is the offset
if (temp!= NULL) {
print_tree(temp->left, w-t, z+3, t);
// getch();
gotoxy(w,z);
cout<<temp->number;
print_tree(temp->right, w+t, z+3, t);
}
}
void search_tree() {
int num;
node *current;
node *tmp = root; // Tmp scans list
clrscr();
if (root == NULL) {
cout << "THE TREE IS EMPTY ...";
getch();
}
else {
while (1) {
clrscr();
print_tree(root,w,z,t);
gotoxy(15,25);
cout << "Enter the element you want to search for (-1
to quit): ";
cin >> num;
if (num == -1)
break;
current = search_pos(tmp, num); ////
if (current == NULL)
cout << endl<<num << " was not found in the
tree...";
getch();
}
// if (current == NULL)
// cout << endl<<num << " was not found in the
tree...";
getch();
} // while
} // else
void make_tree(node *p, int num)
{
node *temp = root;
if ( root == NULL ) { //root =current
root = p;
root -> direction = 'o';
}
else { // if root exists
while(1) {
/////////////////////////////////left side of tree ///////////
if ( num < temp -> number ) { // left branch of tree
if ( temp -> left != NULL ) {
temp = temp -> left;
continue; //goes back to the while(1) above
}
else {
temp -> left = p;
p -> direction = 'l';
p -> parent = temp;
} // else
break;
} // end left side
/////////////////////// right side of tree///////////////
if( num > temp -> number ) { // right link
if ( temp -> right != NULL ) { // if right
sidecontains a val
temp = temp -> right; // right link becomes temp
continue;
}
else { // if a right link does not exist
temp -> right = p;
p -> parent = temp;
p->direction = 'r';
} // else
break;
}
if ( temp != p )
continue;
} // while(1)
} // else (if root exists)
}
void delete_node(node* current) {
// node is a leaf
if ( (current->left ==NULL) && (current->right==NULL) ){
if (current ==root)
root = NULL;
if (current->direction =='l')
current->parent->left= NULL;
if (current -> direction=='r')
current->parent->right = NULL;
}
// left node is empty, chk right node
if (current->direction ==NULL){
if (current->direction == 'o'){
current->right-> direction = 'o';
current -> right -> parent = NULL;
root = current ->right;
}
else
if ( current -> direction == 'l' ) {
current -> right -> direction = 'l';
current -> right -> parent = current -> parent;
current -> parent -> left = current -> right ;
}
else { // if ( current -> direction== 'r' )
current -> parent -> right = current -> right;
current -> right -> parent = current -> parent;
}
}
/////////if the right tree is not empty
if (current->right == NULL) { // right tree is empty, left tree not
empty
if ( current -> direction == 'o' ) { // but left is not
empty
current -> left -> direction = 'o';
current -> left -> parent = NULL;
root = current -> left;
}
else
if ( current -> direction == 'l' ) {
current -> parent -> left = current -> left;
current -> left -> parent = current -> parent;
}
else { // if ( current -> direction == 'r' )
current -> left -> direction = 'r';
current -> left -> parent = current -> parent;
current -> parent -> right = current -> left;
}
}
else {
////////// // case if both subtrees exist
node *previous = current -> right;
if ( current -> direction == 'o' ) {
root = previous;
current -> right -> direction = 'o';
current -> right -> parent = NULL;
while ( previous -> left != NULL ) {
previous = previous -> left;
//
////////
}
current -> left -> parent = previous;
previous -> left = current -> left;
} //if
else
if ( current -> direction == 'l' ) {
current -> right -> direction= 'l';
previous -> parent = current -> parent;
current-> parent -> left = previous;
while ( previous -> left != NULL ) {
previous = previous -> left;
////////
}
current -> left -> parent = previous;
previous -> left = current -> left;
}
else {
// current-> direction== 'r'
previous -> parent = current-> parent;
current -> parent -> right = previous;
while ( previous -> left != NULL ) {
previous = previous -> left;
continue;
}
current-> left -> parent = previous;
previous -> left = current-> left;
}
}
{}
{}
delete current;
}
void delet(){
while(1) {
if ( !root) {
cout << "empty tree\n";
getch();
break;
}
clrscr();
print_tree(root, w, z, t);
gotoxy(25,25);
cout<<"\nEnter the element you want to delete( -1 to quit): ";
cin>>del_element;
if (del_element == -1 )
break;
node *current = search_pos(root, del_element);
delete_node(current);
getch();
} // while
}
void balance_tree(node *tmp){
node *predecessor, *mid_node=root;
int left_nodes, right_nodes, diff, tmp_root; //
// int counter1 = 0, counter2 = 0;
while (1) {
// int counter1 = 0, counter2 = 0;
//count the number of nodes on both side of root
left_nodes = left_trav(mid_node->left);
right_nodes = right_trav(mid_node->right);
//if the |diff| <= 1,=>root node is root
diff = left_nodes - right_nodes;
if ( abs( diff) <= 1 )
break;
// left tree > right tree then predecessor is rightmost of 1st left
node
if ( diff > 0 ) {
predecessor = mid_node -> left ;
while ( predecessor -> right != NULL )
predecessor = predecessor -> right;
node *tempo;
tempo = predecessor -> left;
if ( predecessor != mid_node -> left ) {
if ( tempo != NULL ) {
while ( tempo != NULL && tempo -> left != NULL ) {
tempo = tempo -> left;
}
} // if tempo != NULL
mid_node -> left -> parent = tempo; ////// problem
tempo -> left = mid_node -> left;
predecessor -> parent -> right = NULL;
} // predecessor != mid_node -> left
mid_node -> direction = 'r';
predecessor -> parent = mid_node -> parent;
if ( predecessor -> direction == 'l' )
predecessor -> parent -> left = predecessor;
if ( predecessor -> direction == 'r' )
predecessor -> parent -> right = predecessor; // problem 2
mid_node -> parent = predecessor;
mid_node -> left = NULL;
predecessor -> right = mid_node;
if ( mid_node == root ) {
predecessor -> direction = 'o';
root = predecessor;
}
else
predecessor -> direction = 'l';
clrscr();
print_tree(root, w, z, t);
getch();
mid_node = predecessor;
} // if left tree > right tree then predecessor is rightmost
...
// if right tree > left tree, then predecessor is leftmost of 1st
right node
else { // right tree > left tree
predecessor = mid_node -> right;
while ( predecessor -> left != NULL )
predecessor = predecessor -> left;
node *tempo2;
tempo2 = predecessor -> right;
if ( predecessor != mid_node -> right ) {
if ( tempo2 != NULL ) {
while ( tempo2 != NULL && tempo2 -> right != NULL )
{
tempo2 = tempo2 -> right;
}
}
mid_node -> right -> parent = tempo2;
tempo2 -> right = mid_node -> right;
predecessor -> parent -> left = NULL;
}
mid_node -> direction = 'l';
predecessor -> parent = mid_node -> parent;
if ( predecessor -> direction == 'r' )
predecessor -> parent -> right = predecessor;
if ( predecessor -> direction == 'l' )
predecessor -> parent -> left = predecessor;
mid_node -> parent = predecessor;
mid_node -> right = NULL;
predecessor -> left = mid_node;
if ( mid_node == root ) {
predecessor -> direction = 'o';
root = predecessor;
}
else
predecessor -> direction = 'r';
clrscr();
print_tree(root, w, z, t);
getch();
mid_node = predecessor;
} // else right tree > left tree
gotoxy(2,23);
cout << "end of one interation";
getch();
counter1=0;counter2=0;
} // while
//count the sub trees
if ( mid_node -> right != NULL )
balance_tree( mid_node -> right);
if ( mid_node -> left != NULL )
balance_tree( mid_node -> left );
}
node* search_pos(node* tmp, int num){
// node *tmp=root;
if (tmp!= NULL) {
if (tmp->number==num)
return tmp;
if (num < tmp->number)
search_pos(tmp->left, num);
else
if (num > tmp->number)
search_pos(tmp->right, num);
}
else
return NULL;
}
int left_trav(node *p){
int lcounter;
if (p != NULL )
counter1++;
else
return counter1;
lcounter = left_trav(p->left);
lcounter = left_trav(p->right);
}
int right_trav(node *p){
int rcounter;
if (p != NULL )
counter2++;
else
return counter2;
rcounter = right_trav(p->left);
rcounter = right_trav(p->right);
}
/*
if (temp!= NULL) {
print_tree(temp->left, w-t, z+3, t);
gotoxy(w,z);
cout<<temp->number;
print_tree(temp->right, w+t, z+3, t);
}
int right_trav(node *p){
node *tmp;
tmp = p;
int rcounter;
if (tmp != NULL )
counter++;
else
return counter;
rcounter = right_trav(tmp->left);
rcounter = right_trav(tmp->right);
}
|