Implementação do ADT Tabela de Símbolos (BST)

Dependências da implementação do ADT tabela de símbolos baseado em BSTs. A árvore está ancorada em head e as folhas são nós vazios (representados por z): assim, os algoritmos apenas manipulam nós internos da árvore.

 #include <stdlib.h>
 #include "Item.h"
 
 typedef struct STnode* link;
 struct STnode { Item item; link l, r; int N };
 static link head, z;

Criação de um Novo Elemento

Esta função não faz parte da interface do ADT. A ideia subjacente é isolar procedimentos repetitivos da criação de novas entradas da BST.

 link NEW(Item item, link l, link r, int N) {
   link x  = (link)malloc(sizeof *x); 
   x->item = item;
   x->l    = l;
   x->r    = r;
   x->N    = N;
   return x;
 }

Funções Básicas do ADT

 void STinit()  { head = z = NEW(NULLitem, 0, 0, 0); }
 int  STcount() { return head->N; }

Outras Funções do ADT

• STinsert -
• STsearch -
• STdelete -
• STselect - selecção da k-ésima menor chave
• STsort -