home *** CD-ROM | disk | FTP | other *** search
/ Visual Basic Source Code / Visual Basic Source Code.iso / vbsource / vbdatabs / tree.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1999-03-17  |  11.7 KB  |  456 lines
  1. // ------------------------------- //
  2. // -------- Start of File -------- //
  3. // ------------------------------- //
  4. // ----------------------------------------------------------- // 
  5. // C++ Source Code File Name: tree.cpp
  6. // Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
  7. // Produced by: Doug Gaer
  8. // File Creation Date: 11/07/1996
  9. // Date Last Modified: 03/17/1999
  10. // ----------------------------------------------------------- // 
  11. // ------------- Program description and details ------------- // 
  12. // ----------------------------------------------------------- // 
  13. /*
  14. THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
  15. THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
  16. IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
  17. YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
  18. CORRECTION.
  19.  
  20. This is a simple class implementation of a binary search tree
  21. used to create a tree of character strings. The char * data type
  22. in the TreeNode class is used as a pointer to a pre-allocated
  23. strings. The tree structure itself stores a hierarchal collection
  24. of nodes. Each node stores a pointer to a unique character string
  25. along with left and right pointers to other nodes in the tree.
  26. */
  27. // ----------------------------------------------------------- // 
  28. #include <iostream.h>
  29. #include <string.h>
  30.  
  31. class Tnode; // Forward class name
  32.  
  33. // VisitFunc is a pointer to void(Tnode *Node) that points to
  34. // a visit function used to process node data during tree traversals
  35. typedef void (*VisitFunc)(Tnode *Node); 
  36.  
  37. // (T)ree (N)ode base class
  38. class Tnode
  39. {
  40. public:
  41.   Tnode() { right = left = 0; data = 0; }
  42.   Tnode(char *key, Tnode *l = 0, Tnode *r = 0) {
  43.     data = strdup(key); left = l; right = r; 
  44.   }
  45.   
  46. public:
  47.   char *data;   // data for this tree 
  48.   Tnode *right; // subtree to the right 
  49.   Tnode *left;  // subtree to the left 
  50. };
  51.  
  52. // Binary Search (T)ree class
  53. class Tree : public Tnode
  54. {
  55. public:
  56.   Tree() { root = 0; }
  57.   ~Tree() { Clear(); }
  58.   Tree(const Tree &t) { this->Copy(t); }
  59.   void operator=(const Tree &t) { this->Copy(t); }
  60.   
  61. public:
  62.   int Add(char *key);
  63.   int Remove(char *key);
  64.   int Find(char *key);
  65.   void Clear();
  66.   int Copy(const Tree &t);
  67.   void PrintTree(VisitFunc Visit) { PrintInOrder(root, Visit); }
  68.   int GetHeight() { return Height(root); }
  69.   
  70. private: // Functions for internal processing only
  71.   Tnode *SearchForParent(Tnode *node, char *key, Tnode *&parent, int &side);
  72.   Tnode *Insert(Tnode *&root, char *key, int &exists);
  73.   Tnode *DetachNode(Tnode *&root, Tnode *node, Tnode *parent, int side);
  74.   Tnode *GetParentOfSuccessor(Tnode *node);
  75.   Tnode *Detach(Tnode *&root, char *key);
  76.   int Delete(Tnode *&root, char *key);
  77.   void PrintInOrder(Tnode *tree, VisitFunc Visit);
  78.   void DeleteTree(Tnode *t);
  79.   Tnode *DupTree(Tnode *t);
  80.   int Height(Tnode *t);
  81.   
  82. private:
  83.   Tnode *root; // Pointer to the top of the tree 
  84. };
  85.  
  86. int Tree::Add(char *key)
  87. // Add an entry to the tree. 
  88. {
  89.   int exists;
  90.   Insert(root, key, exists);
  91.   return exists == 0; // Return true if the key did not already exist
  92. }
  93.  
  94. int Tree::Remove(char *key)
  95. // Remove a node from the tree.
  96. // Returns zero if the node does not exist.
  97. {
  98.   return Delete(root, key);
  99. }
  100.  
  101. void Tree::Clear()
  102. // Clear the tree.
  103. {
  104.   DeleteTree(root);
  105.   root = 0;
  106. }
  107.  
  108. int Tree::Find(char *key)
  109. // Search the tree for matching entry 
  110. {
  111.   Tnode *parent;
  112.   int side;
  113.  
  114.   // Search the tree
  115.   Tnode *node = SearchForParent(root, key, parent, side);
  116.  
  117.   return node != 0; // Return true if the matching node is found
  118. }
  119.  
  120. int Tree::Copy(const Tree &t)
  121. // Copy tree t into the tree object that invoked the call. 
  122. {
  123.   Clear();
  124.   Tnode *r = DupTree(t.root);
  125.  
  126.   if(r) {
  127.     root = r; // Tree was copied from the bottom up
  128.     return 1;
  129.   }
  130.   return 0; // Tree was not copied
  131. }
  132.  
  133. Tnode *Tree::Insert(Tnode *&root, char *key, int &exists)
  134. // Insert a new node into the tree. Returns the matching node,
  135. // new or old and may modify the root pointer.
  136. {
  137.   Tnode *parent;
  138.   int side;
  139.  
  140.   // Look for a place to insert the node
  141.   Tnode *node = SearchForParent(root, key, parent, side);
  142.  
  143.   if(node == 0) { // Node does not exist in the tree
  144.     node = new Tnode(key);
  145.     if(parent) {
  146.       if(side) parent->right = node; else parent->left = node;
  147.     }
  148.     else // No parent, so this is the new root
  149.       root = node;
  150.     
  151.     exists = 0;
  152.   }
  153.   else
  154.     exists = 1;
  155.  
  156.   return node;
  157. }
  158.  
  159. Tnode *Tree::SearchForParent(Tnode *node, char *key, Tnode *&parent, int &side)
  160. // Returns the parent of the matching node, as well as the node itself. 
  161. // Each node to the left is smaller then the given node, and each node
  162. // to right is larger.
  163. {
  164.   parent = 0;
  165.   while(node) {
  166.     if(strcmp(key, node->data) == 0) break;
  167.     parent = node;
  168.     if(strcmp(key, node->data) < 0) { // Node is smaller
  169.       side = 0;
  170.       node = node->left;
  171.     }
  172.     else { // Node is larger
  173.       side = 1;
  174.       node = node->right;
  175.     }
  176.   }
  177.   return node;
  178. }
  179.  
  180. Tnode *Tree::DetachNode(Tnode *&root, Tnode *node, Tnode *parent, int side)
  181. // Detach the node with parent from the tree. The node is the left
  182. // child if side equals zero or right child if side equals one.
  183. // Returns a pointer to the node.
  184. {
  185.   Tnode *psucc; // Parent of successor
  186.   Tnode *replacement;
  187.  
  188.   if(node) {
  189.     if(node->left == 0 || node->right == 0) {
  190.       // At lease one child is null, so use the other as the replacement
  191.       replacement = (node->left) ? node->left : node->right;
  192.     }
  193.     else { // Neither child is null
  194.       psucc = GetParentOfSuccessor(node); // Guaranteed not to be null
  195.       if(psucc == node) { // Immediate successor
  196.     replacement = psucc->right;
  197.       }
  198.       else {
  199.     // Detach replacement from its current loaction and
  200.         // relocate it to where node used to be
  201.     replacement = psucc->left;
  202.     psucc->left = psucc->left->right;
  203.         replacement->right = node->right;
  204.       }
  205.  
  206.       // Finish reloacting replacement to where node used to be
  207.       replacement->left = node->left;
  208.     }
  209.  
  210.     if(parent) { // Fix parent of node to point to replacement
  211.       if(side)
  212.         parent->right = replacement; else parent->left = replacement;
  213.     }
  214.     else root = replacement; // No parent, so node was the root
  215.   }
  216.   return node;
  217. }
  218.  
  219. Tnode *Tree::GetParentOfSuccessor(Tnode *node)
  220. // Used by the Tree::DetachNode() function to find the parent of
  221. // the successor node. Returns zero if no successor is found.
  222. {
  223.   Tnode *parent = 0;
  224.  
  225.   // Go right once, then all the way to the left
  226.   Tnode *q = node->right;
  227.   if(q) {
  228.     parent = node;
  229.     while(q->left) {
  230.       parent = q;
  231.       q = q->left;
  232.     }
  233.   }
  234.   return parent;
  235. }
  236.  
  237. Tnode *Tree::Detach(Tnode *&root, char *key)
  238. // Detaches the node matching key from the tree.
  239. {
  240.   int side;
  241.   Tnode *parent, *node;
  242.   node = SearchForParent(root, key, parent, side);
  243.   return DetachNode(root, node, parent, side);
  244. }
  245.  
  246. int Tree::Delete(Tnode *&root, char *key)
  247. // Deletes the node from the tree. 
  248. // Returns zero if the node does not exist.
  249. {
  250.   Tnode *node = Detach(root, key);
  251.   delete node;
  252.   return node != 0;
  253. }
  254.  
  255. void Tree::DeleteTree(Tnode *t)
  256. // Recursive function used to clear the tree from the bottom up.
  257. {
  258.   if(t == 0) return;
  259.   if(t->left == 0) return; else DeleteTree(t->left);
  260.   if(t->right == 0) return; else DeleteTree(t->right);
  261.   delete t;
  262. }
  263.  
  264. void Tree::PrintInOrder(Tnode *tree, VisitFunc Visit)
  265. // Visit each node of tree Tree in in-order, (first the Left
  266. // subtree, then the parent, then the Right subtree), with 
  267. // tail recursion removed
  268. {
  269.   while(tree) {
  270.     PrintInOrder(tree->left, Visit);
  271.     Visit(tree);
  272.     tree = tree->right;
  273.   }
  274. }
  275.  
  276. Tnode *Tree::DupTree(Tnode *t)
  277. // Recursive function that to duplicates a tree using
  278. // postorder traversal.
  279. {
  280.   if(t == 0) return 0;
  281.   Tnode *l = DupTree(t->left);
  282.   Tnode *r = DupTree(t->right);
  283.   return new Tnode(t->data, l, r);
  284. }
  285.  
  286. int Tree::Height(Tnode *t)
  287. // The height of a tree is the maximum of the height of
  288. // its two subtrees. Returns the hight of the tree.
  289. {
  290.   int h = 0;
  291.   if(t != 0) {
  292.     int lh = Height(t->left);
  293.     int rh = Height(t->right);
  294.     h = ((lh > rh) ? lh : rh) +1;
  295.   }
  296.   return h;
  297. }
  298.  
  299. // Test program code starts here
  300. // *********************************************************** //
  301. char *InputData()
  302. // Input a line of text from the console
  303. {
  304.   char buf[255];
  305.   cout << "Input Data: ";
  306.   cin.getline(buf, sizeof(buf));
  307.   unsigned len = 0;
  308.   for(unsigned i = 0; (buf[i] != ' ') && (buf[i] != '\0'); i++) len++;
  309.   char *s = new char[len];
  310.   s[len] = '\0';
  311.   memmove(s, buf, len);
  312.   return s;
  313. }
  314.  
  315. void PrintNode(Tnode *node)
  316. // Visit function used to print the node data to the console
  317. {
  318.   cout << node->data << endl;
  319. }
  320.  
  321. void SkipToEol(istream &s)
  322. // Used to clear istream
  323. {
  324.   char c;
  325.   s.clear();
  326.   while(s.get(c) && c != '\n') { ; }
  327. }
  328.  
  329. int Quit()
  330. // Terminate the program
  331. {
  332.   cout << "Exiting..." << endl;
  333.   return 0;
  334. }
  335.  
  336. void pause()
  337. // Pause the program 
  338. {
  339.   cout << endl;
  340.   cout << "Press enter to continue..." << endl;
  341.   cin.get();
  342. }
  343.  
  344. void Menu(void)
  345. // List the program options
  346. {
  347.   cout << "(?)   Help (prints this menu)" << endl;
  348.   cout << "(A)   Add an item to the tree" << endl;
  349.   cout << "(B)   Build a tree of strings" << endl;
  350.   cout << "(C)   Clear the tree" << endl;
  351.   cout << "(D)   Delete an item from the tree" << endl;
  352.   cout << "(F)   Find an item in the tree" << endl;
  353.   cout << "(H)   Display the tree height" << endl;
  354.   cout << "(L)   List tree items in order" << endl; 
  355.   cout << "(Q)   Quit this program" << endl; 
  356. }
  357.  
  358. // Create an array of words to load in the tree
  359. const int Items = 5; // Adjust this number if any more items are added
  360. char *TreeData[Items] = { "EASY", "COOK", "DELTA", "ABLE", "BAKER", };
  361.  
  362. int main()
  363. // Test program's main thread of execution
  364. {
  365.   Menu(); // Display the options menu
  366.   
  367.   char key;
  368.   char *key_buf;
  369.   Tree tree;
  370.   int i, rv = 1;
  371.  
  372.   while(rv) {
  373.     if (!cin) { // Input is in fail state
  374.        SkipToEol(cin); // Go to end of line
  375.        if (!cin) {  // Can't fix
  376.           cout << "Input stream is broken" << endl;
  377.           return 0;
  378.        }
  379.     }
  380.     cout << '>';
  381.     cin >> key;
  382.     if (!cin) continue; // Fix at top of loop
  383.     switch(key) {
  384.       case 'a' : case 'A' :
  385.     SkipToEol(cin);
  386.     key_buf = InputData();
  387.     tree.Add(key_buf);
  388.     break;
  389.  
  390.       case 'b' : case 'B' :
  391.     SkipToEol(cin);
  392.       // Add the entries to the tree
  393.     for(i = 0; i < Items; i++) {
  394.       // Exit loop if Items is greater then the number of array elements  
  395.       if(TreeData[i] == 0) break; // 0 means the array is empty
  396.       tree.Add(TreeData[i]);
  397.     }
  398.     break;
  399.  
  400.       case 'c' : case 'C' :
  401.     SkipToEol(cin);
  402.     tree.Clear();
  403.     break;
  404.  
  405.       case 'd' : case 'D' :
  406.     SkipToEol(cin);
  407.     key_buf = InputData();
  408.     if(tree.Remove(key_buf)) {
  409.       cout << "Removed " << key_buf << endl;
  410.     }
  411.     else {
  412.       cout << key_buf << " does not exists in the tree" << endl;
  413.     }
  414.     break;
  415.  
  416.       case 'f' : case 'F' :
  417.     SkipToEol(cin);
  418.     key_buf = InputData();
  419.     if(tree.Find(key_buf)) {
  420.       cout << "Found entry " << key_buf << endl;
  421.     }
  422.     else {
  423.       cout << key_buf << " does not exists in the tree" << endl;
  424.     }
  425.     break;    
  426.  
  427.       case 'l' : case 'L' :
  428.     SkipToEol(cin);
  429.     tree.PrintTree(PrintNode);
  430.     break;     
  431.  
  432.       case 'h' : case 'H' :
  433.     SkipToEol(cin);
  434.     cout << "Height = " << tree.GetHeight() << endl;
  435.     break;
  436.  
  437.       case 'q' : case 'Q' :
  438.     rv = Quit();
  439.     break;
  440.  
  441.       case '?' : 
  442.     SkipToEol(cin);
  443.     Menu();
  444.     break;
  445.  
  446.       default:
  447.         cout << "Unrecognized command" << endl;
  448.     }
  449.   }
  450.   return 0;
  451. }
  452. // ----------------------------------------------------------- // 
  453. // ------------------------------- //
  454. // --------- End of File --------- //
  455. // ------------------------------- //
  456.