Daraxtsimon tuzilmalarni tadqiq qilish individual topshiriqlar

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: 830-19

Bajardi: Gulimmatov Oxunjon

TOSHKENT 2020

6-LABORATORIYA ISHI 5-variant

DARAXTSIMON TUZILMALARNI TADQIQ QILISH

INDIVIDUAL TOPSHIRIQLAR

Binar daraxt tuzilmasini 2 bog’lamli ro’yxatlar yordamida shakllantirish. Standart amallarini(yangi tugun qo’shish, ekranga chiqarish, tozalash, tugun o'chirish va individual topshiriqni) funktsiyalar yordamida shakllantirish.

#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;

}