• Qo’yilgan masala.
  • Amaliy mashg’ulot- 11 Mavzu: Binar daraxtlarni tashkil qilish. Binar daraxtlar ustida amallar. Binar daraxtlar. Daraxt balandligi va ko’ruv. Ishdan maqsad




    Download 0,81 Mb.
    Pdf ko'rish
    bet1/9
    Sana11.01.2024
    Hajmi0,81 Mb.
    #135190
      1   2   3   4   5   6   7   8   9
    Bog'liq
    4-dedline Mansurbek



    AMALIY MASHG’ULOT- 11 
    Mavzu: Binar daraxtlarni tashkil qilish. Binar daraxtlar ustida amallar. 
    Binar daraxtlar. Daraxt balandligi va ko’ruv . 
    Ishdan maqsad. Ushbu laboratoriya ishida talabalar Binar daraxtlar 
    tushunchasi bilan tanishib chiqishi hamda daraxt balandligi va binar daraxtlar 
    ustida amallar bajarish 
    Qo’yilgan masala. Talabalar topshiriq variantiga mos ravishda binar darxtlar 
    ustida berilgan amallar bilan ishlash ko’nikmasiga ega bo’lishlari kerak. 
    Ish tartibi: 

    Tajriba ishi nazariy ma’lumotlarini o‘rganish; 

    Berilgan topshiriqning algoritmini ishlab chiqish; 

    C++ dasturlash muhitida dasturni yaratish; 

    Natijalarni tekshirish; 

    Hisobotni tayyorlash va topshirish. 
    Daraxtlar: qatorlar, bog'langanro'yxatlar, Stekvanavbatlardanfarqlio'laroq, 
    buchiziqlima'lumotlartuzilmalari, daraxtlarma'lumotlarningierarxiktuzilmalari. 
    Daraxtso'zbirikmasi: engyuqoritugundaraxtningildizidebataladi. To'g'ridan-
    to'g'ri element ostida bo'lgan elementlar uning bolalari deb ataladi. To'g'ridan-to'g'ri 
    biron bir narsaning yuqorisidagi element uning ota-onasi deb ataladi. Masalan, "a" - 
    "f" ning farzandi, "f" - "a" ning ota-onasi. Va nihoyat, bolalari bo'lmagan elementlar 
    barglar deb nomlanadi. 
     
    Nima uchun daraxtlar? 
    1. Daraxtlardan foydalanishning bir sababi tabiiy ravishda ierarxiyani 
    shakllantiradigan ma'lumotlarni saqlamoqchi bo'lganligingiz bo'lishi 
    mumkin. Masalan, kompyuterdagi fayl tizimi: 


     
    2. Daraxtlar (ba'zi buyurtma bilan, masalan, BST) o'rtacha kirish / qidirishni 
    ta'minlaydi (bog'langan ro'yxatdan tezroq va massivlardan sekinroq). 
    3. Daraxtlar o'rtacha kiritishni / o'chirishni ta'minlaydi (Arraylardan tezroq va 
    tartibsiz bog'langan ro'yxatlarga qaraganda sekinroq). 
    4. bog'langan ro'yxatlar singari va massivlardan farqli o'laroq, daraxtlar 
    tugunlar sonining yuqori chegarasiga ega emas, chunki tugunlar ko'rsatgichlar 
    yordamida bog'langan. 
    Daraxtlarning asosiy dasturlariga quyidagilar kiradi: 
    1. Ierarxik ma'lumotlarning manipulyatsiyasi. 
    2. Ma'lumotni qidirishni osonlashtiring (daraxtlarni kesib o'tishga qarang). 
    3. Ma'lumotlarning saralangan ro'yxatlarini manipulyatsiya qilish. 
    4. Vizual effektlar uchun raqamli tasvirlarni kompozitsiya qilish uchun ish 
    oqimi sifatida. 
    5. Router algoritmlari 
    6. Ko'p bosqichli qaror qabul qilish shakli (qarang biznes shaxmat). 
    Ikkilik daraxt: elementlari ko'pi bilan 2 ta bolaga ega bo'lgan daraxt binar daraxt 
    deb ataladi. Ikkilik daraxtdagi har bir element faqat 2 boladan iborat bo'lishi 
    mumkinligi sababli, biz ularni odatda chap va o'ng bola deb nomlaymiz. 
    Ikkala daraxtning C tilidagi vakili: Daraxt daraxtning eng yuqori tuguniga 
    ko'rsatgich bilan ifodalanadi. Agar daraxt bo'sh bo'lsa, u holda root qiymati NULL 
    bo'ladi. 
    Daraxt tuguni quyidagi qismlarni o'z ichiga oladi. 
    1. Ma'lumotlar 
    2. Chap bolaga ko'rsatgich 
    3. O'ng bolaga ko'rsatgich 
    Cda biz tuzilmalar yordamida daraxt tugunini ifodalashimiz mumkin. Quyida 
    butun sonli ma'lumotlar bilan daraxt tuguniga misol keltirilgan. 


    C-dagi birinchi oddiy daraxt 
    Yaratilgan daraxt quyidagicha bo'ladi. 
    #include  
    using namespace std;
    struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    // val is the key or the value that
    // has to be added to the data part
    Node(int val)
    {
    data = val;
    // Left and right child for node
    // will be initialized to null
    left = NULL;
    right = NULL;
    }
    };
    int main()
    {
    /*create root*/ 
    struct Node* root = new Node(1);
    /* following is the tree after above statement
    1
    / \
    NULL NULL
    */ 
    root->left = new Node(2);
    root->right = new Node(3);


     /* 2 and 3 become left and right children of 1
    1
    / \
    2 3
    / \ / \
    NULL NULL NULL NULL
    */ 
    root->left->left = new Node(4);
    /* 4 becomes left child of 2
    1
    / \
    2 3
    / \ / \
    4 NULL NULL NULL 
    / \
    NULL NULL
    */ 
    return 0;
    }
     
    Qisqacha mazmun: Daraxt - bu ma'lumotlarning ierarxik tuzilishi. 
    Daraxtlarning asosiy ishlatilishlariga ierarxik ma'lumotlarni saqlash, o'rtacha kirish 
    va kiritish / o'chirish operatsiyalarini ta'minlash kiradi. Ikkilik daraxtlar - bu har bir 
    tugunda ko'pi bilan ikkita boladan iborat bo'lgan alohida holatlar. 

    Download 0,81 Mb.
      1   2   3   4   5   6   7   8   9




    Download 0,81 Mb.
    Pdf ko'rish

    Bosh sahifa
    Aloqalar

        Bosh sahifa



    Amaliy mashg’ulot- 11 Mavzu: Binar daraxtlarni tashkil qilish. Binar daraxtlar ustida amallar. Binar daraxtlar. Daraxt balandligi va ko’ruv. Ishdan maqsad

    Download 0,81 Mb.
    Pdf ko'rish