#include <iostream.h>

class TREE
{
public:
  TREE() { root = NULL; }

  void Insert(char c) {
    NODE* p;
    p = new NODE(c);
    p->lch = NULL;
    p->rch = NULL;
    if (root == NULL) {
      root = p;
      return;
    }else
      Insert1(root,p);
  }

  void Show() {
    if (root == NULL) return;
    Show1(root);
    cout << '\n'<< flush;
  }

  int Size() {
    return Size1(root);
  }

  char* Compact(char*& croot) {
    char* segment;
    int ind = 0;

    segment = (char*) new char[Size()];
    croot = Compact1(ind,segment,root);
    return segment;
  }

  void CShow(char* segment,char* cnode) {
    if (cnode == NULL) return;
    CShow(segment,GetLch(cnode));
    cout << ' ' << GetValue(cnode);
    CShow(segment,GetRch(cnode));
  }

  char* Relativize(char* segment,char* croot) {
    char* p;
 
    if (croot == NULL) return NULL;
    p = GetLch(croot);
    if (p != NULL) {
      Relativize1(segment,p);
      PutLch(croot,(char*)(p-segment+1)); // shift by 1 to 
                                          // distinguish from NULL
    }
    p = GetRch(croot);
    if (p != NULL) {
      Relativize1(segment,p);
      PutRch(croot,(char*)(p-segment+1)); // shift by 1 to 
                                          // distinguish from NULL
    }
    return ((char*)(croot-segment+1));    // shift by 1 to 
                                          // distinguish from NULL
  }

  char* Absolutize(char* segment,char* croot) {
    if (croot == NULL) return NULL;
    // undo the shift
    croot = ((char*)(segment+((unsigned long)croot)-1));
    Absolutize1(segment,croot);
    return croot;
  }

protected:
  NODE* root;

  void Insert1(NODE* n,NODE* p) {
    if (p->value < n->value)
      if (n->lch == NULL)
        n->lch = p;
      else
        Insert1(n->lch,p);
    else
      if (n->rch == NULL)
        n->rch = p;
      else
        Insert1(n->rch,p);
  }

  void Show1(NODE* p) {
    if (p == NULL) return;
    Show1(p->lch);
    cout << ' ' << p->value;
    Show1(p->rch);
  }

  int Size1(NODE* p) {
    if (p == NULL)
      return 0;
    return p->Size()+Size1(p->lch)+Size1(p->rch);
  }
  char GetValue(char* p) { // use instead of p->value
    return *p;
  }
  void PutValue(char* p,char c) { // use instead of p->value
    *p = c;
  }
  char* GetLch(char* p) {  // use instead of p->lch
    char *q, *q1, *q2;
    int i;

    q2 = (char*)&q;
    q1 = p+sizeof(char);
    for(i = 0;i<sizeof(char*);i++)
      *q2++ = *q1++;
    return q;
  }
  void PutLch(char* p,char* addr) {  // use instead of p->lch
    char *q, *q1, *q2;
    int i;

    q = addr;
    q2 = (char*)&q;
    q1 = p+sizeof(char);
    for(i = 0;i<sizeof(char*);i++)
      *q1++ = *q2++;
  }
  char* GetRch(char* p) {  // use instead of p->rch
    char *q, *q1, *q2;
    int i;

    q2 = (char*)&q;
    q1 = p+sizeof(char)+sizeof(char*);
    for(i = 0;i<sizeof(char*);i++)
      *q2++ = *q1++;
    return q;
  }
  void PutRch(char* p,char* addr) {  // use instead of p->rch
    char *q, *q1, *q2;
    int i;
  
    q = addr;
    q2 = (char*)&q;
    q1 = p+sizeof(char)+sizeof(char*);
    for(i = 0;i<sizeof(char*);i++)
      *q1++ = *q2++;
  }



  char* Compact1(int& ind,char* segment,NODE* n) {
    char *lch, *rch, *ret;

    if (n == NULL) return NULL;
    lch = Compact1(ind,segment,n->lch);
    rch = Compact1(ind,segment,n->rch);
    //copy n to segment to location segment[ind]
    ret = &segment[ind];
    PutValue(&segment[ind],n->value);
    PutLch(&segment[ind],lch);
    PutRch(&segment[ind],rch);
    ind += n->Size();
    return ret;
  }



  void Relativize1(char* segment,char* cnode) {
    char* p;

    p = GetLch(cnode);
    if (p != NULL) {
      Relativize1(segment,p);
      PutLch(cnode,(char*)(p-segment+1));  // shift up by 1 to 
                                           // distinguish from NULL
    }
    p = GetRch(cnode);
    if (p != NULL) {
      Relativize1(segment,p);
      PutRch(cnode,(char*)(p-segment+1)); // shift up by 1 to 
                                          // distinguish from NULL
    }
  }



  void Absolutize1(char* segment,char* cnode) {
    char* p;

    if ((p = GetLch(cnode)) != NULL) {
      // undo the shift
      p = ((char*)(segment+((unsigned long)p)-1));
      PutLch(cnode,p);
      Absolutize1(segment,p);
    }

    if ((p = GetRch(cnode)) != NULL) {
      // undo the shift
      p = ((char*)(segment+((unsigned long)p)-1));
      PutRch(cnode,p);
      Absolutize1(segment,p);
    }
  }
};//end class TREE