Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình in đường dẫn từ nút gốc đến tất cả các nút lá trong một cây nhị phân nhất định.
Ví dụ:giả sử chúng ta có cây nhị phân sau
Trong cây nhị phân này, chúng ta có 4 nút lá. Do đó, chúng ta có thể có 4 đường dẫn từ nút gốc đến nút lá.
Để giải quyết vấn đề này, chúng tôi sẽ sử dụng phương pháp lặp lại. Trong khi thực hiện đặt hàng trước của cây nhị phân, chúng ta có thể lưu trữ các con trỏ cha trong một bản đồ. Bất cứ khi nào trong quá trình truyền tải, chúng ta gặp một nút lá, chúng ta có thể dễ dàng in đường dẫn của nó từ nút gốc bằng cách sử dụng con trỏ mẹ.
Ví dụ
#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;
} Đầu ra
101 82 34 101 82 55 101 23 29