Estruturas de suporte à implementação de BSTs

Estrutura com base em nós ligados

Simples

Cada nó dispõe, além de um item, de duas ligações para os filhos.

 typedef struct node *link;
 struct node {
   Item i;
   link l, r;
 };

Com contador

Cada nó dispõe, além de um item, de um contador e de duas ligações para os filhos. A contagem refere-se ao número de nós da árvore abaixo do nó actual (inclusivé).

 typedef struct node *link;
 struct node {
   Item item;
   size_t N;
   link l, r;
 };

Duplamente ligada

Cada nó dispõe, além de um item, de duas ligações para os filhos e um para o nó pai (p). Como anteriormente, pode ser incluído um contador.

 typedef struct node *link;
 struct node {
   Item i;
   link p, l, r;
 };