O'zbеkiston respublikasi axborot texnologiyalari va kommunikatsiyalarini

O'ZBЕKISTON RESPUBLIKASI AXBOROT
TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI
RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI

TOSHKЕNT AXBOROT TЕXNOLOGIYALARI UNIVЕRSITЕTI

Labaratoriya Ishi-6

Guruh: SWD003-L2 .

Bajardi: Mirziyotov Abdumovlon.
Tekshirdi: Bo’riev Yusuf.

TOSHKENT 2022.

Daraxt tugunlari haqiqiy sonlar bo’lsin. Yozuvi berilgan kalit qiymatidan katta bo’lgan daraxt tugunlarini o’chiruvchi dastur tuzing.


#include
using namespace std;
struct Node
{
int data;
struct Node *left, *right;
};
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
struct Node1 {
int data;
struct Node1* next;
};
Node* SortedMerge(Node* a, Node* b);
void push(struct Node1** head, int data)
{
struct Node1* newNode =
(struct Node1*)malloc(sizeof(struct Node1));
newNode->data = data;
newNode->next = (*head);
(*head) = newNode;
}
void printList(struct Node1* head)
{
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
cout << "NULL" << endl;
}
Node1* SortedMerge(Node1* a, Node1* b);
void FrontBackSplit(Node1* source,
Node1** frontRef, Node1** backRef);
void MergeSort(Node1** headRef)
{
Node1* head = *headRef;
Node1* a;
Node1* b;
if ((head == NULL) || (head->next == NULL)) {
return;
}
FrontBackSplit(head, &a, &b);
MergeSort(&a);
MergeSort(&b);
*headRef = SortedMerge(a, b);
}
Node1* SortedMerge(Node1* a, Node1* b)
{
Node1* result = NULL;
if (a == NULL)
return (b);
else if (b == NULL)
return (a);
if (a->data <= b->data) {
result = a;
result->next = SortedMerge(a->next, b);
}
else {
result = b;
result->next = SortedMerge(a, b->next);
}
return (result);
}
void FrontBackSplit(Node1* source,
Node1** frontRef, Node1** backRef)
{
Node1* fast;
Node1* slow;
slow = source;
fast = source->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
int main()
{
Node *root = newNode(11);
root->left = newNode(23);
root->right = newNode(13);
root->left->left = newNode(4);
root->right->left = newNode(85);
root->right->right = newNode(7);
root->right->left->left = newNode(6);
root->right->left->right = newNode(17);
root->right->right->left = newNode(45);
root->right->right->right = newNode(410);
struct Node1* head = NULL;
cout << "Binar daraxt chapdan ongga: ";
queue q;
q.push(root);
while (!q.empty()) {
Node* current = q.front();
q.pop();
cout << current->data << " ";
push(&head, current->data);
if (current->left) q.push(current->left);
if (current->right) q.push(current->right);
}
MergeSort(&head);
cout << "\nSaralangan navbat : ";
printList(head);
return 0;
}