Chương trình chuyển đổi danh sách liên kết thành cây tìm kiếm nhị phân trong C ++

Giả sử chúng ta có một danh sách liên kết đơn trong đó các phần tử được sắp xếp theo thứ tự không giảm, chúng ta phải chuyển nó thành cây tìm kiếm nhị phân cân bằng chiều cao. Vì vậy, nếu danh sách có dạng [-10, -3, 0, 5, 9], Cây có thể sẽ giống như -

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Nếu danh sách trống, thì
  • trả về null
• Xác định một phương thức đệ quy được gọi là sortedListToBST (), phương thức này sẽ sử dụng nút bắt đầu danh sách
• x:=địa chỉ của nút trước của nút giữa từ danh sách a
• mid:=nút giữa chính xác
• tạo một nút mới có giá trị bằng cách lấy từ giá trị giữa
• nextStart:=tiếp theo của nút giữa
• đặt giữa tiếp theo là null
• bên phải của nút:=sortedListToBST (nextStart)
• nếu x không rỗng, thì
  • tiếp theo của x =null và bên trái của nút:=sortedListToBST (a)
• nút trả lại

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class ListNode{
   public:
   int val;
   ListNode *next;
   ListNode(int data){
      val = data;
      next = NULL;
   }
};
ListNode *make_list(vector<int> v){
   ListNode *head = new ListNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      ListNode *ptr = head;
      while(ptr->next != NULL){
         ptr = ptr->next;
      }
      ptr->next = new ListNode(v[i]);
   }
   return head;
}
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = right = NULL;
   }
};
void inord(TreeNode *root){
   if(root != NULL){
      inord(root->left);
      cout << root->val << " ";
      inord(root->right);
   }
}
class Solution {
   public:
   pair <ListNode*, ListNode*> getMid(ListNode* a){
      ListNode* prev = NULL;
      ListNode* fast = a;
      ListNode* slow = a;
      while(fast && fast->next){
         fast = fast->next->next;
         prev = slow;
         slow = slow->next;
      }
      return {prev, slow};
   }
   TreeNode* sortedListToBST(ListNode* a) {
      if(!a)return NULL;
         pair<ListNode*, ListNode*> x = getMid(a);
         ListNode* mid = x.second;
         TreeNode* Node = new TreeNode(mid->val);
         ListNode* nextStart = mid->next;
         mid->next = NULL;
         Node->right = sortedListToBST(nextStart);
         if(x.first){
            x.first->next = NULL;
            Node->left = sortedListToBST(a);
      }
      return Node;
   }
};
main(){
   vector<int> v = {-10,-3,0,5,9};
   ListNode *head = make_list(v);
   Solution ob;
   inord(ob.sortedListToBST(head));
}

Đầu vào

[-10,-3,0,5,9]

Đầu ra

-10 -3 0 5 9