P: n/a

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, wt, 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>rightdirection = '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;
currentparent left = previous;
while ( previous left != NULL ) {
previous = previous left;
////////
}
current left parent = previous;
previous left = current left;
}
else {
// currentdirection== 'r'
previous parent = currentparent;
current parent right = previous;
while ( previous left != NULL ) {
previous = previous left;
continue;
}
currentleft parent = previous;
previous left = currentleft;
}
}
{}
{}
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);
}  
Share this Question
P: n/a
 wh*************@gmail.com writes:
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.
I wouldn't bother to implement that balancing algorithm. It's
both slower and harder to implement than more efficient
approaches. Try the one described here: http://adtinfo.org/libavl.html/BalancingaBST.html
(This is my webpage.)

Ben Pfaff bl*@cs.stanford.edu http://benpfaff.org  
P: n/a

On Feb 12, 5:13 pm, Ben Pfaff <b...@cs.stanford.eduwrote:
Try the one described here:
A redblack tree is another good form of balanced BST.
Beej  
P: n/a

[Offtopic in comp.lang.c  crossposted to comp.programming and
followups set.]
Ben Pfaff said: wh*************@gmail.com writes:
>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.
I wouldn't bother to implement that balancing algorithm. It's
both slower and harder to implement than more efficient
approaches.
I couldn't decode his code sufficiently to tell whether your advice to
him would also constitute advice to me, so I'd appreciate feedback.
My technique is this: each node keeps counts of its left children and
right children. (Housekeeping is done when nodes are promoted and when
nodes are deleted.) To balance a tree, I use the childcounts to dodge
left or right until I've found the ideal root node (the one which will
have equally populated subtrees, +/ 1 of course), and I rotate that
node to the root. Then I recurse into the subtrees. It works well and
I'm happy with the performance. Shouldn't I be?

Richard Heathfield
"Usenet is a strange place"  dmr 29/7/1999 http://www.cpax.org.uk
email: rjh at the above domain,  www.  
P: n/a

Ben Pfaff wrote:
wh*************@gmail.com writes:
>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.
I wouldn't bother to implement that balancing algorithm. It's
both slower and harder to implement than more efficient
approaches. Try the one described here: http://adtinfo.org/libavl.html/BalancingaBST.html
(This is my webpage.)
Thought I knew your name from somewhere... ;)
Jeff   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 10474
 replies: 4
 date asked: Feb 13 '07
