Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti malumotlar Tuzilmasi fanidan mustaqil ish mavzu

Qiymati pastki har qanday topilgan bo'lsa, oxirida u qaytib, shunday qilib, u qadar targ'ib qilinadi, aks holda null qaytariladi.

Agar qiymat topilmasa, biz oxir-oqibat barg tugunining chap yoki o'ng farzandiga etib boramiz va u tarqaladi va qaytariladi.

Misol

#include

using namespace std;

struct node {

int key;

struct node *left, *right;

};

struct node *newNode(int item) {

struct node *temp = (struct node *)malloc(sizeof(struct node));

temp->key = item;

temp->left = temp->right = NULL;

return temp;

}

void inorder(struct node *root) {

if (root != NULL) {

inorder(root->left);

cout << root->key << " -> ";

inorder(root->right);

}

}

struct node *insert(struct node *node, int key) {

if (node == NULL) return newNode(key);

if (key < node->key)

node->left = insert(node->left, key);

else

node->right = insert(node->right, key);

return node;

}

struct node *minValueNode(struct node *node) {

struct node *current = node;

while (current && current->left != NULL)

current = current->left;

return current;

}

struct node *deleteNode(struct node *root, int key) {

if (root == NULL) return root;

if (key < root->key)

root->left = deleteNode(root->left, key);

else if (key > root->key)

root->right = deleteNode(root->right, key);

else {

if (root->left == NULL) {

struct node *temp = root->right;

free(root);

return temp;

} else if (root->right == NULL) {

struct node *temp = root->left;

free(root);

return temp;

}

struct node *temp = minValueNode(root->right);

root->key = temp->key;

root->right = deleteNode(root->right, temp->key);

}

return root;

}

int main() {

struct node *root = NULL;

root = insert(root, 8);

root = insert(root, 3);

root = insert(root, 1);

root = insert(root, 6);

root = insert(root, 7);

root = insert(root, 10);

root = insert(root, 14);

root = insert(root, 4);

cout << "Inorder traversal: ";

inorder(root);

cout << "\nAfter deleting 10\n";

root = deleteNode(root, 10);

cout << "Inorder traversal: ";

inorder(root);

}

Mavzu bo’yicha nazorat savollari.

1.Binar daraxt qanday hosil qilinadi?

2.Ko’p o’lchamli daraxtni qanday qilib binary daraxt ko’rinishiga keltirish mumkin? Daraxtda qanday amallarni bajarish mumkin?

3.Daraxt bir tomonlama yo’naltirilgan ro’yxatdagi kabi bo’lsa, qidiruv vaqti qancha?

Xulosa

Ikkilik qidiruv daraxti yordamida biz ish samaradorligini oshiramiz va ozimiz uchun ham yengillik bo’ladi. Bu usul orqali elementlarni osongina o’chirish yoki qoshish imkoniyatiga ega bo’lamiz.

Foydalanilgan adabiyotlar

• 
  Dinman M.I. S++. Osvoy na primerax//SPB.:BXV-Peterburg
  
• 
  Baknell Djulian M. Fundamentalnыe algoritmы i strukturы dannыx v Delphi//SPb: OOO «DiaSoftYUP»,
  

Testlar

1. Qaysi izoh tog’ri

a) key(left_son)

b) key(left_son)<=key(right_son)

c) key(left_son)>=key(right_son)

d) key(left_son)==key(right_son)

2. Agar daraxtning o’ng va chap qism daraxtlari bosqiclari va vazni teng bo`lsa…

a) bu holda binary daraxti ideal muvozanatlangan

b) bu holda binary daraxti ideal

c) bu holda binary daraxti muvozanatlangan

d) bu holda binary daraxti simmetrik

3. Binar daraxtda to’g’ri, simmetrik, teskari qaysi usulga tegishli

a) Elementlarni ma’lum bir ko’rinishda tartiblash yoki chop etish

b) Daraxt tugunini o’chirish

c) Daraxtga yangi tugun qo’yish

d) Daraxtda ideal tugun ko’rish

4. Quyida keltirilgan kodning xato qismi topilsin

Node *q=NULL;

Node *p=tree;

while(p!=NULL){

q=p;

if(key==p->key){

search=p;

return 0;

}

If(key
key) p=p->left;

else p=p->right;

}

1. 
   If(key
   key) p=p->left;
   

2. 
   else p<=p->right;
   

3. 
   if(key=p->key)
   

4. 
   else p=p->left;
   

5. Qaysi xolda o’g’il ota orniga joylashtiriladi

a) Topilgan tugun faqatgina bitta o’g’ilga ega bo’lsa

b) Topilgan tugun terminal bo’lsa

c) O’chirilayotgan tugun ikkita bo’lsa

d) O’chirilayotgan tugun terminal bo’lsa