พิมพ์เส้นทางรากถึงปลายโดยไม่ต้องใช้การเรียกซ้ำในการเขียนโปรแกรม 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