Зертханалық жұмыс №2
Тақырыбы:Ағаш типті мәліметтер құрылымдарын ұйымдастыру.
Жалпы мәлімет
Тармақ дегеніміз – иеархиялық құрылым құратын элементтер мен қатынастардың жиынтығы.
Тармақтың элементтері түйін деп аталады. Ағаш тәрізді құрылым түпкі деп аталатын алғашқы бір түйіннен басталатын көптеген түйіндер жиынтығын құрайды.
0-деңгей 1-деңгей 2-деңгей 3-деңгей
Мұнда ағаштың түбірі дегеніміз – ары қарай түбірі болмайтын төбесі, яғни мұндағы А. Әрбір тармақтың бір ғана түбірі болады. Тармақтың ең төменгі түйіндері E, F, G, H жапырақ деп аталады. Егер тармақтың элементі жапырақ болмаса, онда оны тармақтың ішкі түйіні немесе төбесі деп аталады. Бос тармақ дегеніміз – ешқандай төбесі жоқ тармақты атаймыз. Балалық төбесі деп – тармақта орналасқан өзінің ата-аналық төбесінен төмен қарай тұрған және онымен тікелей байланысқан төбені атаймыз. Мысалға, егер i төбесі F төбесіне қатысты балалық төбесі болса, онда F төбесі I төбесіне қатысты ата-аналық төбе деп аталады.
Балалық түйіндер және олардың балалық түйіндері ұрпақ деп аталады. Мысалға, E, F және I, J B – түйінінің ұрпақтары.
Тектері бұл түйіннің ата-аналары немесе ата-әжелері.
Тармақтың әрбір түйіні осы түйіннен және барлық ұрпақтарынан тұратын бұтақтың түбірі болып табылады. Мысалы, В төбесі E,F,I,J деңгейінің түйіні. Мысалға, F түйіні F,I,J түйіндерінен тұратын бұтақтың түбірі болып табылады. G түйіні ұрпақсыз бұтақтың түйіні. А түйіні өзі тармақ болып табылатын бұтақтың түбірі.
Кез келген түйіннен түйіннен бастап оның ұрпақтарына қарай жүру белгілі бір жол бойымен жүзеге асады. Мысалға, А түбірінен бастап F түйініне дейінгі жол A,B,F төбелерінен өтеді. Кез келген түйіннен оның ұрпақтарына баратын жол жалғыз ғана болады. Түйіннің деңгейі дегеніміз – ол түбірден осы осы түйінге дейінгі жолдың ұзындығы. Мысалға, А түбірінің деңгейі 0-ға тең. Түбірдің әрбір баласының деңгейі 1-ге тең. Мысалға F түйіні 2 деңгейдегі ұзындығы 2-ге тең түйін болып табылады.
Тармақтың тереңдігі дегеніміз – оның кез келген түйінінің максимальды деңгейі немесе тармақтың тереңдігі дегеніміз ол түбірден бастап түйінге дейінгі ең ұзақ жолдың ұзындығы.
Тармақ тәрізді құрылымды беру әдістері
Тармақтарды берудің 4 түрлі әдісі бар:
графтар
кірістірілген жақшалар
кірістірілген жиындар
кесінді тізбектер.
1. Графтар. Бәрі А түйінінен тарайды
2. Кірістірілген жақшалар:
(A(B(E,F(I,J)), C(G),D(H)))
Кірістірілген жиындар.
4. Кесінді тізбек.
A B E I
F J
C G
D H
Көбінесе тармақтарды бейнелеу үшін графтар қолданылады.
Тапсырмалар: Реттелген екілік тармақ жасап, оны экранға шығаратын бағдарлама құру керек.