fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. // Cấu trúc nút cây
  5. struct Node {
  6.     int data;
  7.     Node* left;
  8.     Node* right;
  9. };
  10.  
  11. // Tạo nút mới
  12. Node* createNode(int value) {
  13.     Node* newNode = new Node();
  14.     newNode->data = value;
  15.     newNode->left = newNode->right = nullptr;
  16.     return newNode;
  17. }
  18.  
  19. // Thêm phần tử vào BST
  20. Node* insert(Node* root, int value) {
  21.     if (root == nullptr)
  22.         return createNode(value);
  23.     if (value < root->data)
  24.         root->left = insert(root->left, value);
  25.     else if (value > root->data)
  26.         root->right = insert(root->right, value);
  27.     // Nếu value == root->data thì bỏ qua (không thêm trùng)
  28.     return root;
  29. }
  30.  
  31. // Duyệt cây theo thứ tự giữa (inorder)
  32. void inorder(Node* root) {
  33.     if (root != nullptr) {
  34.         inorder(root->left);
  35.         cout << root->data << " ";
  36.         inorder(root->right);
  37.     }
  38. }
  39.  
  40. // Tìm phần tử
  41. bool search(Node* root, int key) {
  42.     if (root == nullptr)
  43.         return false;
  44.     if (key == root->data)
  45.         return true;
  46.     else if (key < root->data)
  47.         return search(root->left, key);
  48.     else
  49.         return search(root->right, key);
  50. }
  51.  
  52. // Tìm node nhỏ nhất trong cây con
  53. Node* findMin(Node* root) {
  54.     while (root->left != nullptr)
  55.         root = root->left;
  56.     return root;
  57. }
  58.  
  59. // Xoá phần tử trong BST
  60. Node* deleteNode(Node* root, int key) {
  61.     if (root == nullptr) return root;
  62.  
  63.     if (key < root->data)
  64.         root->left = deleteNode(root->left, key);
  65.     else if (key > root->data)
  66.         root->right = deleteNode(root->right, key);
  67.     else {
  68.         // Node cần xoá có 1 hoặc 0 con
  69.         if (root->left == nullptr) {
  70.             Node* temp = root->right;
  71.             delete root;
  72.             return temp;
  73.         }
  74.         else if (root->right == nullptr) {
  75.             Node* temp = root->left;
  76.             delete root;
  77.             return temp;
  78.         }
  79.  
  80.         // Node có 2 con: tìm node nhỏ nhất bên phải
  81.         Node* temp = findMin(root->right);
  82.         root->data = temp->data; // Gán giá trị nhỏ nhất
  83.         root->right = deleteNode(root->right, temp->data); // Xoá node nhỏ nhất
  84.     }
  85.     return root;
  86. }
  87.  
  88. // ================================
  89. int main() {
  90.     Node* root = nullptr;
  91.  
  92.     // Thêm phần tử
  93.     root = insert(root, 50);
  94.     insert(root, 30);
  95.     insert(root, 70);
  96.     insert(root, 20);
  97.     insert(root, 40);
  98.     insert(root, 60);
  99.     insert(root, 80);
  100.  
  101.     cout << "Duyet Inorder: ";
  102.     inorder(root);
  103.     cout << endl;
  104.  
  105.     int key = 40;
  106.     cout << "Tim " << key << ": " << (search(root, key) ? "Co" : "Khong") << endl;
  107.  
  108.     root = deleteNode(root, 30);
  109.     cout << "Sau khi xoa 30: ";
  110.     inorder(root);
  111.     cout << endl;
  112.  
  113.     return 0;
  114. }
  115.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Duyet Inorder: 20 30 40 50 60 70 80 
Tim 40: Co
Sau khi xoa 30: 20 40 50 60 70 80
https://ideone.com/WllFMG
language:
C++ (gcc 8.3)
created:
3 days 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!