이진 트리가 주어지면 프로그램은 루트에서 리프까지 여러 경로를 찾아야 하므로 모든 경로가 인쇄되어야 하지만 문제는 재귀를 사용하지 않는 것입니다.
재귀 없이 트리를 수행하는 것이 제약 조건이므로 트리를 반복적으로 탐색합니다. 따라서 이를 달성하기 위해 루트 요소를 저장할 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