C++を使用して再帰を使用せずにルートからリーフへのパスを出力するプログラム

このチュートリアルでは、ルートノードから特定のバイナリツリー内のすべてのリーフノードへのパスを出力するプログラムについて説明します。

たとえば、次の二分木があるとしましょう

この二分木には、4つのリーフノードがあります。したがって、ルートノードからリーフノードへのパスは4つになります。

これを解決するために、反復アプローチを使用します。二分木のプレオーダートラバーサルを実行している間、マップに親ポインタを格納できます。トラバーサル中にリーフノードに遭遇したときはいつでも、親ポインタを使用してルートノードからそのパスを簡単に出力できます。

例

#include <bits/stdc++.h>>
using namespace std;
struct Node{
   int data;
   struct Node *left, *right;
};
//to create a new node
Node* create_node(int data){
   Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return node;
}
//printing the path from root to leaf
void print_cpath(Node* curr, map<Node*, Node*> parent){
   stack<Node*> nodes_stack;
   while (curr){
      nodes_stack.push(curr);
      curr = parent[curr];
   }
   while (!nodes_stack.empty()){
      curr = nodes_stack.top();
      nodes_stack.pop();
      cout << curr->data << " ";
   }
cout << endl;
}
//to perform pre order traversal
void preorder_traversal(Node* root){
   if (root == NULL)
      return;
   stack<Node*> nodeStack;
   nodeStack.push(root);
   map<Node*, Node*> parent;
   parent[root] = NULL;
   while (!nodeStack.empty()){
      Node* current = nodeStack.top();
      nodeStack.pop();
      if (!(current->left) && !(current->right))
         print_cpath(current, parent);
      if (current->right){
         parent[current->right] = current;
         nodeStack.push(current->right);
      }
      if (current->left){
         parent[current->left] = current;
         nodeStack.push(current->left);
      }
   }
}
int main(){
   Node* root = create_node(101);
   root->left = create_node(82);
   root->right = create_node(23);
   root->left->left = create_node(34);
   root->left->right = create_node(55);
   root->right->left = create_node(29);
   preorder_traversal(root);
   return 0;
}

出力

101 82 34
101 82 55
101 23 29