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

Од Википедија — слободната енциклопедија
Прејди на: содржини, барај
Едноставно неподредено дрво

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

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

Пример за дрво во C[уреди]

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

typedef int info_type;

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

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

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

Користење[уреди]

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

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

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