C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++の各ノードに次の右ポインタを設定する


完全な二分木があり、各ノードに次のフィールドがあるとします:(データ、左、右、次)、左は左のサブツリーを指し、右は右のサブツリーを指し、次のポインターは次のノードを指します。右側にノードがない場合、それはnullになります。したがって、最初に次の各ポインタがnullに設定され、リンクを作成する必要があります。ツリーが最初のツリーのようであるとすると、次のノードに変換されます-

C++の各ノードに次の右ポインタを設定する


C++の各ノードに次の右ポインタを設定する

これを解決するには、次の手順に従います-

  • pre:=root、nextPre:=null、prev:=nullを設定します
  • preがnullではない場合
    • preがnullではない場合
      • preの左側がnullでない場合
        • prevがnullでない場合は、prevの次を:=preの左側に設定します。それ以外の場合は、nextPre:=preの左側を設定します
        • prev:=preの左側
      • preの権利がnullでない場合
        • prevの次を設定:prevがnullでない場合はpreの権利、それ以外の場合はnextPre:=preの権利
        • prev:=preの権利
    • pre:=nextPre
    • nextPreをnullに設定し、prevをnullに設定
  • nullを返す

理解を深めるために、次の実装を見てみましょう-

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

入力

[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);

出力

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

  1. C++のリンクリスト内の最大値の右側のノードへのポイントアービットポインタ

    この問題では、値、リンクポインター、および任意のポインターを持つリンクリストが提供されます。私たちのタスクは、リンクリストの右側にある最大値を指すように任意のポインターポイントを作成することです。 問題を理解するために例を見てみましょう ここでは、リンクリストの次の任意のポインタを見ることができます。これは、リンクリストの右側にある最大の要素を指しています。 12 -> 76, 76 -> 54, 54 -> 8, 8 -> 41 この問題を解決するには、ノードの右側にある最大の要素を見つける必要があります。このために、リンクリストを逆方向にトラバースし、す

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

    この問題では、ツリーが与えられます。構造体には、次にポインタが含まれています。私たちのタスクは、このポインタに順序付けられた後継者を入力することです。 ノードの。 struct node {    int value;    struct node* left;    struct node* right;    struct node* next; } 次のすべてのポインターはNULLに設定されており、ノードの順序どおりの後続ポインターにポインターを設定する必要があります。 順序のないトラバーサル −これは次