|
Qabul qildi: begulov olmos
|
| bet | 3/3 | | Sana | 26.12.2023 | | Hajmi | 329,75 Kb. | | #128536 |
Bog'liq 9iaZvX6g1OnzDdMiWy3JLFRNadaGArP3right
info
left
4.3-rasm. Binar daraxt elementining tuzilishi
19-variant
Binar daraxtda berilgan tugungacha bo‘lgan masofani aniqlashning algoritmi va dasturini keltiring
Dastur kodi
Binar daraxtda berilgan tugunga bo‘lgan masofani topish uchun recursive (qaytarish) algoritmni ishlatish mumkin. Bu algoritm tugunni topish uchun kerak bo‘lgan qidirishning har safarida bir qadam qo‘shib, tugunni alohida o‘rnatilgan qidirishning ichidan o‘tkazadi.
#include
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = right = nullptr;
}
};
int findDistance(Node* root, int target) {
if (root == nullptr) {
return -1; // Tugun topilmadi
}
if (root->data == target) {
return 0; // Tugun topildi, masofa 0
}
int leftDistance = findDistance(root->left, target);
int rightDistance = findDistance(root->right, target);
if (leftDistance >= 0) {
return leftDistance + 1; // Tugun topildi, masofa qo‘shiladi
} else if (rightDistance >= 0) {
return rightDistance + 1; // Tugun topildi, masofa qo‘shiladi
} else {
return -1; // Tugun topilmadi
}
}
int main() {
// Binar daraxt yaratish
Node* root = new Node(10);
root->left = new Node(5);
root->right = new Node(15);
root->left->left = new Node(2);
root->left->right = new Node(7);
root->right->left = new Node(12);
root->right->right = new Node(20);
int targetNodeValue = 7; // Qidiriladigan tugun qiymati
// Berilgan tugunga bo‘lgan masofani topish
int distance = findDistance(root, targetNodeValue);
if (distance >= 0) {
cout << "Tugun " << targetNodeValue << " ga bo‘lgan masofa: " << distance << endl;
} else {
cout << "Tugun topilmadi" << endl;
}
return 0;
}
|
| |
