425,534 Members | 1,807 Online Need help? Post your question and get tips & solutions from a community of 425,534 IT Pros & Developers. It's quick & easy.

# Balancing a Binary Tree

 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 #include #include #include #include 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<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<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); } Feb 13 '07 #1
4 Replies

 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/Balancing-a-BST.html (This is my webpage.) -- Ben Pfaff bl*@cs.stanford.edu http://benpfaff.org Feb 13 '07 #2

 P: n/a On Feb 12, 5:13 pm, Ben Pfaff

 P: n/a [Off-topic 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 tofirst chose option 1 and then delete or search. Im having sometrouble with the balancing function. It seems to be going into aninfinite 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 child-counts 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. Feb 13 '07 #4

 P: n/a Ben Pfaff wrote: wh*************@gmail.com writes: >I have written a program for a binary tree. On compiling one has tofirst chose option 1 and then delete or search. Im having some troublewith the balancing function. It seems to be going into an infiniteloop, 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/Balancing-a-BST.html (This is my webpage.) Thought I knew your name from somewhere... ;-) Jeff Feb 14 '07 #5

### This discussion thread is closed

Replies have been disabled for this discussion. 