Тармақ тәрізді құрылымды беру әдістері

Тармақтарды берудің 4 түрлі әдісі бар:

2. графтар

3. кірістірілген жақшалар

4. кірістірілген жиындар

5. кесінді тізбектер.

1. Графтар. Бәрі А түйінінен тарайды

2. Кірістірілген жақшалар:

(A(B(E,F(I,J)), C(G),D(H)))

3. Кірістірілген жиындар.

4. Кесінді тізбек.

A B E I

F J

C G

D H

Көбінесе тармақтарды бейнелеу үшін графтар қолданылады.

Дәріс 11.

Екілік бинарлық тармақтар. Екілік тармақтардың құрылымы.

Мақсаты: Екілік бинарлық тармақтар ұғымын қалыптастыру . Екілік тармақтардың құрылымы беру.

Программалауда екілік тармақтар кең қолданылады. Екілік тармақтар келесі қасиеттерге ие:

1. екілік тармақта әрбір төбенің екіден артық балалық түйіні болмайды.

2. кез келген төбенің балалық төбелері оң жақ балалық төбе және сол жақ балалық төбе болып бөлінеді. (Бұл тармақтардың графтық берілуіне қатысты айтылады. Кез келген тармақтарды оған сәйкес екілік тармақ ретінде беруге болады)

Екілік тармақ рекурсивті құрылымды болды. Себебі әрбір түйіні өзінің астындағы бұтақтың тамыры немесе түбірі болып табылады. Оны өздері де (бұтақтың) сол жақ және оң жақ бұтақтардың түбірлері болып табылатын балалары бар. Сондықтан тармақтарды өңдеу процедуоамы көбінесе рекурсивті болып табылады. Екілік тармақ дегеніміз – үш қиылыспайтын ішкі жиындарға бөлінетін түйіндер жиыны. Мұнда {R} – түбірлі түйін, {L₁,L₂,…,L_n} – R сол жақ бұтақ, {R₁, R₂,…,R_n} – R оң жақ бұтақ. Яғни оны былай бейнелеуге болады.

Оң жақ бұтақ

Сол жақ бұтақ

Екілік тармақ кез келген n деңгейде бірден бастап 2ⁿ түйіндерге дейін болуы мүмкін. Тармақтардың тығыздығы дегеніміз – тармақтың түйіндерінің оның тереңдігіне қатысты саны.

Мәліметтер құрылмы ретінде жоғары тығыздықтағы тармақтар маңызды болып табылады. Яғни, тығыз тармақ мәліметтің көп құрылымын сақтай алады және элементтерге кіруді тиімді жүзеге асыра алады.

Туындаған тармақтар, аяқталған тармақтар тығыздық шеткі шаралары немесе өлшемдері болып табылады. n тереңдіктегі аяқталған 2-к тармақ дегеніміз – 0-дан бастап n-1 –ге дейінгі әрбір деңгейі түйіндерінің толық жиыны бар және n деңгейіндегі барлық жапырақтары сол жағынан орналасқан екілік тармақтарды айтамыз. Толық тармақ дегеніміз – бұл n деңгейді 2ⁿ түйіндерде тұратын аяқталған бинарлық тармақ.

Туындалған тармақ Аяқталған тармақ

(4-деңгей) (3-деңгей)

Толық тармақ

(2-деңгей)

Тармақтың тереңдігі дегеніміз – оның түбірінен ең шеткі түйініне дейінгі ең ұзын жолдың ұзындығы болады. Мысалға, n түйіні бар туындалған тармақ үшін ең ұзақ жол ұзындығы n-1-ге тең болады. Сонда 5 түйіні бар тармақтың максимальды тереңдігі 4-ке тең болады. N түйіні бар аяқталған тармақ үшін log₂n-ң бүтін бөлігіне тең болады. Мысалы, егер тармақтың 10000 элементі болса, n=10000, онда тереңдігі - int(log₂1000)= int(13,28)=13.