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,9 00,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);

}