เติม Inorder Successor สำหรับโหนดทั้งหมดใน C ++

ในปัญหานี้เราได้รับต้นไม้ โครงสร้างประกอบด้วยตัวชี้ถัดไป งานของเราคือเติมตัวชี้นี้ด้วย ผู้สืบทอดลำดับ ของโหนด

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

ตัวชี้ถัดไปทั้งหมดถูกตั้งค่าเป็น NULL และเราต้องตั้งค่าตัวชี้ให้เป็นตัวต่อเนื่องที่ไม่เรียงลำดับของโหนด

การข้ามเส้นทางที่ไม่เป็นระเบียบ − นี้จะวนไปตามรูปแบบต่อไปนี้

Left node -> root Node -> right node.

ผู้สืบทอด Inorder − ส่วนต่อที่ไม่เป็นระเบียบคือโหนดที่มาหลังจากโหนดปัจจุบันคือการข้ามผ่านที่ไม่เป็นระเบียบของทรี

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

การข้ามผ่านในลำดับคือ 7 8 3 5 9 1

การเติมแต่ละโหนด -

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

เพื่อแก้ปัญหานี้ เราจะสำรวจต้นไม้แต่กลับกันในรูปแบบคำสั่ง จากนั้นเราจะใส่องค์ประกอบการเยี่ยมชมครั้งสุดท้ายไปที่หมายเลขถัดไป

ตัวอย่าง

โปรแกรมแสดงการใช้งานโซลูชันของเรา

#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;
}

ผลลัพธ์

การเติมต้นไม้โดยการเพิ่มผู้สืบทอดลำดับต่อไป

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