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

Од Википедија

Оваа статија не наведува никакви извори или референци. (ноември 2009) Ве молиме помогнете со тоа што ќе додадете наводи до доверливи извори. Непроверливата содржина може да биде изменета или отстранета.

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

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

[уреди] Пример за дрво во 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#