Estruturas de suporte à implementação de BSTs: Difference between revisions
From Wiki**3
No edit summary |
m (Estruturas de suporte à implementação de BSTs moved to Estruturas de suporte à implementação de BSTs) |
||
(One intermediate revision by the same user not shown) | |||
Line 1: | Line 1: | ||
== Estrutura com base em nós ligados == | == 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é). | 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é). | ||
Line 8: | Line 20: | ||
size_t N; | size_t N; | ||
link l, r; | 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 (<code>p</code>). Como anteriormente, pode ser incluÃdo um contador. | |||
typedef struct node *link; | |||
struct node { | |||
Item i; | |||
link p, l, r; | |||
}; | }; |
Latest revision as of 09:10, 12 November 2008
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; };