#include <iostream>
using namespace std;

class BinTree{
private:
  class BinNode{
  public:
    int idata;
    BinNode *left,*right;
    BinNode(int a = 0) {idata = a; left = right = 0; }
    void printNode(){ cout << idata << " "; }
  };
  BinNode *root;
  void traverse(BinNode *rp, int level);
  void addNode(BinNode *rp, BinNode *node);
  BinNode *delNode(BinNode *rp,int x);
public:
  BinTree(){ root = 0;}
  void printTree(){ traverse(root, 0); }
  void insert(int x){
    BinNode *np = new BinNode(x);
    if(!root) root = np;
    else addNode(root, np);
  }
  void remove(int x){ root = delNode(root,x); }
};

void BinTree::addNode(BinNode *rp,BinNode *node){
  if(rp->idata > node->idata){
    if(rp->left != 0)
      addNode(rp->left,node);
    else
      rp->left=node;
  } else {
    if(rp->right != 0)
      addNode(rp->right,node);
    else
      rp->right=node;
  }
}

BinTree::BinNode *BinTree::delNode(BinNode *rp, int x){
  int cmp;
  if (rp == 0)
    return 0;
  if ((cmp = x - rp->idata) != 0) {
    if (cmp < 0) {
      rp->left = BinTree::delNode(rp->left, x);
      return rp;
    } else {
      rp->right = BinTree::delNode(rp->right, x);
      return rp;
    }
  } else { /* deleting */
    BinNode *p, *q;
    if (rp->left == 0) {
      p = rp->right;
      delete rp;
      return p;
    } else if (rp->right == 0) {
      p = rp->left;
      delete rp;
      return p;
    } else {
      p = rp->left;
      for (q = rp->left; q->right != 0; q = q->right)
        ;
      q->right = rp->right;
      delete rp;
      return p;
    }
  }
}

void BinTree::traverse(BinNode *rp, int level){ 
#if 0
  if(rp==NULL)return; 
  if(rp->left!=NULL){
    traverse(rp->left);
  }
  rp->printNode();
  if(rp->right!=NULL){
    traverse(rp->right);
  }
#endif
  if (rp != 0) {
    traverse(rp->left, level + 2);
    for (int i = 0; i < level; i++) cout << " ";
    rp->printNode();    
    cout << endl;
    traverse(rp->right, level + 2);
  }
}

int main(){
  BinTree bt;
  int x;

  cout << "input positive integer.(if negative, transfered to next step.) --> ";
  while(cin >> x && x >0){
    bt.insert(x);
 }

 bt.printTree();
 cout << endl;

  while(cout << "positive integer to delete --> " && cin >> x && x > 0){
    bt.remove(x);
    bt.printTree();
    cout << endl;
 }
 return 0;
}
/* end */