Điền Inorder kế thừa cho tất cả các nút trong C ++

Trong bài toán này, chúng ta được đưa ra một cái cây. Cấu trúc chứa một con trỏ tiếp theo. Nhiệm vụ của chúng tôi là điền con trỏ này với inorder kế nhiệm của nút.

struct node {
   int value;
   struct node* left;
   struct node* right;
   struct node* next;
}

Tất cả con trỏ tiếp theo được đặt thành NULL và chúng ta phải đặt con trỏ thành nút kế nhiệm nhỏ hơn.

Inorder traversal - Điều này truyền qua biểu mẫu sau,

Left node -> root Node -> right node.

Người kế nhiệm Inorder - nút tiếp theo thứ nhất là nút xuất hiện sau nút hiện tại là nút truyền tải không theo thứ tự của cây.

Hãy lấy một ví dụ để hiểu vấn đề,

Truyền theo thứ tự là 7 8 3 5 9 1

Đang điền từng nút -

Next of 5 is 9
Next of 8 is 3
Next of 7 is 8
Next of 3 is 5
Next of 9 is 1

Để giải quyết vấn đề này, chúng ta sẽ đi ngang cây nhưng ngược lại ở dạng thứ tự. Sau đó, chúng tôi sẽ đặt phần tử lượt truy cập cuối cùng vào phần tử tiếp theo của số.

Ví dụ

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

#include<iostream>
using namespace std;
struct node {
   int data;
   node *left;
   node *right;
   node *next;
};
node* insertNode(int data){
   node* Node = new node();
   Node->data = data;
   Node->left = NULL;
   Node->right = NULL;
   Node->next = NULL;
   return(Node);
}
void populateTree(node* pop){
   static node *next = NULL;
   if (pop){
      populateTree(pop->right);
      pop->next = next;
      next = pop;
      populateTree(pop->left);
   }
}
void printNext(node * root) {
   node *ptr = root->left->left;
   while(ptr){
      cout<<"Next of "<<ptr->data<<" is ";
      cout<<(ptr->next? ptr->next->data: -1)<<endl;
      ptr = ptr->next;
   }
}
int main() {
   node *root = insertNode(15);
   root->left = insertNode(99);
   root->right = insertNode(1);
   root->left->left = insertNode(76);
   root->left->right = insertNode(31);
   cout<<"Populating the Tree by adding inorder successor to the next\n";
   populateTree(root);
   printNext(root);
   return 0;
}

Đầu ra

Đưa vào Cây bằng cách thêm người kế nhiệm inorder vào cây tiếp theo

Next of 76 is 99
Next of 99 is 31
Next of 31 is 15
Next of 15 is 1
Next of 1 is -1