C++のすべてのノードにInorderSuccessorを入力します

この問題では、ツリーが与えられます。構造体には、次にポインタが含まれています。私たちのタスクは、このポインタに順序付けられた後継者を入力することです。 ノードの。

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

次のすべてのポインターはNULLに設定されており、ノードの順序どおりの後続ポインターにポインターを設定する必要があります。

順序のないトラバーサル −これは次の形式でトラバースします

Left node -> root Node -> right node.

後継者の注文 −インオーダーサクセサは、現在のノードがツリーのインオーダートラバーサルの後に来るノードです。

問題を理解するために例を見てみましょう

順序どおりの走査は783 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