C++で再帰およびスタックなしのバイナリツリーのポストオーダートラバーサル

再帰とスタックを使用せずにツリーをトラバースします。深さ優先探索ベースの手法を使用し、データはハッシュテーブルに保存されます。 。

例

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

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node *left, *right;
};
void postOrderTraversal(struct Node* head) {
   struct Node* temp = head;
   unordered_set<Node*> visited;
   while (temp && visited.find(temp) == visited.end()) {
      if (temp->left &&
         visited.find(temp->left) == visited.end())
         temp = temp->left;
      else if (temp->right &&
         visited.find(temp->right) == visited.end())
         temp = temp->right;
      else {
         cout<<temp->data<<"\t";
         visited.insert(temp);
         temp = head;
      }
   }
}
struct Node* insertNode(int data){
   struct Node* node = new Node;
   node->data = data;
   node->left = NULL;
   node->right = NULL;
   return (node);
}
int main(){
   struct Node* root = insertNode(6);
   root->left = insertNode(2);
   root->right = insertNode(9);
   root->left->left = insertNode(8);
   root->left->right = insertNode(4);
   root->right->left = insertNode(7);
   root->right->left->left = insertNode(13);
   cout<<"Post Order Traversal of the binary tree :\n";
   postOrderTraversal(root);
   return 0;
}

出力

Post Order Traversal of the binary tree :
8    4    2    13    7    9    6

同じソリューションを更新して、ハッシュテーブルの使用をなくすことができます。その仕事は訪問したノードを保存することです。システムの負荷を軽減するために、ツリー自体のすべてのノードに訪問済みフラグを追加します。これにより、アルゴリズムが改善されます。

より効果的な解決策は、順序付けられていないマップを使用することです。これにより、ヘッドへのトラックバックのオーバーヘッドが削減されます。

例

実装を示すプログラム

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node *left, *right;
   bool visited;
};
void postOrderTraversal(Node* root) {
   Node* n = root;
   unordered_map<Node*, Node*> postorder;
   postorder.insert(pair<Node*, Node*>(root, nullptr));
   while (n) {
      if (n->left && postorder.find(n->left) == postorder.end()) {
         postorder.insert(pair<Node*, Node*>(n->left, n));
         n = n->left;
      }
      else if (n->right && postorder.find(n->right) == postorder.end()) {
         postorder.insert(pair<Node*, Node*>(n->right, n));
         n = n->right;
      }
      else {
         cout<<n->data<<"\t";
         n = (postorder.find(n))->second;
      }
   }
}
struct Node* insertNode(int data) {
   struct Node* node = new Node;
   node->data = data;
   node->left = NULL;
   node->right = NULL;
   node->visited = false;
   return (node);
}
int main() {
   struct Node* root = insertNode(6);
   root->left = insertNode(2);
   root->right = insertNode(9);
   root->left->left = insertNode(8);
   root->left->right = insertNode(4);
   root->right->left = insertNode(7);
   root->right->left->left = insertNode(13);
   cout<<"Post Order Traversal of the binary tree :\n";
   postOrderTraversal(root);
   return 0;
}

出力

Post Order Traversal of the binary tree :
8    4    2    13    7    9    6