C++의 모든 노드에 대해 Inorder Successor 채우기

이 문제에서는 나무가 주어집니다. 구조체는 다음 포인터를 포함합니다. 우리의 임무는 이 포인터를 순차적 계승자로 채우는 것입니다. 노드의.

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

모든 다음 포인터는 NULL로 설정되고 우리는 노드의 inorder 후속에 대한 포인터를 설정해야 합니다.

순차 순회 − 이것은 다음과 같은 형식으로 횡단합니다.

Left node -> root Node -> right node.

순차적 계승자 - 중위 계승자는 현재 노드 다음에 오는 노드가 트리의 중위 순회입니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

순회 순회는 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