4-amaliy mashg’ulot

4.10. Binar daraxt balandligi
Binar daraxtning balandligi deb daraxt bosqichlari soniga aytiladi. Binar daraxt balandligini aniqlash uchun uning har bir tuguni chap va o‘ng qismdaraxtlari balandliklari solishtiriladi va maksimal qiymat balandlik deb olinadi. Misol uchun quyidagi 8.9-rasmdagi daraxtning balandligi 2 ga teng.

4.9-rasm. Binar daraxt balandligi.

Topshiriq

VARYANT -10
Daraxt tugunlari haqiqiy sonlar bo‘lsin. Daraxt barcha tugunlarini o‘rta arifmetigiga teng qiymatli tugunni berilgan binar daraxtga kiritish algoritmi va dasturini keltiring.

#include

using namespace std;

// Daraxt tugunlari uchun struct

struct Node {
int data;
Node* left;
Node* right;

Node(int value) : data(value), left(nullptr), right(nullptr) {}

};

// O'rta arifmetigini topshiruvchi funksiya

int findMid(int arr[], int start, int end) {
return start + (end - start) / 2;
}

// Binar daraxtga tugun qo'shish funksiya

Node* insertBST(Node* root, int value) {
if (root == nullptr)
return new Node(value);

if (value < root->data)

root->left = insertBST(root->left, value);
else if (value > root->data)
root->right = insertBST(root->right, value);

return root;

}

// Massivdan binar daraxt yaratish funksiya

Node* createBST(int arr[], int start, int end) {
if (start > end)
return nullptr;

int mid = findMid(arr, start, end);

Node* root = new Node(arr[mid]);

root->left = createBST(arr, start, mid - 1);

root->right = createBST(arr, mid + 1, end);

return root;

}

// Barcha daraxt tugunlarini chiqarish funksiya

void printTree(Node* root) {
if (root != nullptr) {
printTree(root->left);
cout << root->data << " ";
printTree(root->right);
}
}

int main() {

// Haqiqiy sonlar massivi
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

// Massiv o'rta arifmetigini topshirish

int n = sizeof(arr) / sizeof(arr[0]);
int mid = findMid(arr, 0, n - 1);

// Binar daraxtni yaratish

Node* root = createBST(arr, 0, n - 1);

// O'rta arifmetigiga teng bo'lgan tugunni qo'shish

root = insertBST(root, arr[mid]);

// Barcha tugunlarni chiqarish

cout << "Barcha tugunlar: ";
printTree(root);

return 0;

}