Рекурсив маълумотлар тузилмаси

Мавзу: Чизиқсиз маълумотлар тузилмаси

• Режа:
• Chiziqsiz ma’lumotlar tuzilmasi. Daraxtsimon maʻlumotlar tuzilmalari
• Binar va ko‘ptarmoqli daraxtlar. Taʻriflar va xususiyatlar. Daraxtlarni binar ko‘rinishga keltirish algoritmi. Rekursiya va ularni dasturlashda ishlatish.

Чизиқсиз маълумотлар тузилмаси

• Def.1.

• Агар тузилмани ташкил этувчи элементлар боғлиқлиги қатъий тартибланмаган бўлса, у ҳолда бундай тузилмага чизиқсиз маълумотлар тузилмаси деб аталади.

• Изоҳ

• Чизиқсиз маълумотлар тузилмасида элементлар орасидаги муносабатлар ихтиёрий бўлиши мумкин.

• Чизиқсиз тузилмани 3 та фарқли белгиси мавжуд:
• Тузилмани хар бир элементи бошқа ихтиёрий элементга мурожаат қилиш мумкин;
• Тузилмани берилган элементига мазкур тузилманинг ихтиёрий сондаги элементи мурожаат қилиши мумкин;
• Мурожаатлар оғирликга, яъни мурожаатлар иерархик кўринишга эга бўлиши мумкин.

• Чизиқсиз маълумотлар тузилмаси классификацияси

• Рўйхатлар:
• чизиқсиз икки боғламли;
• кўп боғламли;
• Дарахтлар:
• бинар дарахтлар;
• кўпўлчамли дарахтлар;
• Графлар:
• йўналтирилган граф (орграф);
• йўналтирилмаган граф (граф);
• гиперграф.

• Изоҳ

• Умуман олганда дарахт хам йўналтирилган граф бўлади.

Мисоллар

• Орграф

• D1

• D2

• D3

• Чизиқсиз боғланган рўйхат

• Дарахт

Чизиқсиз боғланган рўйхатлар

Чизиқсиз боғланган рўйхат

Рекурсия ҳақида тушунча

• Изоҳ

• Рекурсия (умуман)– бу объектни мазкур объектга мурожаат қилиш орқали аниқлашдир.

• Изоҳ

• Рекурсив алгоритм – бу алгоритмни аниқлашда ўзига бевосита ёки билвосита мурожаат қилишдир.

• Эслатма: Алгоритм ва дастурларни тузишда рекурсиядан фойдаланиш вақтни тежайди, хажми кичик бўлади, лекин итерацион усулга нисбатан дастур секинроқ ишлайди ҳамда кўпроқ хотира талаб этади.

• Def.1.

• Агар маълумотлар тузилмаси элементлари ҳам мазкур тузилмага ўхшаш тузилма бўлса, у ҳолда бундай тузилмага рекурсив маълумотлар тузилмаси дейилади.