Ma’lumotlar tuzilmasi va algoritmlar 13-ma’ruza: Daraxtsimon ma’lumotlar tuzilmasi

Kompyuter xotirasida daraxtni ifodalashaning eng qulay usuli bu uni bog’langan ro’yxatlar ko’rinishida ifodalashdir. Ro’yxat elementi tugun qiymati va chiqish darajasini o’z ichiga oluvchi informasion maydonga xamda chiqish darajasiga teng bo’lgan ko’rsatkichlar maydoniga ega bo’lishi lozim (yuqoridai rasm), ya’ni elementning har bir ko’rsatkichi ushbu elementni tugun o’g’illari bo’lgan tugunlarga yo’nalishini aniqlaydi.

• Kompyuter xotirasida daraxtni ifodalashaning eng qulay usuli bu uni bog’langan ro’yxatlar ko’rinishida ifodalashdir. Ro’yxat elementi tugun qiymati va chiqish darajasini o’z ichiga oluvchi informasion maydonga xamda chiqish darajasiga teng bo’lgan ko’rsatkichlar maydoniga ega bo’lishi lozim (yuqoridai rasm), ya’ni elementning har bir ko’rsatkichi ushbu elementni tugun o’g’illari bo’lgan tugunlarga yo’nalishini aniqlaydi.

class Node{

class Node{

private:

std:set node;

std:string: name;

int value;

bool leaf;

public:

AddNode(std:string name){

..

}

AddLeaf(int val){

..

}

...

};

Binar daraxt tushunchasi

• Daraxt – bu siklik bo’lmagan (asiklik) bog’langan graf.
• Graf – bu bo’sh bo’lmagan tugunlar va tugunlar juftliklarini bog’lovchi yoylar to’plami.
• Bog’liqlik – har bir tugunlar juftligi orasida hech bo’lmaganda bitta yo’l (yoy) mavjud
• Siklik bo’lmagan (Asiklik) – ixtiyoriy tugunlar juftligida faqat bitta yo’l mavjud.
• Binar daraxt – har bir tugunga ikkitadan ko’p bo’lmagan tugunlar bog’langan tartiblangan daraxt.