fork(2) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. class BinTree{
  5. private:
  6.   class BinNode{
  7.   public:
  8.     int idata;
  9.     BinNode *left,*right;
  10.     BinNode(int a = 0) {idata = a; left = right = 0; }
  11.     void printNode(){ cout << idata << " "; }
  12.   };
  13.   BinNode *root;
  14.   void traverse(BinNode *rp, int level);
  15.   void addNode(BinNode *rp, BinNode *node);
  16.   BinNode *delNode(BinNode *rp,int x);
  17. public:
  18.   BinTree(){ root = 0;}
  19.   void printTree(){ traverse(root, 0); }
  20.   void insert(int x){
  21.     BinNode *np = new BinNode(x);
  22.     if(!root) root = np;
  23.     else addNode(root, np);
  24.   }
  25.   void remove(int x){ root = delNode(root,x); }
  26. };
  27.  
  28. void BinTree::addNode(BinNode *rp,BinNode *node){
  29.   if(rp->idata > node->idata){
  30.     if(rp->left != 0)
  31.       addNode(rp->left,node);
  32.     else
  33.       rp->left=node;
  34.   } else {
  35.     if(rp->right != 0)
  36.       addNode(rp->right,node);
  37.     else
  38.       rp->right=node;
  39.   }
  40. }
  41.  
  42. BinTree::BinNode *BinTree::delNode(BinNode *rp, int x){
  43.   int cmp;
  44.   if (rp == 0)
  45.     return 0;
  46.   if ((cmp = x - rp->idata) != 0) {
  47.     if (cmp < 0) {
  48.       rp->left = BinTree::delNode(rp->left, x);
  49.       return rp;
  50.     } else {
  51.       rp->right = BinTree::delNode(rp->right, x);
  52.       return rp;
  53.     }
  54.   } else { /* deleting */
  55.     BinNode *p, *q;
  56.     if (rp->left == 0) {
  57.       p = rp->right;
  58.       delete rp;
  59.       return p;
  60.     } else if (rp->right == 0) {
  61.       p = rp->left;
  62.       delete rp;
  63.       return p;
  64.     } else {
  65.       p = rp->left;
  66.       for (q = rp->left; q->right != 0; q = q->right)
  67.         ;
  68.       q->right = rp->right;
  69.       delete rp;
  70.       return p;
  71.     }
  72.   }
  73. }
  74.  
  75. void BinTree::traverse(BinNode *rp, int level){ 
  76. #if 0
  77.   if(rp==NULL)return; 
  78.   if(rp->left!=NULL){
  79.     traverse(rp->left);
  80.   }
  81.   rp->printNode();
  82.   if(rp->right!=NULL){
  83.     traverse(rp->right);
  84.   }
  85. #endif
  86.   if (rp != 0) {
  87.     traverse(rp->left, level + 2);
  88.     for (int i = 0; i < level; i++) cout << " ";
  89.     rp->printNode();    
  90.     cout << endl;
  91.     traverse(rp->right, level + 2);
  92.   }
  93. }
  94.  
  95. int main(){
  96.   BinTree bt;
  97.   int x;
  98.  
  99.   cout << "input positive integer.(if negative, transfered to next step.) --> ";
  100.   while(cin >> x && x >0){
  101.     bt.insert(x);
  102.  }
  103.  
  104.  bt.printTree();
  105.  cout << endl;
  106.  
  107.   while(cout << "positive integer to delete --> " && cin >> x && x > 0){
  108.     bt.remove(x);
  109.     bt.printTree();
  110.     cout << endl;
  111.  }
  112.  return 0;
  113. }
  114. /* end */
  115.  
Success #stdin #stdout 0s 2904KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
input positive integer.(if negative, transfered to next step.) --> 
positive integer to delete -->
https://ideone.com/GLN6cG
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!