ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมที่จะพิมพ์พาธจากโหนดรูทไปยังโหนดปลายสุดทั้งหมดในไบนารีทรีที่กำหนด
ตัวอย่างเช่น สมมติว่าเรามีไบนารีทรีต่อไปนี้
ในไบนารีทรีนี้ เรามีโหนดลีฟ 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
