ในปัญหานี้ เราจะได้รับไบนารีทรี และเราต้องพิมพ์ลีฟโหนดทั้งหมดของไบนารีทรีจากขวาไปซ้าย
มาดูตัวอย่างทำความเข้าใจปัญหากัน
ป้อนข้อมูล −
ผลผลิต − 7 4 1
เพื่อแก้ปัญหานี้ เราจะต้องสำรวจไบนารีทรี การข้ามผ่านนี้สามารถทำได้สองวิธี -
สั่งจองล่วงหน้า − การข้ามผ่านนี้ใช้การเรียกซ้ำ ที่นี่ เราจะสำรวจ รูท จากนั้นไปทางซ้าย และทรีย่อยทางขวา หากเราพบโหนดปลายสุด เราจะพิมพ์ มิฉะนั้น เราจะตรวจสอบโหนดลูกของโหนดและสำรวจเพื่อหาโหนดปลายสุด
ตัวอย่าง
โปรแกรมแสดงการใช้งานโซลูชันของเรา -
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
Node* insertNode(int data) {
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void findLeafNode(Node* root) {
if (!root)
return;
if (!root->left && !root->right) {
cout<<root->data<<"\t";
return;
}
if (root->right)
findLeafNode(root->right);
if (root->left)
findLeafNode(root->left);
}
int main() {
Node* root = insertNode(21);
root->left = insertNode(5);
root->right = insertNode(11);
root->left->left = insertNode(8);
root->left->right = insertNode(98);
root->right->left = insertNode(2);
root->right->right = insertNode(8);
cout<<"Leaf nodes of the tree from right to left are:\n";
findLeafNode(root);
return 0;
} ผลลัพธ์
Leaf nodes of the tree from right to left are − 18 2 98 8
การข้ามผ่านของการสั่งซื้อทางไปรษณีย์ − การข้ามผ่านนี้เพื่อค้นหาโหนดปลายสุดจะใช้การวนซ้ำ เราจะใช้สแต็กเพื่อเก็บข้อมูลและสำรวจทรีในลักษณะโพสต์ออร์เดอร์ (ทรีย่อยขวาอันดับแรก จากนั้นออกจากทรีย่อยแล้วจึงรูท) และพิมพ์ลีฟโหนด
ตัวอย่าง
โปรแกรมแสดงการใช้งานโซลูชันของเรา -
#include<bits/stdc++.h>
using namespace std;
struct Node {
Node* left;
Node* right;
int data;
};
Node* insertNode(int key) {
Node* node = new Node();
node->left = node->right = NULL;
node->data = key;
return node;
}
void findLeafNode(Node* tree) {
stack<Node*> treeStack;
while (1) {
if (tree) {
treeStack.push(tree);
tree = tree->right;
} else {
if (treeStack.empty())
break;
else {
if (treeStack.top()->left == NULL) {
tree = treeStack.top();
treeStack.pop();
if (tree->right == NULL)
cout<<tree->data<<"\t";
}
while (tree == treeStack.top()->left) {
tree = treeStack.top();
treeStack.pop();
if (treeStack.empty())
break;
}
if (!treeStack.empty())
tree = treeStack.top()->left;
else
tree = NULL;
}
}
}
}
int main(){
Node* root = insertNode(21);
root->left = insertNode(5);
root->right = insertNode(11);
root->left->left = insertNode(8);
root->left->right = insertNode(98);
root->right->left = insertNode(2);
root->right->right = insertNode(18);
cout<<"Leaf nodes of the tree from right to left are:\n";
findLeafNode(root);
return 0;
} ผลลัพธ์
Leaf nodes of the tree from right to left are − 18 2 98 8
