home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c100 / 1.ddi / OOPWLD.ZIP / BINTREE / FULLBIN.HPP < prev    next >
Encoding:
C/C++ Source or Header  |  1990-06-11  |  2.8 KB  |  79 lines
  1. // FULLBIN.HPP: Full-featured binary tree.  Note use of recursive 
  2. // calls; this isn't particularly risky because balanced binary 
  3. // trees tend to be relatively shallow.
  4. #include "smap.hpp"
  5. #include <string.h>
  6. #include <stdio.h>
  7.  
  8. class tree {
  9.   char * data;
  10.   tree * left, * right;
  11.   void dup(char * dat) {  // use borland's dup() instead, for smallness
  12.     delete data;
  13.     data = new char[strlen(dat) + 1];
  14.     strcpy(data,dat);
  15.   }
  16.   // indicators of the balance of the tree:
  17.   enum treebalance { balanced = 0, heavy_left, heavy_right };
  18. public:
  19.   // When constructor is called with no arguments, makes an empty node:
  20.   tree(char * dat = "") : left(NULL), right(NULL), data(NULL) { dup(dat); }
  21.   ~tree() { delete data; }
  22.   void add(char * dat);
  23.   tree * find(char * dat);
  24.   void preorder_traverse() {
  25.     printf(" %s ", data);
  26.     if(left) left->preorder_traverse();
  27.     if(right) right->preorder_traverse();
  28.   }
  29.   void inorder_traverse() {
  30.     if(left) left->inorder_traverse();
  31.     printf(" %s ", data);
  32.     if(right) right->inorder_traverse();
  33.   }
  34.   void postorder_traverse() {
  35.     if(left) left->postorder_traverse();
  36.     if(right) right->postorder_traverse();
  37.     printf(" %s ", data);
  38.   }
  39.   int depth(int curr_depth = 0) {  // measure depth of tree
  40.     int dl, dr; dl = dr = curr_depth;
  41.     if(left) dl = left->depth(dl + 1);  // plumb the left depth
  42.     if(right) dr = right->depth(dr + 1); // plumb the right depth
  43.     return dl > dr ? dl : dr;
  44.   }
  45.   friend void rotate_left(tree ** tp);
  46.   friend void rotate_right(tree ** tp);
  47.   treebalance heavy() { // tells you how the tree is balanced
  48.     if(!left && !right) return balanced;
  49.     if(!left) return (right->depth() > 1) ? heavy_right : balanced;
  50.     if(!right) return (left->depth() > 1) ? heavy_left : balanced;
  51.     if(left->depth() - 1 > right->depth())
  52.       return heavy_left;
  53.     if(right->depth() - 1 > left->depth())
  54.       return heavy_right;
  55.     return balanced;
  56.   }
  57.   friend void balance(tree ** tp) {  // balance the tree
  58.     while((*tp)->heavy() == tree::heavy_right)
  59.       rotate_left(tp);
  60.     while((*tp)->heavy() == tree::heavy_left)
  61.       rotate_right(tp);
  62.     }
  63.   friend void rebalance(tree **tp) {
  64.     if((*tp)->left) rebalance(&((*tp)->left));
  65.     if((*tp)->right) rebalance(&((*tp)->right));
  66.     while((*tp)->heavy() == tree::heavy_right)
  67.       rotate_left(tp);
  68.     while((*tp)->heavy() == tree::heavy_left)
  69.       rotate_right(tp);
  70.     }
  71.   void place(screenmap & screen, int depth, int location, int bisection) {
  72.     screen(depth,location) = *data;  // only put one character in as a test
  73.     if(left) 
  74.       left->place(screen, depth+1, location - bisection/2, bisection/2);
  75.     if(right) 
  76.       right->place(screen, depth+1, location + bisection/2, bisection/2);
  77.   }
  78. };
  79.