fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <fstream>
  4. #include <chrono>
  5. #include <vector>
  6. #include <iomanip>
  7.  
  8. using namespace std;
  9.  
  10. struct Node{
  11.     int val;
  12.     Node* left = nullptr;
  13.     Node* right = nullptr;
  14. };
  15.  
  16. Node* addNode(Node* root, int x){
  17.     if(root == nullptr) return new Node{x, nullptr, nullptr};
  18.  
  19.     if(x < root->val)
  20.         root->left = addNode(root->left, x);
  21.     else if(x > root->val)
  22.         root->right = addNode(root->right, x);
  23.     return root;
  24. }
  25.  
  26. bool existInBST(Node* root, int x){
  27.     if(root == nullptr) return false;
  28.     if(root->val == x) return true;
  29.     if(x < root->val) return existInBST(root->left, x);
  30.     return existInBST(root->right, x);
  31. }
  32.  
  33. void inorder(Node* root){
  34.     if(root == nullptr) return;
  35.  
  36.     if(root->left != nullptr) inorder(root->left);
  37.     cout << root->val << " ";
  38.     if(root->right != nullptr) inorder(root->right);
  39. }
  40.  
  41. void preorder(Node* root){
  42.     if(root == nullptr) return;
  43.  
  44.     cout << root->val << " ";
  45.     if(root->left != nullptr) preorder(root->left);
  46.     if(root->right != nullptr) preorder(root->right);
  47. }
  48.  
  49. void postorder(Node* root){
  50.     if(root == nullptr) return;
  51.  
  52.     if(root->left != nullptr) postorder(root->left);
  53.     if(root->right != nullptr) postorder(root->right);
  54.     cout << root->val << " ";
  55. }
  56.  
  57. Node* get(Node* cur){
  58.     cur = cur->right;
  59.     while(cur != nullptr && cur->left != nullptr)
  60.         cur = cur->left;
  61.     return cur;
  62. }
  63.  
  64. Node* deleteNode(Node* root, int data){
  65.     if(root == nullptr) return root;
  66.  
  67.     if(data < root->val){
  68.         root->left = deleteNode(root->left, data);
  69.     }
  70.     else if(data > root->val){
  71.         root->right = deleteNode(root->right, data);
  72.     }
  73.     else{
  74.         if(root->left == nullptr){
  75.             Node* tmp = root->right;
  76.             delete root;
  77.             return tmp;
  78.         }
  79.         if(root->right == nullptr){
  80.             Node* tmp = root->left;
  81.             delete root;
  82.             return tmp;
  83.         }
  84.  
  85.         Node* succ = get(root);
  86.         root->val = succ->val;
  87.         root->right = deleteNode(root->right, succ->val);
  88.     }
  89.     return root;
  90. }
  91.  
  92. int main(){
  93.     int q;
  94.     Node* root = nullptr;
  95.     while(cin >> q){
  96.         if(q == 1){
  97.             int x; cin >> x;
  98.             root = addNode(root, x);
  99.         }
  100.         else if(q == 2){
  101.             string s; cin >> s;
  102.             if(s == "NLR") preorder(root);
  103.             else if(s == "LNR") inorder(root);
  104.             else postorder(root);
  105.             cout << '\n';
  106.         }
  107.         else if(q == 3){
  108.             int x; cin >> x;
  109.             bool found = existInBST(root, x);
  110.             if(found) cout << "YES";
  111.             else cout << "NO";
  112.             cout << '\n';
  113.         }
  114.         else{
  115.             int x; cin >> x;
  116.             root = deleteNode(root, x);
  117.         }
  118.     }
  119.     return 0;
  120. }
Success #stdin #stdout 0s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DNvDQq
language:
C++14 (clang 8.0)
created:
1 day 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!