C++のバイナリツリーのノードのポストオーダーサクセサ

この問題では、二分木とノードが与えられます。私たちのタスクは、ノードのポストオーダーサクセサをバイナリツリーに出力することです。

バイナリ ツリー は、各ノードが最大2つの子ノードを持つことができる特殊なタイプのツリーです。

ポストオーダートラバーサル はツリートラバーサル手法であり、最初の左のサブツリーが右のサブツリーよりもトラバースされ、ルートが最後にトラバースされます。

上記のツリーのポストオーダートラバーサル： 8 4 2 7 9 6

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

入力 −上記の例の二分木、node =7

出力 − 9

説明 −二分木のポストオーダートラバーサルでそれを見ることができます。

この問題を解決するためのシンプルで簡単なnoobの解決策は、注文後のトラバーサルを見つけて、トラバーサルの横にある番号を印刷することです。

しかし、より効果的な解決策を学ぶ必要があります。

効果的な解決策には、ポストオーダートラバーサルに関する一般的な観察を使用することが含まれます。

• ルートはポストオーダートラバーサルの最後のノードであるため、その後継ノードはNULLです。

• 現在のノードが正しい子である場合、親ノードは後継ノードです。

• 現在のノードが子のままになっている場合は、

  • 右の兄弟が存在しない場合、後継者は親ノードです

  • 右の兄弟が存在する場合、ノードまたはその左端の子のいずれかが後継です。

この方法は効果的であり、時間計算量はO（h）、彼の木の高さです。

例

ソリューションの実装を示すプログラム

#include <iostream>
using namespace std;
struct Node {
   struct Node *left, *right, *parent;
   int value;
};
struct Node* insertNode(int value) {
   Node* temp = new Node;
   temp->left = temp->right = temp->parent = NULL;
   temp->value = value;
   return temp;
}
Node* findPostorderSuccessor(Node* root, Node* n) {
   if (n == root)
      return NULL;
   Node* parent = n->parent;
   if (parent->right == NULL || parent->right == n)
      return parent;
   Node* curr = parent->right;
   while (curr->left != NULL)
      curr = curr->left;
   return curr;
}
int main(){
   struct Node* root = insertNode(6);
   root->parent = NULL;
   root->left = insertNode(2);
   root->left->parent = root;
   root->left->left = insertNode(8);
   root->left->left->parent = root->left;
   root->left->right = insertNode(4);
   root->left->right->parent = root->left;
   root->right = insertNode(9);
   root->right->parent = root;
   root->right->left = insertNode(7);
   root->right->left->parent = root->right;
   root->left->right->left = insertNode(14);
   struct Node* successorNode = findPostorderSuccessor(root, root->left->right);
   if (successorNode)
      cout<<"Postorder successor of "<<root->left->right->value<<" is "<<successorNode->value;
   else
      cout<<"Postorder successor of "<<root->left->right->value<<" is NULL";
   return 0;
}

出力

Postorder successor of 4 is 2