Дървовидни структури

1. Основни понятия.

Дървовидна структура от базов тип t е едно от двете:

1. празната структура;

2. възел от тип t, свързан с краен брой несвързани помежду си дървовидни структури от базов тип t, наречени поддървета.

Общоприето е дървовидните структури да се наричат просто дървета.

В частност списъкът е дървовидна структура, в която всеки възел има най-много едно поддърво. Затова списъкът се нарича още изродено дърво.

Подредено дърво се нарича такова дърво, за което клоните при всеки възел са подредени. Следователно, двете подредени дървета на фиг.1 са различни.

фиг.1

Възелът y, който е непосредствено под възела x, се нарича (пряк) наследник (потомък) на x; ако x е на ниво i, казва се, че y е на ниво i+1. Обратно, възелът x се нарича родител (предшественик) на y. Приема се по дефиниция, че коренът на дървото има ниво 1. Максималното ниво на дървото се нарича негова дълбочина. Възел без наследници се нарича листо. Броят на преките наследници (изходящите връзки) на даден възел се нарича негова степен. Броят на клоните или ребрата, по които трябва да се премине, за да се достигне от корена до възел x, се нарича дължина на пътя до x.

Особено важни са подредените дървета от степен 2. Те се наричат двоични (бинарни) дървета. Двоичното дърво се дефинира рекурсивно като крайно множество от възли, което е или празно, или се състои от възел (корен) с две несвързани двоични дървета, наречени ляво и дясно поддърво.

Дървета, със степен по-голяма от 2, се наричат многоходови дървета.

Познати примери за двоични дървета са:

• семейните родословни дървета, като бащата и майката се явяват в качеството на наследници;

фиг.2