PROGRAM 3 // PROGRAM: PROGRAM3.CPP AUTHOR: ANTHONY F. ORTIZ #include#include #include #include // DELCARATION OF TREE NODE CLASS. template class TREE_NODE { protected: // KEY INFORMATION. ETYPE ELEMENT; // RIGHT AND LEFT POINTERS. TREE_NODE * LEFT; TREE_NODE * RIGHT; // TREE_NODE CONSTRUCTOR. TREE_NODE (ETYPE E = 0, TREE_NODE * L = 0, TREE_NODE * R = 0) : ELEMENT (E), LEFT (L), RIGHT (R) {} // HEIGHT OF A NODE IN A TREE. friend int HEIGHT (TREE_NODE * T); // A CLASS CALLED BINARY_SEARCH_TREE WILL USE THE TREE NODE // CLASS. friend class BINARY_SEARCH_TREE ; }; // DELCARATION OF BINARY SEARCH TREE CLASS. template class BINARY_SEARCH_TREE { // THESE PROCEDURES WILL BE CALLED BY THE PUBLIC ONES OF THE SAME // NAME. protected: // MAKE AN EMPTY TREE. void MAKE_EMPTY (TREE_NODE * & T); // INSERT AN ELEMENT INTO A TREE. void INSERT (const ETYPE & X, TREE_NODE * & T); // REMOVE AN ELEMENT FROM A TREE. void REMOVE (const ETYPE & X, TREE_NODE * & T); // PRINT THE TREE USING A INORDER TRAVERSAL. // THIS WILL PRINT IT IN SORTED ORDER. void PRINT_TREE (TREE_NODE * T) const; // COPY A TREE. TREE_NODE * COPY (const TREE_NODE * T); // FIND AN ELEMENT IN THE TREE. TREE_NODE * FIND (const ETYPE & X, TREE_NODE * T) const; // FIND THE MINIMUM ELEMENT IN THE TREE. TREE_NODE * FIND_MIN (TREE_NODE * T) const; // FIND THE MAXIMUM ELEMENT IN THE TREE. TREE_NODE * FIND_MAX (TREE_NODE * T) const; // ROOT OF THE TREE. TREE_NODE * ROOT; // THE LAST FIND IN A FIND ROUTINE. TREE_NODE * LAST_FIND; // THESE PROCEDURES WILL CALL THE PROTECTED ONES. public: // CONSTRUCTORS. BINARY_SEARCH_TREE () : ROOT (0), LAST_FIND (0) {} // ERROR MESSAGE WHEN PASS BY VALUE. BINARY_SEARCH_TREE (BINARY_SEARCH_TREE & VALUE) {cout << "TREE PASSED BY VALUE."; operator = (VALUE);} // DESTRUCTOR. virtual ~BINARY_SEARCH_TREE () {MAKE_EMPTY (ROOT); ROOT = LAST_FIND = 0;} // OPERATORS. // COPY A TREE. const BINARY_SEARCH_TREE & operator = (const BINARY_SEARCH_TREE & VALUE); // RETURN A TREE ELEMENT. ETYPE operator () () const {return LAST_FIND != 0 ? LAST_FIND -> ELEMENT : 0;} // MEMBER FUNCTIONS. // CALL MAKE_EMPTY AND ASSIGN 0 TO ROOT AND LAST FIND. void MAKE_EMPTY () {MAKE_EMPTY (ROOT); ROOT = LAST_FIND = 0;} // CALL PRINT_TREE. void PRINT_TREE () const {PRINT_TREE (ROOT);} // ASSIGN LAST_FIND TO THE FUNCTION FIND. virtual int FIND (const ETYPE & X) {return int (LAST_FIND = FIND (X, ROOT));} // ASSIGN LAST_FIND TO THE FUNCTION FIND_MIN. virtual int FIND_MIN () {return int (LAST_FIND = FIND_MIN (ROOT));} // ASSIGN LAST_FIND TO THE FUNCTION FIND_MAX. virtual int FIND_MAX () {return int (LAST_FIND = FIND_MAX (ROOT));} // CALL INSERT. virtual void INSERT (const ETYPE & X) {INSERT (X, ROOT);} // CALL REMOVE. virtual void REMOVE (const ETYPE & X) {REMOVE (X, ROOT);} }; // COPY A TREE USING '=' OPERATOR. template const BINARY_SEARCH_TREE & BINARY_SEARCH_TREE :: operator = (const BINARY_SEARCH_TREE & VALUE) { if (this != & VALUE) { MAKE_EMPTY (ROOT); ROOT = COPY (VALUE.ROOT); LAST_FIND = ROOT; } return * this; } // COPY THE TREE. template TREE_NODE * BINARY_SEARCH_TREE :: COPY (const TREE_NODE * T) { if (T != 0) return new TREE_NODE (T -> ELEMENT, COPY (T -> LEFT), COPY (T -> RIGHT)); else return 0; } // MAKE THE TREE EMPTY. template void BINARY_SEARCH_TREE :: MAKE_EMPTY (TREE_NODE * & T) { if (T != 0) { MAKE_EMPTY (T -> LEFT); MAKE_EMPTY (T -> RIGHT); delete T; T = 0; } } // FIND AN ELEMENT IN THE TREE. template TREE_NODE * BINARY_SEARCH_TREE :: FIND (const ETYPE & X, TREE_NODE * T) const { if (T == 0) return 0; else if (X < T -> ELEMENT) return FIND (X, T -> LEFT); else if (X > T -> ELEMENT) return FIND (X, T -> RIGHT); else return T; } // FIND THE MINIMUM ELEMENT IN THE TREE. template TREE_NODE * BINARY_SEARCH_TREE :: FIND_MIN (TREE_NODE * T) const { if (T == 0) return 0; else if (T -> LEFT == 0) return T; else return FIND_MIN (T -> LEFT); } // FIND THE MAXIMUM ELEMENT OF A TREE. template TREE_NODE * BINARY_SEARCH_TREE :: FIND_MAX (TREE_NODE * T) const { if (T == 0) return 0; else if (T -> RIGHT == 0) return T; else return FIND_MAX (T -> RIGHT); } // INSERT AN ELEMENT INTO THE TREE. template void BINARY_SEARCH_TREE :: INSERT (const ETYPE & X, TREE_NODE * & T) { if (T == 0) { T = new TREE_NODE (X); if (T == 0) cout << "OUT OF SPACE."; } else if (X < T -> ELEMENT) INSERT (X, T -> LEFT); else if (X > T -> ELEMENT) INSERT (X, T -> RIGHT); // ELSE X IS IN THE TREE ALREADY AND DO NOTHING. } // REMOVE AN ELEMENT FROM THE TREE. template void BINARY_SEARCH_TREE :: REMOVE (const ETYPE & X, TREE_NODE * & T) { TREE_NODE * TMP_CELL; if (T == 0) cout << "ELEMENT NOT FOUND."; else if (X < T -> ELEMENT) // GO LEFT. REMOVE (X, T -> LEFT); else if (X > T -> ELEMENT) // GO RIGHT. REMOVE (X, T -> RIGHT); else // FOUND ELEMENT TO BE REMOVED. if (T -> LEFT != 0 && T -> RIGHT != 0) // TWO CHILDREN. { // REPLACE WITH SMALLEST IN RIGHT SUBTREE. TMP_CELL = FIND_MIN (T -> RIGHT); T -> ELEMENT = TMP_CELL -> ELEMENT; REMOVE (T -> ELEMENT, T -> RIGHT); } else // ONE OR ZERO CHILD. { TMP_CELL = T; if (T -> LEFT == 0) // ONLY A RIGHT CHILD. T = T -> RIGHT; else if (T -> RIGHT == 0) // ONLY A LEFT CHILD. T = T -> LEFT; delete TMP_CELL; } } // PRINT THE TREE USING AN INORDER TRAVERSAL. // THIS WILL PRINT IT IN SORTED ORDER. template void BINARY_SEARCH_TREE :: PRINT_TREE (TREE_NODE * T) const { if (T != 0) { PRINT_TREE (T -> LEFT); cout << HEIGHT (T) << " " << T -> ELEMENT << " "; PRINT_TREE (T -> RIGHT); } } // CALCULATE THE HEIGHT OF A NODE. template int HEIGHT (TREE_NODE * T) { if (T == 0) return -1; else return 1 + MAX (HEIGHT (T -> LEFT), HEIGHT (T -> RIGHT)); } int MAX (int A, int B) { if (A > B) { return A; } else { return B; } } // THIS PROGRAM WILL INSERT 40 RANDOM INTEGERS FROM 1000 TO 10000 INTO // A BINARY SEACH TREE AND PRINT THEM IN ASCENDING ORDER. THEN, IT // WILL DELETE 20 ELEMENTS FROM THE TREE, PRINTING THE NEW TREE EVERY // FORTH REMOVAL. int main () { // CLEAR SCREEN. clrscr (); // DECLARE VARIABLE FOR A BINARY SEARCH TREE OF INTEGERS. // IT WILL HOLD THE 40 RANDOM INTEGERS. BINARY_SEARCH_TREE INTEGER_TREE; // HOLDS THE CURRENT RANDOM NUMBER. int RANDOM_NUMBER; // HOLDS THE CURRENT RANDOM NUMBER. NEEDED FOR REMOVAL. int TEMP; // HOLDS THE 40 RANDOM INTEGERS. // THIS WILL BE USED FOR DELETION. int RANDOM_ARRAY [40]; // INSERT 40 RANDOM INTEGERS FROM 1000 TO 10000 INTO THE TREE. for (int I = 0; I <= 39; I++) { // GET RANDOM NUMBER. RANDOM_NUMBER = (rand () % 9000) + 1000; // INSERT IT INTO THE TREE. INTEGER_TREE.INSERT (RANDOM_NUMBER); // ALSO, INSERT IT INTO AN ARRAY. RANDOM_ARRAY [I] = RANDOM_NUMBER; } // PRINT A HEADING AND THEN THE TREE. cout << "AFTER 40 INSERTIONS:\n\n"; INTEGER_TREE.PRINT_TREE (); // PAUSE SO USER CAN SEE THE SCREEN. delay (5000); // REMOVE 20 ELEMENTS FROM THE TREE. for (int J = 0; J <= 19; J++) { // LOOP IF THE RANDOM NUMBER IS NOT IN THE ARRAY. // THIS MIGHT HAPPEN IF IT HAS BEEN REMOVED FROM // TREE AND ARRAY. do { // RANDOM NUMBER FROM 0 TO 39. // INDEX OF THE ARRAY. RANDOM_NUMBER = (rand () % 40); } while (RANDOM_ARRAY [RANDOM_NUMBER] == 0); // HOLD THE RANDOM NUMBER. TEMP = RANDOM_ARRAY [RANDOM_NUMBER]; // PUT 0 IN THE ARRAY OF THE APPROPRIATE INDEX. RANDOM_ARRAY [RANDOM_NUMBER] = 0; // PUT THE RANDOM NUMBER IN THE TEMP VARIABLE INTO // THE RANDOM NUMBER VARIABLE. RANDOM_NUMBER = TEMP; // REMOVE THE RANDOM NUMBER. INTEGER_TREE.REMOVE (RANDOM_NUMBER); // WRITE A HEADING AND SHOW THE NEW TREE. if ((J + 1) % 4 == 0) { cout << "\n\nAFTER 4 DELETIONS:\n\n"; INTEGER_TREE.PRINT_TREE (); // PAUSE SO USER CAN SEE THE SCREEN. delay (5000); } } return 0; } // OUTFILE: PROG3.OUT AFTER 40 INSERTIONS: 1 1004 0 1119 2 1130 11 1346 1 1492 0 1509 3 2090 2 2360 0 2651 1 2816 10 2982 9 3656 0 4252 4 4571 3 4681 2 4734 1 4979 0 4995 5 5126 1 5214 0 5310 2 5441 3 5463 4 5879 6 5948 0 5985 1 6412 2 6558 0 6593 1 6779 7 7415 0 7561 1 8047 0 8092 8 8117 1 8190 0 9571 2 9595 1 9721 0 9995 AFTER 4 DELETIONS: 1 1004 0 1119 2 1130 11 1346 1 1492 0 1509 3 2090 2 2360 0 2651 1 2816 10 2982 9 3656 4 4571 3 4681 2 4734 1 4979 0 4995 5 5310 0 5441 1 5463 2 5879 6 5985 0 6412 2 6558 0 6593 1 6779 7 7415 0 7561 1 8047 0 8092 8 8117 1 8190 0 9571 2 9595 1 9721 0 9995 AFTER 4 DELETIONS: 1 1004 0 1119 2 1130 9 1346 1 1492 0 1509 3 2090 2 2360 0 2651 1 2816 8 2982 3 4681 2 4734 1 4979 0 4995 4 5310 0 5441 1 5463 2 5879 5 6412 2 6558 0 6593 1 6779 6 7415 0 7561 1 8047 0 8092 7 8117 1 8190 0 9571 2 9721 0 9995 AFTER 4 DELETIONS: 0 1004 1 1130 9 1346 1 1492 0 1509 2 2090 1 2360 0 2816 8 2982 3 4681 2 4734 1 4979 0 4995 4 5310 0 5441 1 5463 2 5879 5 6412 2 6558 0 6593 1 6779 6 7415 0 7561 1 8047 7 8117 0 8190 1 9721 0 9995 AFTER 4 DELETIONS: 0 1004 1 1130 8 1346 0 1509 2 2090 1 2360 0 2816 7 4681 2 4734 1 4979 0 4995 3 5441 0 5463 1 5879 4 6412 1 6558 0 6593 5 7415 0 7561 1 8047 6 8117 0 8190 1 9721 0 9995 AFTER 4 DELETIONS: 0 1004 1 1130 7 1346 0 1509 1 2090 0 2360 6 4734 1 4979 0 4995 2 5463 0 5879 3 6412 1 6558 0 6593 4 7415 0 8047 5 8117 0 8190 1 9721 0 9995
BACK TO CS3240 PAGE.