C ++プログラミングで再帰を使用せずに、ルートからリーフへのパスを出力します。

二分木を考えると、プログラムはルートからリーフまでの複数のパスを見つける必要があります。つまり、すべてのパスを出力する必要がありますが、再帰を使用しないことが課題です。

再帰なしで実行することが制約であるため、ツリーを繰り返しトラバースします。したがって、これを実現するために、ルート要素を格納するSTLマップを使用できます。リーフノードがレベル順トラバーサルによって識別されると、ルートノードを指すマップポインターがあるため、ルートからリーフへのパスが出力されます。

上記のツリーには、ルートからリーフに到達するために生成できる複数のパスがあります-

10 -> 3 -> 140
10 -> 3 -> 162
10 -> 211 -> 100
10 -> 211 -> 146

したがって、プログラムは、指定されたすべてのパスを指定されたバイナリツリーの出力として出力する必要があります。

アルゴリズム

START
Step 1 -> create a structure of a node as
   struct Node
      struct node *left, *right
      int data
   End
Step 2 -> function to create a node
   node* newnode(int data)
   node->data = data
   node->left = node->right = NULL;
   return (node)
Step 3 -> create function to calculate the path
   void calculatePath(Node* curr, map<Node*, Node*> first)
   create STL stack<Node*> stk
   Loop While (curr)
      stk.push(curr)
      curr = first[curr]
   End
   Loop While !stk.empty()
      curr = stk.top()
      stk.pop()
      print curr->data
   End
Step 4 -> create function to find the leaf nodes
   void leaf(Node* root)
   IF root = NULL
      Return
   End
   Create STL stack<Node*> stc
   stc.push(root)
   Create STL map<Node*, Node*> prnt
   prnt[root] = NULL
   Loop while !stc.empty()
      Node* curr = stc.top()
      stc.pop()
      IF!(curr->left) && !(curr->right)
         calculatePath(curr, prnt)
      End
      IF curr->right
         prnt[curr->right] = curr
         stc.push(curr->right)
      End
      IF curr->left
         prnt[curr->left] = curr
         stc.push(curr->left)
      End
   End
STOP

例

#include <bits/stdc++.h>
using namespace std;
//structure of a node
struct Node{
   int data;
   struct Node *left, *right;
};
//function to create a new node
Node* newNode(int data){
   Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return node;
}
//this function will calculate the path
void calculatePath(Node* curr, map<Node*, Node*> first){
   stack<Node*> stk;
   while (curr){
      stk.push(curr);
      curr = first[curr];
   }
   while (!stk.empty()){
      curr = stk.top();
      stk.pop();
      cout << curr->data << " ";
   }
   cout << endl;
}
//this function will lead to the leafs
void leaf(Node* root){
   if (root == NULL)
      return;
   stack<Node*> stc;
   stc.push(root);
   map<Node*, Node*> prnt;
   prnt[root] = NULL;
   while (!stc.empty()){
      Node* curr = stc.top();
      stc.pop();
      if (!(curr->left) && !(curr->right))
         calculatePath(curr, prnt);
      if (curr->right){
         prnt[curr->right] = curr;
         stc.push(curr->right);
      }
      if (curr->left){
         prnt[curr->left] = curr;
         stc.push(curr->left);
      }
   }
}
int main(){
   Node* root = newNode(67); //it will insert the nodes to create a tree
   root->left = newNode(34);
   root->right = newNode(89);
   root->left->left = newNode(23);
   root->left->right = newNode(95);
   root->right->left = newNode(12);
   leaf(root); //call the function leaf
   return 0;
}

出力

上記のプログラムを実行すると、次の出力が生成されます

67 34 23
67 34 95
67 89 12