Дрво (податочна структура)

Едноставно неподредено дрво

Во компјутерските науки, дрво е динамична рекурзивна податочна структура.

Структурата на дрвото се состои од јазол, што во себе содржи податочен клуч (некој податок). Јазолот исто така содржи врски (линкови) што покажуваат кон други јазли.

Пример за дрво во C

Претстава на јазол на дрво во програмскиот јазик C коe што содржи две врски (покажувачи кон други јазли).

typedef int info_type;

typedef struct element
{
    info_type info;
    struct element *left_link, *right_link;
}   jazol, *jazolp;

Вака дефинираното дрво се вика бинарно дрво.

За оваа структура може да се дефинираат едноставни рекурзивни функции коишто рекурзивно ќе вршат динамичко алоцирање/деалоцирање на меморија за покажувачите во структурата, со цел да се создаде структурата онака како што сака програмерот.

Користење

Дрвата се користат:

• за претставување и алоцирање на некоја хиерархиска структура на податоци на динамичен начин.
• за бинарно пребарување на податоци.
• кај датотечните системи.
• кај базите на податоци.
• за парсирање на изрази кај програмските јазици.
• кај алгоритмите за компресија и архивирање на датотеки.
• кај компјутерска имплементација на некои игри (пр. икс-нула, шах...)
• кај некои алгоритми за сортирање.

Надворешни врски

• Опис од ideainfo.8m.com
• Опис од „Речник на алгоритми и податочни структури“
• Класа за дрво во C++
• Листа на податочни структури од „LEDA“
• NGenerics : имплементација во C#