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

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

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

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

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

typedef int info_type;

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

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

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

Користење

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

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

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

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