Điền các con trỏ bên phải tiếp theo trong mỗi nút trong C ++

Giả sử chúng ta có một cây nhị phân hoàn chỉnh, trong đó mỗi nút có các trường sau:(dữ liệu, trái, phải, tiếp theo), bên trái sẽ trỏ đến cây con bên trái, bên phải sẽ trỏ đến cây con bên phải và con trỏ tiếp theo sẽ trỏ đến nút tiếp theo . Nếu không có nút nào ở phía bên tay phải, thì nút đó sẽ là nút rỗng. Vì vậy, ban đầu mỗi con trỏ tiếp theo được đặt thành null, chúng ta phải tạo các liên kết. Giả sử cây giống như cây đầu tiên, nó sẽ được chuyển đổi sang nút tiếp theo -

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

• đặt pre:=root, nextPre:=null và trước:=null
• while pre không rỗng
  • while pre không rỗng
    • if left of pre không rỗng
      • đặt tiếp theo của giá trị trước:=bên trái của trước, khi trước không bị rỗng, ngược lại thì nextPre:=bên trái của trước
      • before:=left of pre
    • nếu bên phải của phần trước không rỗng
      • đặt tiếp theo của trước:=bên phải của trước, khi trước không phải là null, ngược lại thì nextPre:=bên phải của trước
      • before:=right of pre
  • pre:=nextPre
  • đặt nextPre là null và trước là null
• trả về null

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>
#include <stack>
using namespace std;
class Node {
public:
   int val;
   Node* left;
   Node* right;
   Node* next;
   Node() {}
   Node(int _val, Node* _left, Node* _right) {
      val = _val;
      left = _left;
      right = _right;
      next = NULL;
   }
};
class Solution {
public:
   Node* connect(Node* root) {
      Node* pre = root;
      Node* nextPre = NULL;
      Node* prev = NULL;
      while(pre){
         while(pre){
            //cout << pre->val << endl;
            if(pre->left){
               if(prev){
                  prev->next = pre->left;
               }else{
                  nextPre = pre->left;
               }
               prev = pre->left;
            }
            if(pre->right){
               if(prev){
                  prev->next = pre->right;
               }else{
                  nextPre = pre->right;
               }
               prev = pre->right;
            }
            pre = pre->next;
         }
         //cout << "*" << endl;
         pre = nextPre;
         nextPre = NULL;
         prev = NULL;
      }
      return root;
   }
};
void printTree(Node* root) {
   cout << "[";
   if (root == NULL) return;
   queue<Node*> q;
   Node *curr;
   q.push(root);
   q.push(NULL);
   while (q.size() > 1) {
      curr = q.front();
      q.pop();
      if (curr == NULL){
         q.push(NULL);
      }
      else {
         // if(curr->next)
         // q.push(curr->next);
         if(curr->left)
            q.push(curr->left);
            if(curr->right)
               q.push(curr->right);
               if(curr->val == 0){
                  cout << "null" << ", ";
               }else{
                  cout << curr->val << ", ";
                  if (curr->next == NULL) cout<<"#, ";
              }
      }
   }
   cout << "]"<<endl;
}
int main() {
Node* root;
Node nodeFour(4, NULL, NULL);
Node nodeFive(5, NULL, NULL );
Node nodeSeven(7, NULL, NULL);
Node nodeSix(6, NULL, NULL);
Node nodeTwo(2,&nodeFour,&nodeFive);
Node nodeThree(3,&nodeSix,&nodeSeven);
Node nodeOne(1,&nodeTwo,&nodeThree);
root = &nodeOne;
Solution ob;
root = ob.connect(root);
printTree(root);
}

Đầu vào

[1,2,3,4,5,6,7]
Node* root;
Node nodeFour(4, NULL, NULL);
Node nodeFive(5, NULL, NULL );
Node nodeSeven(7, NULL, NULL);
Node nodeSix(6, NULL, NULL);
Node nodeTwo(2,&nodeFour,&nodeFive);
Node nodeThree(3,&nodeSix,&nodeSeven);
Node nodeOne(1,&nodeTwo,&nodeThree);
root = &nodeOne;
Solution ob;
root = ob.connect(root);

Đầu ra

[1, #, 2, 3, #, 4, 5, 6, 7, #, ]