ANSI C 3

6 STRUKTURY

Żaden węzeł nie może mieć więcej niż dwóch potomków; może natomiast mieć jednego lub nie mieć żadnego.

Węzły w drzewie są uporządkowane tak, aby dla każdego węzła jego lewe poddrze-wo zawierało słowa leksykograficznie mniejsze od słowa w tym węźle, a prawe pod-drzewo - słowa większe. Prezentujemy drzewo binarne zdania „Nadszedł czas, aby wszyscy dobrzy ludzie przyszli z pomocą swojej partii’" tak, jak je budowano wstawiając po kolei każde napotkane słowo.

Nadszedł

/\ /\ aby dobrzy    przyszli z

\ /\

ludzie pomocą swojej

/

partii

Aby sprawdzić, czy nowo wczytane słowo znajduje się już w drzewie, porównujemy je ze słowem zapisanym w korzeniu drzewa. Jeżeli jest tym właśnie słowem, to mamy odpowiedź twierdzącą. Jeżeli nowe słowo jest mniejsze od słowa zawartego w węźle, to poszukiwanie kontynuujemy od lewego potomka; w przeciwnym przypadku badamy prawego potomka. Jeśli nie ma potomka po właściwej stronie znaczy to, że nowe słowo nie występuje w drzewie i że brakujący potomek jest właściwym miejscem dla tego słowa. Proces ten jest rekurencyjnie zstępujący (dziedziczny), gdyż poszukiwanie rozpoczęte w dowolnym węźle korzysta z poszukiwania rozpoczynającego się od jednego z jego potomków. Wobec tego zastosowanie rekurencyjnych procedur wstawiających i wypisujących słowa będzie najbardziej naturalne.

Wracając do opisu węzła, jego odpowiednią reprezentacją jest struktura o czterech składowych;    -V

struct tnode {    /* węzeł drzewa */

char *word;    /* wskaźnik do tekstu słowa */    ~~~

int count;    /* licznik wystąpień */

struct tnode *left; /* lewy potomek */ struct tnode *right; /* prawy potomek */

Taka rekurencyjna deklaracja węzła może wygląda ryzykownie, lecz jest zupełnie po* prawna. Nie dopuszcza się, aby struktura zawierała w sobie swoje własne wcielenie, ak

6.5 STRUKTURY ODWOŁUJĄCE SIĘ DO SAMYCH SIEBIE struct tnode *left;

deklaruje left jako wskaźnik do struktury tnode, a nie jako samą strukturę.

Nieraz bywa potrzebna inna odmiana struktur odwołujących się do siebie samych: dwie struktury, które odwołują się do siebie nawzajem. Osiągnąć to można w następujący sposób:

struct t {

• • •

struct s *p; /* p wskazuje na strukturę s */

K

struct s {

• • •

struct t *q■' I* q wskazuje na strukturę t */

};

Cały program jest zaskakująco mały dzięki garści wcześniej napisanych funkcji, na przykład getword. Funkcja main czyta kolejne słowa za pomocą getword i umieszcza je w drzewie za pomocą funkcji addtree.

#include <stdio.h>

#include <ctype.h>

#include <string.h>

#define MAXWORD 100

struct tnode *addtree(struct tnode *, char *);

void treeprint(struct tnode *);

int getword(char *, int);

I* zliczanie wystąpień słów */ main()

{

struct tnode +root; /* wskaźnik do korzenia drzewa */ char word[MAXWORD];

root = NULL;

while (getword(word, MAXWORD) != EOF) if (isalpha(wordK)]))

root = addtree(root, word); treeprint(root); return 0;

}

189