Drzewo (ang. tree) jest strukturą danych zbudowaną z elementów, które nazywamy węzłami (ang. nodes). Dane przechowuje się w węzłach drzewa. Węzły są ze sobą powiązane w sposób hierarchiczny za pomocą krawędzi (ang. edges), które zwykle przedstawia się za pomocą strzałki określającej hierarchię. Pierwszy węzeł drzewa nazywa się korzeniem (ang. root node). Od niego "wyrastają" pozostałe węzły, które będziemy nazywać synami, dziećmi, rodzeństwem, węzłami podrzędnymi (ang. child nodes). Węzeł nadrzędny w stosunku do danego węzła potomnego nazywamy ojcem, rodzicem (ang. parent node). Synowie są węzłami podrzędnymi w strukturze hierarchicznej. Synowie tego samego ojca są nazywani rodzeństwem (ang. sibling nodes). Rodzice są węzłami nadrzędnymi w strukturze hierarchicznej. Jeśli węzeł nie posiada synów, to nazywa się liściem (ang. leaf node), w przeciwnym razie nazywa się węzłem wewnętrznym (ang. internal node, inner node, branch node).

Struktura drzewa
		A…H – węzły drzewa, strzałki – krawędzie. Zwrot określa kierunek hierarchii rodzić → syn, A – korzeń drzewa, B, C, D – rodzeństwo węzła A, który jest dla nich ojcem, E, F, G – rodzeństwo węzła B, który jest dla nich ojcem, H – syn węzła D, który jest dla niego ojcem, A, B, D – węzły wewnętrzne C, E, F, G, H – liście

Za wyjątkiem korzenia wszystkie pozostałe węzły w drzewie posiadają swojego ojca. W normalnym drzewie liczba synów dla dowolnego węzła nie jest ograniczona. Istnieje jednakże bardzo ważna klasa drzew, w których dany węzeł może posiadać co najwyżej dwóch synów. Noszą one nazwę drzew binarnych lub B-drzew (ang. binary trees, B-trees).

Ciąg węzłów połączonych krawędziami nazwiemy ścieżką (ang. path). Od korzenia do określonego węzła w drzewie wiedzie zawsze dokładnie jedna ścieżka prosta, tzn. taka, iż zawarte w niej węzły pojawiają się tylko jeden raz. Długością ścieżki (ang. path length) nazwiemy liczbę krawędzi łączących węzły w ścieżce. Dla naszego drzewa mamy następujące ścieżki proste od korzenia do kolejnych węzłów:

Struktura drzewa		Ścieżki
		ścieżka od A do A: długość 0: A ścieżka od A do B: długość 1: A→B ścieżka od A do C: długość 1: A→C ścieżka od A do D: długość 1: A→D ścieżka od A do E: długość 2: A→B→E ścieżka od A do F: długość 2: A→B→F ścieżka od A do G: długość 2: A→B→G ścieżka od A do H: długość 2: A→D→H

Długość ścieżki prostej od korzenia do danego węzła nazywa się poziomem węzła (ang. node level). Korzeń drzewa ma zawsze poziom 0. W naszym drzewie węzły B, C i D mają poziom 1, a E, F, G i  H mają poziom 2. Wysokość drzewa (ang. tree height) jest równa największemu poziomowi węzłów (lub najdłuższej ścieżce prostej rozpoczynającej się w korzeniu). Dla naszego drzewa wysokość jest równa 2. Wysokość węzła (ang. node height), to długość najdłuższej ścieżki prostej od tego węzła do liścia. Dla korzenia wysokość węzła jest równa wysokości drzewa:

Struktura drzewa		Wysokości węzłów
		węzeł A: wysokość = 2 węzeł B: wysokość = 1 węzeł C: wysokość = 0 węzeł D: wysokość = 1 węzeł E: wysokość = 0 węzeł F: wysokość = 0 węzeł G: wysokość = 0 węzeł H: wysokość = 0

Poziom drzewa (ang. tree level) dla danego węzła to długość ścieżki prostej od korzenia do  danego węzła.

Struktura drzewa		Poziomy
		Poziom 0: A Poziom 1: B, C, D Poziom 2: E, F, G, H

Liczba krawędzi powiązanych z danym węzłem nosi nazwę stopnia węzła (ang. node degree). Krawędzie drzewa są  krawędziami skierowanymi (ang. directed edges) i oznaczamy je za pomocą strzałek. Kierunek strzałki jednoznacznie określa pozycję w hierarchii – strzałka wychodzi od ojca i kończy się na synu. Z  tego powodu stopień węzła rozbija się na dwa stopnie:

Stopień węzła jest sumą stopnia wejściowego i wyjściowego.

Struktura drzewa
		węzeł A: we = 0, wy = 3, stopień węzła = 3 węzeł B: we = 1, wy = 3, stopień węzła = 4 węzeł C: we = 1, wy = 0, stopień węzła = 1 węzeł D: we = 1, wy = 1, stopień węzła = 2 węzeł E: we = 1, wy = 0, stopień węzła = 1 węzeł F: we = 1, wy = 0, stopień węzła = 1 węzeł G: we = 1, wy = 0, stopień węzła = 1 węzeł H: we = 1, wy = 0, stopień węzła = 1

Zwróć uwagę, że liście nie będące korzeniem (jeśli korzeń jest liściem, to jego stopień wynosi 0) mają zawsze stopień równy 1.

Drzewo, w którym węzły mogą posiadać co najwyżej dwóch synów, nazywa się drzewem binarnym (ang. binary tree, B-tree). Węzły potomne nazywamy odpowiednio synem lewym (ang. left child node) i synem prawym (ang. right child node). Drzewa binarne mają ogromne znaczenie w informatyce, ponieważ za ich pomocą można odwzorować również drzewa, których węzły posiadają dowolną liczbę synów – sposób takiego odwzorowania podamy w dalszej części rozdziału.

Drzewo binarne
		A – korzeń, ojciec węzłów B i C B, C – synowie węzła  A:     B – lewy syn węzła A,     C – prawy syn węzła A D, E – liście, synowie węzła B F, G – liście, synowie węzła C

W drzewie binarnym stopień każdego węzła nie przekracza 3. Stopień korzenia nie przekracza 2.

Regularne drzewo binarne (ang. regular binary tree, proper binary tree) zawiera wyłącznie węzły, których stopień wyjściowy jest albo równy 2 (węzeł posiada dwóch synów –  jest węzłem wewnętrznym), albo 0 (węzeł nie posiada synów – jest liściem).

Regularne drzewo binarne		Stopnie wyjściowe
		A – stopień wyjściowy 2, węzeł wewnętrzny B –  stopień wyjściowy 2, węzeł wewnętrzny C – stopień wyjściowy 2, węzeł wewnętrzny D – stopień wyjściowy 0, liść E – stopień wyjściowy 0, liść F – stopień wyjściowy 0, liść G – stopień wyjściowy 0, liść

Dla regularnego drzewa binarnego liczba węzłów na poziomie k-tym jest zawsze równa 2^k. Liczba wszystkich węzłów, czyli rozmiar drzewa (ang. binary tree size) jest równa 2^p-1, gdzie p oznacza liczbę poziomów.

Dla n węzłów liczba poziomów jest równa log₂(n+1).

Ponumerujmy poziomami kolejne węzły, idąc od strony lewej do prawej:

Numery węzłów są powiązane ze strukturą hierarchii drzewa prostymi zależnościami:

Jeśli węzeł o numerze k posiada synów, to: – lewy syn ma numer 2k+1, – prawy syn ma numer 2k+2,

Jeśli węzeł o numerze k posiada ojca, to: ojciec ma numer [(k-1)/2], […] oznacza część całkowitą.

Węzeł o numerze k znajduje się na poziomie o numerze [log₂(k+1)].

Węzeł o numerze k jest wewnętrzny, jeśli 2k+2 < n. W przeciwnym razie węzeł jest liściem.

Własności te pozwalają odwzorowywać regularne drzewo binarne w ciąg elementów i na odwrót

Kompletne drzewo binarne (ang. complete binary tree) posiada zapełnione węzłami wszystkie poziomy z wyjątkiem ostatniego, jednakże na ostatnim poziomie węzły są zapełnione począwszy od lewej strony.

Kompletne drzewo binarne

Niekompletne drzewo binarne

Kompletne drzewo binarne również da się odwzorować w ciąg węzłów. W takim drzewie liczba elementów n może być mniejsza od maksymalnej liczby węzłów, ponieważ ostatni poziom nie musi posiadać kompletu węzłów. Jednakże w przeciwieństwie do drzewa regularnego węzeł wewnętrzny może posiadać tylko jednego, lewego syna (u nas węzłem takim jest węzeł 4). Dlatego w kompletnym drzewie binarnym o rozmiarze n dla węzła o numerze k zachodzi:

2k+2 > n – węzeł jest liściem
2k+2 = n – węzeł jest ostatnim węzłem wewnętrznym i posiada tylko lewego syna
2k+2 < n – węzeł jest węzłem wewnętrznym i posiada oba węzły potomne.

Poddrzewo (ang. subtree) jest drzewem zawartym w drzewie, gdy jako korzeń przyjmiemy jeden z jego węzłów. Dla danego węzła drzewa binarnego mogą istnieć dwa poddrzewa: lewe poddrzewo (ang. left subtree) – korzeniem jest lewy syn i analogicznie prawe poddrzewo (ang. right subtree) – korzeniem jest prawy syn:

Istnieje wiele różnych rozwiązań dla reprezentacji drzew binarnych w pamięci komputera. Tutaj podamy te najprostsze.

Kompletne drzewo binarne

W tym przypadku drzewo możemy odwzorować w tablicy n-elementowej. Każdy element tablicy jest węzłem. Hierarchię drzewa przedstawiamy przy pomocy indeksów i ich własności dla kompletnych drzew binarnych. Korzeniem drzewa jest element o indeksie 0. Jego dwoma synami są kolejno elementy o indeksach 1 (lewy syn) i 2 (prawy syn). Postępując podobnie z pozostałymi węzłami otrzymamy całe drzewo binarne:

Niekompletne drzewo binarne

Drzewo odwzorowujemy podobnie jak listę. Każdy element jest strukturą, która oprócz danych zawiera dwa lub trzy wskaźniki:

Wersja uproszczona

type
  PBTnode = ^BTnode;
  BTnode  = record
    left  : PBTnode;
    right : PBTnode;
    Data: typ_danych;
  end;

struct BTnode
{
  BTnode * left;
  BTnode * right;
  typ_danych data;
};

Type BTnode
  left  As BTnode Ptr
  right As BTnode Ptr
  data  As typ_danych
End Type

class BTnode:


    def __init__(self, v):
        self.left  = None
        self.right = None
        self.data  = v

Wersja pełna

type
  PBTnode = ^BTnode;
  BTnode  = record
    up    : PBTnode;
    left  : PBTnode;
    right : PBTnode;
    Data: typ_danych;
  end;

struct BTnode
{
  BTnode * up;
  BTnode * left;
  BTnode * right;
  typ_danych data;
};

Type BTnode
  up    As BTnode Ptr
  left  As BTnode Ptr
  right As BTnode Ptr
  data  As typ_danych
End Type

class BTnode:


    def __init__(self, v):
        self.up    = None
        self.left  = None
        self.right = None
        self.data  = v

Gdzie:

up    – wskazuje ojca danego węzła.
        Dla korzenia pole to zawiera wskazanie puste
left  – wskazuje lewego syna 
right – wskazuje prawego syna 
data  – dane dowolnego typu przechowywane przez węzeł

Wskaźniki pozwalają na poruszanie się po węzłach w strukturze drzewa. Wskaźniki left i right umożliwiają przechodzenie w dół drzewa. Wskaźnik up prowadzi w górę do ojca danego węzła. Jeśli ten kierunek nie jest istotny, to wskaźnik może zostać pominięty (wersja uproszczona).

Drzewo dowolne może posiadać węzły o dowolnej liczbie synów. Jeśli liczba możliwych węzłów potomnych nie jest duża, to do reprezentacji takiego drzewa można wykorzystać metodę z drzewa binarnego, zwiększając odpowiednio liczbę wskaźników. Na przykład dla drzew czwórkowych (ang. quadtree) możemy zaimplementować następującą strukturę danych:

type
  PQuadTreeNode = ^QuadTreeNode;
  QuadTreeNode  = record
    up   : PQuadTreeNode;
    ne   : PQuadTreeNode;
    nw   : PQuadTreeNode;
    se   : PQuadTreeNode;
    sw   : PQuadTreeNode;
    Data: typ_danych;
  end;

struct QuadTreeNode
{
  QuadTreeNode * up;
  QuadTreeNode * ne;
  QuadTreeNode * nw;
  QuadTreeNode * se;
  QuadTreeNode * sw;
  typ_danych data;
};

Type QuadTreeNode
  up As QuadTreeNode Ptr
  ne As QuadTreeNode Ptr
  nw As QuadTreeNode Ptr
  se As QuadTreeNode Ptr
  sw As QuadTreeNode Ptr
  data As typ_danych
End Type

class quad_tree_node:


    def __init__(self, v):
        self.up = None
        self.ne = None
        self.nw = None
        self.se = None
        self.sw = None
        self.data = v

Gdzie:

up – wskazuje ojca danego węzła. Dla korzenia pole to zawiera wskazanie puste
ne – wskazuje syna północnowschodniego
nw – wskazuje syna północnozachodniego
se – wskazuje syna południowowschodniego
sw – wskazuje syna południowozachodniego
data – dane dowolnego typu przechowywane przez węzeł

Gdy liczba synów jest duża, to rezerwowanie w każdym węźle pól na wskaźniki przestaje być efektywne. Zamiast prostych pól możemy umieścić w każdym węźle tablicę dynamiczną o wymaganym rozmiarze, której każdy element jest wskaźnikiem do syna danego węzła. Do obsługi takiej struktury będzie potrzebna jeszcze informacja o liczbie elementów w tablicy. Dodatkowo musimy pamiętać o zwolnieniu tablic dynamicznych, gdy drzewo jest usuwane z pamięci.

type
  PAnyTreeNode = ^AnyTreeNode;
  TAnyTreeNode = array of PAnyTreeNode;
  AnyTreeNode = record
    up    : PAnyTreeNode;
    child : TAnyTreeNode;
    n     : Integer;
    Data: typ_danych;
  end;

struct AnyTreeNode
{
  AnyTreeNode * up;
  AnyTreeNode * child;
  int n;
  typ_danych data;
};

Type AnyTreeNode
  up As AnyTreeNode Ptr
  child As AnyTreeNode Ptr
  n As Integer
  data As typ_danych
End Type

class any_tree_node:


    def __init__(self, n, v):
        self.up = None
        self.child = [None]*n
        self.n = n
        self.data = v

Gdzie:

up    – wskazuje ojca danego węzła.
        Dla korzenia pole to zawiera wskazanie puste
child – wskazuje tablicę zawierającą wskazania do węzłów potomnych
n     – określa liczbę synów węzła
data  – dane dowolnego typu przechowywane przez węzeł

Alternatywnym rozwiązaniem jest zastosowanie listy jednokierunkowej, której elementy przechowują wskazania synów danego węzła. Wymaga to dołączenia do programu metod obsługi takiej listy, a najlepiej zastosowanie odpowiedniego obiektu.

type
  PAnyTreeNode = ^AnyTreeNode;
  PSLel = ^SLel;
  SLel =  record
    next : PSLel;
    node : PAnyTreeNode;
  end;

  AnyTreeNode = record
    up    : PAnyTreeNode;
    child : PSLel;
    Data: typ_danych;
  end;

typedef struct AnyTreeNode PAnyTreeNode;

struct SLel
{
  SLel * next;
  PAnyTreeNode * node;
};

struct AnyTreeNode
{
  AnyTreeNode * up;
  SLel * child;
  typ_danych data;
};

Type PAnyTreeNode As AnyTreeNode

Type SLel
  next As SLel Ptr
  node As PAnyTreeNode Ptr
End Type

Type AnyTreeNode
  up As AnyTreeNode Ptr
  child As SLel Ptr
  data As typ_danych
End Type

class SLel:


    def __init__(self):
        self.next = None
        self.node = None


class AnyTreeNode:


    def __init__(self, v):
        self.up    = None
        self.child = None
        self.data  = v

Zwróć uwagę, że w powyższym rozwiązaniu występują tzw. odwołania krzyżowe. Polegają one na tym, iż element jednej struktury odwołuje się do innej struktury, która z kolei odwołuje się do tej pierwszej. Elementy listy zawierają wskazania węzłów drzewa w polu node. Z kolei węzły drzewa w polu child wskazują listę. Obie struktury odwołują się do siebie nawzajem. Konieczne jest utworzenie pomocniczego typu danych PAnyTreeNode i użycie go w definicji listy. Nie można tutaj zastosować typu AnyTreeNode, ponieważ nie jest on w tym miejscu jeszcze zdefiniowany. Natomiast typ pomocniczy PAnyTreeNode informuje kompilator, że właściwa definicja zostanie podane później w programie.

Ostatnia metoda reprezentacji dowolnych drzew wykorzystuje drzewo binarne w pewien szczególny sposób. Zasada jest następująca:

Drzewo dowolne	Drzewo binarne	Opis operacji
	?	Konstruujemy drzewo binarne.
		Korzeń drzewa dowolnego przechodzi w korzeń drzewa binarnego.
		Lewy syn węzła A w drzewie dowolnym staje się lewym synem węzła A w drzewie binarnym.
		Syn C węzła A staje się "prawym synem" węzła B w drzewie binarnym. Jednakże tutaj prawi synowie są interpretowani jako rodzeństwo tego samego ojca, czyli węzła A.
		Syn D węzła A staje się "prawym synem" węzła C, czyli jego bratem. Zwróć uwagę, że bracia tworzą w ten sposób listę jednokierunkową za pomocą prawych dowiązań.
		Syn E węzła B w drzewie dowolnym staje się lewym synem węzła B w drzewie binarnym. Zwróć uwagę, że węzeł B wyczerpał już dostępne dla niego krawędzie wyjściowe, których może posiadać co najwyżej dwie.
		Węzły F i G dołączamy kolejno jako prawych braci węzła E. Wszystkie trzy worzą listę jednokierunkową.
		Węzeł H dołączamy jako lewego syna węzła C.
		Węzeł I dołączamy jako lewego syna węzła D.
		Węzeł J dołączamy jako prawego brata węzła I. Drzewo binarne zostało utworzone.

→

Podana transformacja pozwala przedstawić dowolne drzewo jako drzewo binarne. Zmianie ulega tutaj interpretacja krawędzi:

Wynika stąd prosty wniosek – skoro każde drzewo da się sprowadzić do drzewa binarnego, to wystarczy opracować dobre metody przetwarzania drzew binarnych, aby móc przetwarzać dowolne drzewa. Dlatego właśnie drzewa binarne są tak ważne w informatyce.