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