fork download 
  1. #include <iostream>
  2. #include <cstdlib>
  3.  
  4. struct notesTree
  5. {
  6.     int nProdID;
  7.     notesTree* pLeftChild;
  8.     notesTree* pRightChild;
  9.  
  10.     notesTree(int prod_id)
  11.         : nProdID(prod_id)
  12.         , pLeftChild()
  13.         , pRightChild()
  14.     {};
  15.  
  16.     notesTree(const notesTree& obj)
  17.         : nProdID(obj.nProdID)
  18.         , pLeftChild()
  19.         , pRightChild()
  20.     {};
  21. };
  22.  
  23. void RemoveItem(notesTree** pp, int id)
  24. {
  25.     while (*pp)
  26.     {
  27.         if (id < (*pp)->nProdID)
  28.             pp = &(*pp)->pLeftChild;
  29.         else if ((*pp)->nProdID < id)
  30.             pp = &(*pp)->pRightChild;
  31.         else break;
  32.     }
  33.  
  34.     if (*pp)
  35.     {
  36.         // save the victim pointer
  37.         notesTree *victim = *pp;
  38.  
  39.         // move the left tree up a level
  40.         *pp = victim->pLeftChild;
  41.  
  42.         // hang the victim's right child on the
  43.         //  first null-right pointer in the left tree
  44.         while (*pp)
  45.             pp = &(*pp)->pRightChild;
  46.         *pp = victim->pRightChild;
  47.  
  48.         delete victim;
  49.     }
  50. }
  51.  
  52. void InserItem(notesTree **pp, int id)
  53. {
  54.     while (*pp)
  55.     {
  56.         if (id < (*pp)->nProdID)
  57.             pp = &(*pp)->pLeftChild;
  58.         else if ((*pp)->nProdID < id)
  59.             pp = &(*pp)->pRightChild;
  60.         else break;
  61.     }
  62.  
  63.     if (!*pp)
  64.         *pp = new notesTree(id);
  65. }
  66.  
  67. void InOrder(notesTree *p)
  68. {
  69.     if (!p)
  70.         return;
  71.     InOrder(p->pLeftChild);
  72.     std::cout << p->nProdID << ' ';
  73.     InOrder(p->pRightChild);
  74. }
  75.  
  76.  
  77. int main()
  78. {
  79.     notesTree *root = NULL;
  80.  
  81.     InserItem(&root, 5);
  82.     InserItem(&root, 2);
  83.     InserItem(&root, 1);
  84.     InserItem(&root, 3);
  85.     InserItem(&root, 4);
  86.     InserItem(&root, 7);
  87.     InserItem(&root, 6);
  88.     InserItem(&root, 8);
  89.     InserItem(&root, 9);
  90.  
  91.     InOrder(root);
  92.     std::cout << std::endl;
  93.  
  94.     RemoveItem(&root, 5);
  95.     InOrder(root);
  96.     std::cout << std::endl;
  97.  
  98.     RemoveItem(&root, 6);
  99.     InOrder(root);
  100.     std::cout << std::endl;
  101.  
  102.     RemoveItem(&root, 1);
  103.     InOrder(root);
  104.     std::cout << std::endl;
  105.  
  106.     RemoveItem(&root, 8);
  107.     InOrder(root);
  108.     std::cout << std::endl;
  109.  
  110.     return EXIT_SUCCESS;
  111. }
Success #stdin #stdout 0s 3428KB
comments (?)
stdin 
Standard input is empty
stdout 
1 2 3 4 5 6 7 8 9 
1 2 3 4 6 7 8 9 
1 2 3 4 7 8 9 
2 3 4 7 8 9 
2 3 4 7 9
https://ideone.com/pYShO8
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!