fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. // Định nghĩa cấu trúc nút cho cây BST và DLL
  6. class Node {
  7. public:
  8.     int val;       // Giá trị của nút
  9.     Node* left;    // Con trỏ trái (trong BST)
  10.     Node* right;   // Con trỏ phải (trong BST)
  11.  
  12.     Node() : val(0), left(nullptr), right(nullptr) {}
  13.     Node(int _val) : val(_val), left(nullptr), right(nullptr) {}
  14. };
  15.  
  16. class Solution {
  17. private:
  18.     Node* prevDLL = nullptr; // Nút trước đó trong quá trình chuyển đổi BST sang DLL
  19.     Node* headDLL = nullptr; // Đầu của DLL được tạo từ BST
  20.  
  21.     // Hàm đệ quy để duyệt cây BST theo thứ tự (in-order) và xây dựng DLL
  22.     void dfs(Node* root) {
  23.         if (root == nullptr) {
  24.             return; // Nếu nút hiện tại là null, kết thúc đệ quy
  25.         }
  26.         dfs(root->left); // Duyệt cây con bên trái
  27.  
  28.         // Xử lý nút hiện tại
  29.         if (prevDLL != nullptr) {
  30.             prevDLL->right = root; // Liên kết nút trước với nút hiện tại (trong DLL)
  31.             root->left = prevDLL;  // Liên kết nút hiện tại với nút trước (trong DLL)
  32.         } else {
  33.             headDLL = root; // Nếu prevDLL là null, nút hiện tại là đầu của DLL
  34.         }
  35.         prevDLL = root; // Cập nhật nút trước là nút hiện tại
  36.  
  37.         dfs(root->right); // Duyệt cây con bên phải
  38.     }
  39.  
  40. public:
  41.     // Hàm chính để chuyển đổi BST thành Doubly Linked List (DLL)
  42.     Node* BSTtoDLL(Node* rootBST) {
  43.         if (rootBST == nullptr) {
  44.             return nullptr; // Nếu BST rỗng, trả về null
  45.         }
  46.         prevDLL = nullptr;
  47.         headDLL = nullptr;
  48.         dfs(rootBST); // Gọi hàm dfs để xây dựng DLL
  49.         return headDLL; // Trả về đầu của DLL
  50.     }
  51.  
  52.     // Hàm để chèn nút vào BST (hàm hỗ trợ)
  53.     Node* insert(Node* root, int val) {
  54.         if (root == nullptr) {
  55.             return new Node(val); // Nếu cây rỗng, tạo nút mới
  56.         }
  57.         if (val < root->val) {
  58.             root->left = insert(root->left, val); // Chèn vào cây con bên trái
  59.         } else {
  60.             root->right = insert(root->right, val); // Chèn vào cây con bên phải
  61.         }
  62.         return root; // Trả về gốc của cây
  63.     }
  64.  
  65.     // Helper function to print the doubly linked list
  66.     void printDLL(Node* head) {
  67.         Node* current = head;
  68.         while (current != nullptr) {
  69.             cout << current->val << " "; // In giá trị của nút hiện tại
  70.             current = current->right;    // Di chuyển đến nút tiếp theo
  71.         }
  72.         cout << endl;
  73.     }
  74.  
  75.     // Function to print the BST (in-order for verification) - GIỮ NGUYÊN
  76.     void printBST(Node* node)
  77.     {
  78.         if (node == nullptr)
  79.             return;
  80.         cout << node->val << " ";
  81.         printBST(node->left);
  82.         printBST(node->right);
  83.     }
  84.  
  85.     //============================//
  86.     // Chuyển đổi DLL sang BST
  87.  
  88. private:
  89.     Node* sortedDLLToBSTHelper(Node*& headRef, int n) {
  90.         if (n <= 0) return nullptr; // Trường hợp cơ sở: không còn nút để xử lý
  91.  
  92.         Node* left = sortedDLLToBSTHelper(headRef, n / 2); // Xây dựng cây con bên trái
  93.  
  94.         Node* root = headRef; // Nút hiện tại trong DLL sẽ là gốc của cây con hiện tại
  95.         if (headRef) {
  96.             headRef = headRef->right; // Di chuyển con trỏ headRef đến nút tiếp theo trong DLL
  97.         }
  98.  
  99.         root->left = left; // Gán cây con bên trái cho nút gốc
  100.         root->right = sortedDLLToBSTHelper(headRef, n - n / 2 - 1); // Xây dựng cây con bên phải
  101.  
  102.         return root; // Trả về gốc của cây con hiện tại
  103.     }
  104.  
  105.     // Hàm để đếm số lượng nút trong DLL
  106.     int countNodesDLL(Node* head) {
  107.         int count = 0;
  108.         Node* current = head;
  109.         while (current != nullptr) {
  110.             count++;             // Tăng bộ đếm cho mỗi nút
  111.             current = current->right; // Di chuyển đến nút tiếp theo
  112.         }
  113.         return count; // Trả về tổng số nút
  114.     }
  115.  
  116. public:
  117.     // Hàm chính để chuyển đổi Doubly Linked List (DLL) thành BST cân bằng
  118.     Node* DLLtoBST(Node* head) {
  119.         if (!head) return nullptr; // Nếu DLL rỗng, trả về null
  120.         int n = countNodesDLL(head); // Đếm số lượng nút trong DLL
  121.         Node* currentHead = head;   // Tạo một bản sao của head để truyền vào hàm đệ quy
  122.         return sortedDLLToBSTHelper(currentHead, n); // Gọi hàm đệ quy để xây dựng BST
  123.     }
  124. };
  125.  
  126. int main() {
  127.     Solution sol;
  128.     Node* rootBST = nullptr;
  129.     rootBST = sol.insert(rootBST, 4);
  130.     rootBST = sol.insert(rootBST, 2);
  131.     rootBST = sol.insert(rootBST, 5);
  132.     rootBST = sol.insert(rootBST, 1);
  133.     rootBST = sol.insert(rootBST, 3);
  134.     rootBST = sol.insert(rootBST, 6);
  135.     rootBST = sol.insert(rootBST, 7);
  136.  
  137.     cout << "BST (Trước): ";
  138.     sol.printBST(rootBST);
  139.     cout << endl;
  140.  
  141.     Node* headDLL = sol.BSTtoDLL(rootBST);
  142.     cout << "Doubly Linked List: ";
  143.     sol.printDLL(headDLL);
  144.  
  145.     Node* rootFromDLL = sol.DLLtoBST(headDLL);
  146.     cout << "BST (Sau): ";
  147.     sol.printBST(rootFromDLL);
  148.     cout << endl;
  149.  
  150.     return 0;
  151. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
BST (Trước): 4 2 1 3 5 6 7 
Doubly Linked List: 1 2 3 4 5 6 7 
BST (Sau): 4 2 1 3 6 5 7
https://ideone.com/DB61Nn
language:
C++14 (gcc 8.3)
created:
9 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!