Puun funktioiden esittelyt

Puuta voidaan käsitellä yleisen puun operaatioiden avulla tietämättä puun oikeaa tyyppiä. Kuitenkin usein tarvitaan puita jotka sisältävät jotakin määrätyntyyppistä tietoa. Mahdollisimman erityyppisten tilanteiden kattavuuden vuoksi tietorakennekirjastoa varten on toteutettu neljä erilaista tyypitettyä puutyyppiä : kokonaislukupuu, joka sisältää int / integer - arvoja, liukulukupuu (sisältää float / real - tyyppistä tietoa), merkkijonopuu (char* / string[ ]) ja osoitinpuu (void* / pointer - tyyppistä tietoa).

Tässä osassa on esitelty yleisen-, kokonaisluku-, liukuluku- ja merkkijonopuun funktiot. Osoitinpuusta enemmän osuudessa "Kirjaston laajentaminen". Funktioista / proseduureista esitellään aina ensiksi C-kieliset, sitten Pascal-kieliset versiot. Kaikkien funktioiden käytössä oletetaan että puu on määritelty. Mikäli parametrina annettava puu T on määrittelemätön, on aliohjelmien toiminta määrittelemätöntä, lukuunottamatta tietenkin TREE_CREATE:a joka määrittelee puun. Samoin oletetaan solmujen kohdalla.

TREE_CREATE (T, D)
TREE_RETRIEVE (T, N)
TREE_PRINT (T)
TREE_ROOT(T)
TREE_PARENT(T,N)
TREE_LEFTMOST_CHILD(T,N)
TREE_RIGHT_SIBLING(T,N)
TREE_FREE (T)
TREE_ASSIGN_ROOT(T,N)
TREE_ASSIGN_LEFTMOST_CHILD(T,ND,NS)
TREE_ASSIGN_RIGHTSIBLING(T,ND,NS)
TREE_CREATE_NODE(x)
TREE_DESTROY_NODE(T,N)
TREE_PRINT_NODE(T,N)
TREE_CONSTRUCT_RANDOM (T, count, min, max)
TREE_TYPE (T)
TREE_LESS (T, x, y)
TREE_SAME (T, x, y)
TREE_EMPTY (T)

Yleisen puun käsittely

Yleisen puun funktioita tarvitaan silloin, kun pitää käsitellä puuta, jonka tyyppiä ei vielä ohjelmaa kirjoitettaessa tiedetä. Yleistä puuta luotaessa määritellään puun tyyppi kuvaajan DESCRIPTOR avulla. Funktio TREE_TYPE(T) palauttaa puun T kuvaajan jota voidaan käyttää uutta puuta luotaessa. Kuvaaja sisältää kaiken tiedon siitä miten puun alkioita vertaillaan, käsitellään ja tulostetaan.

Int / integer - puun käsittely

Kokonaislukupuun esittelyissä käytetään kokonaislukutyyppinä tyypinmäärittelyä INT_TYPE, joka on määritelty toteutuskohtaisesti. Tämä siksi, että esimerkiksi joissakin MS/DOS-ympäristössä toimivissa kääntäjissä int on 16-bittinen luku (enintään 2^16), mutta esim. cs:n gpc:ssä 32-bittinen (enintään 2^32). INT_TREE_XXX – operaatiot voidaan lyhentää koodissa IT_XXX.

Float / real - puun käsittely

Liukulukupuun esittelyissä käytetään liukulukutyyppiä FLOAT_TYPE, samoista syistä kuin kokonaislukupuun kohdalla. FLOAT_TREE_XXX – operaatiot voidaan lyhentää koodissa FT_XXX.

Char* / string[ ] - puun käsittely

Merkkijonopuun tyyppinä on C:ssä char*, osoitin merkkijonoon. Pascalissa tyyppinä on string, jonka maksimipituus on vakio RANDOM_STR_MAX, cs:llä 16 merkkiä. CHARP_TREE_XXX – operaatiot voidaan lyhentää koodissa CT_XXX.

Funktioiden esittelyt

TREE_CREATE (T, D)
void TREE_CREATE (TREE T, DESCRIPTOR D);

void INT_TREE_CREATE(TREE T);

void FLOAT_TREE_CREATE(TREE T);

void CHARP_TREE_CREATE(TREE T);

void VOIDPTR_TREE_CREATE(TREE T);

procedure TREE_CREATE (var T:TREE; D:DESCRIPTOR);

procedure INT_TREE_CREATE (var T:TREE);

procedure FLOAT_TREE_CREATE (var T:TREE);

procedure CHARP_TREE_CREATE (var T:TREE);

procedure VOIDPTR_TREE_CREATE(var T:TREE);

Yleinen TREE_CREATE(T, D) muodostaa tyhjän puun T, ja asettaa puun kuvaajaksi kuvaajan D = {INT_DESC| FLOAT_DESC| CHARP_DESC| VOIDP_DESC}. Mikäli puu T ei ole tyhjä puu, kaikki puussa ollut tieto menetetään, ja se jää varamaan muistia turhaan. Tyypitetyt operaatiot muodostavat omaa tyyppiään olevan puun T.

Aikavaativuus : O(1)

TREE_RETRIEVE (T, N)
ELEMENT TREE_RETRIEVE (TREE T, TREE_NODE N);

INT_TYPE INT_TREE_RETRIEVE (TREE T, TREE_NODE N);

FLOAT_TYPE FLOAT_TREE_RETRIEVE (TREE T, TREE_NODE N);

CHARP_TYPE CHARP_TREE_RETRIEVE (TREE T, TREE_NODE N);

function TREE_RETRIEVE (T:TREE; N:TREE_NODE) : ELEMENT;

function INT_TREE_RETRIEVE(T:TREE; N:TREE_NODE) : INT_TYPE;

function FLOAT_TREE_RETRIEVE(T:TREE; N:TREE_NODE) : FLOAT_TYPE;

function CHARP_TREE_RETRIEVE(T:TREE; N:TREE_NODE) : CHARP_TYPE;

function VOIDPTR_TREE_RETRIEVE(T:TREE; N:TREE_NODE) : pointer;

Palauttaa puun T solmun N arvon. Yleinen puu palauttaa ELEMENT-tyypin, tyypitettyjen puiden funktiot palauttavat puun omaa tyyppiä olevan arvon. Jos solmua N ei ole puussa T, tulos on määrittelemätön.

Aikavaativuus : O(1)

TREE_PRINT_NODE (T, N)
void TREE_PRINT_NODE (TREE T, TREE_NODE N);

procedure TREE_PRINT_NODE (T:TREE; N:TREE_NODE);

Tulostaa solmun N puun T kuvaajassa määritellyllä tavalla. Solmun N ei tarvitse olla kuitenkaan puussa T.

Aikavaativuus : Yksinkertaisille tyypeille O(1)

TREE_ROOT(T)
TREE_NODE TREE_ROOT (TREE T);

TREE_NODE INT_TREE_ROOT(TREE T);

TREE_NODE FLOAT_TREE_ROOT(TREE T);

TREE_NODE CHARP_TREE_ROOT(TREE T);

TREE_NODE VOIDPTR_TREE_ROOT(TREE T);

function TREE_ROOT(T:TREE):TREE_NODE;

function INT_TREE_ROOT(T:TREE):TREE_NODE;

function FLOAT_TREE_ROOT(T:TREE):TREE_NODE;

function CHARP_TREE_ROOT(T:TREE):TREE_NODE;

function VOIDPTR_TREE_ROOT(T:TREE):TREE_NODE;

Palauttaa puun T juurisolmun. Jos puu on tyhjä puu, palauttaa TREE_NIL.

Aikavaativuus : O(1)

TREE_PARENT(T,N)
TREE_NODE TREE_PARENT (TREE T, TREE_NODE N);

TREE_NODE INT_TREE_PARENT(TREE T, TREE_NODE N);

TREE_NODE FLOAT_TREE_PARENT(TREE T, TREE_NODE N);

TREE_NODE CHARP_TREE_PARENT(TREE T, TREE_NODE N);

TREE_NODE VOIDPTR_TREE_PARENT(TREE T, TREE_NODE N);

function TREE_PARENT(T:TREE; N:TREE_NODE):TREE_NODE;

function INT_TREE_PARENT(T:TREE; N:TREE_NODE):TREE_NODE;

function FLOAT_TREE_PARENT(T:TREE; N:TREE_NODE):TREE_NODE;

function CHARP_TREE_PARENT(T:TREE; N:TREE_NODE):TREE_NODE;

function VOIDPTR_TREE_PARENT(T:TREE; N:TREE_NODE):TREE_NODE;

Palauttaa solmun N vanhemman ( isän ).

Aikavaativuus : O(1)

TREE_LEFTMOST_CHILD(T,N)

TREE_NODE TREE_LEFTMOST_CHILD (TREE T, TREE_NODE N);

TREE_NODE INT_TREE_LEFTMOST_CHILD(TREE T, TREE_NODE N);

TREE_NODE FLOAT_TREE_LEFTMOST_CHILD(TREE T, TREE_NODE N);

TREE_NODE CHARP_TREE_LEFTMOST_CHILD(TREE T, TREE_NODE N);

TREE_NODE VOIDPTR_TREE_LEFTMOST_CHILD(TREE T, TREE_NODE N);

function TREE_LEFTMOST_CHILD(T:TREE; N:TREE_NODE):TREE_NODE;

function INT_TREE_LEFTMOST_CHILD(T:TREE; N:TREE_NODE):TREE_NODE;

function FLOAT_TREE_LEFTMOST_CHILD(T:TREE; N:TREE_NODE):TREE_NODE;

function CHARP_TREE_LEFTMOST_CHILD(T:TREE; N:TREE_NODE):TREE_NODE;

function VOIDPTR_TREE_LEFTMOST_CHILD(T:TREE; N:TREE_NODE):TREE_NODE;

Palauttaa solmun N vanhimman lapsen.

Aikavaativuus : O(1)

TREE_RIGHT_SIBLING(T,N)

TREE_NODE TREE_RIGHT_SIBLING (TREE T, TREE_NODE N);

TREE_NODE INT_TREE_RIGHT_SIBLING(TREE T, TREE_NODE N);

TREE_NODE FLOAT_TREE_RIGHT_SIBLING(TREE T, TREE_NODE N);

TREE_NODE CHARP_TREE_RIGHT_SIBLING(TREE T, TREE_NODE N);

TREE_NODE VOIDPTR_TREE_RIGHT_SIBLING(TREE T, TREE_NODE N);

procedure TREE_RIGHT_SIBLING(T:TREE; N:TREE_NODE):TREE_NODE;

procedure INT_TREE_RIGHT_SIBLING(T:TREE; N:TREE_NODE):TREE_NODE;

procedure FLOAT_TREE_RIGHT_SIBLING(T:TREE; N:TREE_NODE):TREE_NODE;

procedure CHARP_TREE_RIGHT_SIBLING(T:TREE; N:TREE_NODE):TREE_NODE;

procedure VOIDPTR_TREE_RIGHT_SIBLING(T:TREE; N:TREE_NODE):TREE_NODE;

Palauttaa solmun N seuraavaksi vanhimman sisaruksen,tai TREE_NIL jos N:llä ei ole nuorempia sisaruksia.

Aikavaativuus : O(1)

TREE_ASSIGN_ROOT(T,N)

void TREE_ASSIGN_ROOT (TREE T, TREE_NODE N);

void INT_TREE_ASSIGN_ROOT (TREE T, TREE_NODE N);

void FLOAT_TREE_ASSIGN_ROOT (TREE T, TREE_NODE N);

void CHARP_TREE_ASSIGN_ROOT (TREE T, TREE_NODE N);

procedure TREE_ASSIGN_ROOT(T:TREE; N:TREE_NODE);

procedure INT_TREE_ASSIGN_ROOT(T:TREE; N:TREE_NODE);

procedure FLOAT_TREE_ASSIGN_ROOT(T:TREE; N:TREE_NODE);

procedure CHARP_TREE_ASSIGN_ROOT(T:TREE; N:TREE_NODE);

procedure VOIDPTR_TREE_ASSIGN_ROOT(T:TREE; N:TREE_NODE);

Asettaa puun T juurisolmuksi N:n. N:n tyypiksi tulee puun T tyyppi.

Aikavaativuus : O(1)

TREE_ASSIGN_LEFTMOST_CHILD(T,ND,NS)

void TREE_ASSIGN_LEFTMOST_CHILD (TREE T, TREE_NODE ND, TREE_NODE NS);

void INT_TREE_ASSIGN_LEFTMOST_CHILD (TREE T, TREE_NODE ND, TREE_NODE NS);

void FLOAT_TREE_ASSIGN_LEFTMOST_CHILD (TREE T, TREE_NODE ND, TREE_NODE NS);

void CHARP_TREE_ASSIGN_LEFTMOST_CHILD (TREE T, TREE_NODE ND, TREE_NODE NS);

void VOIDPTR_TREE_ASSIGN_LEFTMOST_CHILD (TREE T, TREE_NODE ND, TREE_NODE NS);

procedure TREE_ASSIGN_LEFTMOST_CHILD (T:TREE;ND:TREE_NODE;NS:TREE_NODE);

procedure INT_TREE_ASSIGN_LEFTMOST_CHILD (T:TREE;ND:TREE_NODE;NS: TREE_NODE);

procedure FLOAT_TREE_ASSIGN_LEFTMOST_CHILD (T:TREE;ND:TREE_NODE;NS: TREE_NODE);

procedure CHARP_TREE_ASSIGN_LEFTMOST_CHILD (T:TREE;ND:TREE_NODE;NS: TREE_NODE);

procedure VOIDPTR_TREE_ASSIGN_LEFTMOST_CHILD (T:TREE;ND:TREE_NODE;NS: TREE_NODE);

Asettaa solmun ND (node-destination) vanhimmaksi lapseksi solmun NS (node-source). Solmu NS muutetaan samantyyppiseksi kuin solmu ND .

Aikavaativuus : O(1)

TREE_ASSIGN_RIGHT_SIBLING(T,ND,NS)

void TREE_ASSIGN_RIGHT_SIBLING (TREE T, TREE_NODE ND, TREE_NODE NS);

void INT_TREE_ASSIGN_RIGHT_SIBLING (TREE T, TREE_NODE ND, TREE_NODE NS);

void FLOAT_TREE_ASSIGN_RIGHT_SIBLING (TREE T, TREE_NODE ND, TREE_NODE NS);

void CHARP_TREE_ASSIGN_RIGHT_SIBLING (TREE T, TREE_NODE ND, TREE_NODE NS);

void VOIDPTR_TREE_ASSIGN_RIGHT_SIBLING (TREE T, TREE_NODE ND, TREE_NODE NS);

procedure TREE_ASSIGN_RIGHT_SIBLING (T:TREE;ND:TREE_NODE;NS:TREE_NODE);

procedure INT_TREE_ASSIGN_RIGHT_SIBLING (T:TREE;ND: TREE_NODE;NS: TREE_NODE);

procedure FLOAT_TREE_ASSIGN_RIGHT_SIBLING (T:TREE;ND: TREE_NODE;NS: TREE_NODE);

procedure CHARP_TREE_ASSIGN_RIGHT_SIBLING (T:TREE;ND: TREE_NODE;NS: TREE_NODE);

procedure VOIDPTR_TREE_ASSIGN_RIGHT_SIBLING (T:TREE;ND: TREE_NODE;NS: TREE_NODE);

Asettaa solmun ND seuraavaksi (nuoremmaksi) sisarukseksi solmun NS. NS:n tyypiksi tulee solmun ND tyyppi.

Aikavaativuus : O(1)

TREE_CREATE_NODE(x)

TREE_NODE TREE_CREATE_NODE (ELEMENT x);

TREE_NODE INT_TREE_CREATE_NODE(INT_TYPE x);

TREE_NODE FLOAT_TREE_CREATE_NODE(FLOAT_TYPE x);

TREE_NODE CHARP_TREE_CREATE_NODE(char* x);

TREE_NODE VOIDPTR_TREE_CREATE_NODE(void* x);

function TREE_CREATE_NODE(x:ELEMENT):TREE_NODE;

function INT_TREE_CREATE_NODE(x:INT_TYPE):TREE_NODE;

function FLOAT_TREE_CREATE_NODE(x:FLOAT_TYPE):TREE_NODE;

function CHARP_TREE_CREATE_NODE(x:CHARP_TYPE):TREE_NODE;

function VOIDPTR_TREE_CREATE_NODE(x:pointer):TREE_NODE;

Luo uuden solmun, asettaa sen dataksi x ja palauttaa luodun solmun. Solmun tyyppi määrätään vasta puuhun vietäessä.

Aikavaativuus : O(1)

TREE_DESTROY_NODE (T,N)
void TREE_DESTROY_NODE (TREE T, TREE_NODE N);

void INT_TREE_DESTROY_NODE(TREE T, TREE_NODE N);

void FLOAT_TREE_DESTROY_NODE(TREE T, TREE_NODE N);

void CHARP_TREE_DESTROY_NODE(TREE T, TREE_NODE N);

void VOIDPTR_TREE_DESTROY_NODE(TREE T, TREE_NODE N);

procedure TREE_DESTROY_NODE(T:TREE; N:TREE_NODE);

procedure INT_TREE_DESTROY_NODE(T:TREE; N:TREE_NODE);

procedure FLOAT_TREE_DESTROY_NODE(T:TREE; N:TREE_NODE);

procedure CHARP_TREE_DESTROY_NODE(T:TREE; N:TREE_NODE);

procedure VOIDPTR_TREE_DESTROY_NODE(T:TREE; N:TREE_NODE);

Poistaa puusta T solmun N. Solmun poistamisen jälkeen solmun N, kaikkien sen sisarusten ja kaikkien sen jälkeläisten tiedot vanhentuvat.

Aikavaativuus : O(1)

TREE_FREE (T)
void TREE_FREE(TREE T);

void INT_TREE_FREE(TREE T);

void FLOAT_TREE_FREE(TREE T);

void CHARP_TREE_FREE(TREE T);

void VOIDPTR_TREE_FREE(TREE T);

procedure TREE_FREE (var T:TREE);

procedure INT_TREE_FREE (var T:TREE);

procedure FLOAT_TREE_FREE (var T:TREE);

procedure CHARP_TREE_FREE (var T:TREE);

procedure VOIDPTR_TREE_FREE (var T:TREE);

Vapauttaa kaiken puun T varaaman tilan ja asettaa puun T määrittelemättömäksi puuksi. On hyvä ohjelmointitapa vapauttaa ohjelman lopussa ohjelman varaama tila.Jos void*- tai char*-puussa on talletettuna tietoa jolle on varattu muistia eikä siihen enää päästä käsiksi puun tuhoamisen jälkeen, täytyy ennen TREE_FREE:n kutsumista huolehtia varatun muistitilan vapauttamisesta.

Aikavaativuus : O(n)

Seuraavat aliohjelmat eivät ole välttämättömiä puun käytön kannalta, mutta helpottavat ohjelmien tekemistä ja testaamista:

TREE_TYPE (T)
DESCRIPTOR TREE_TYPE (TREE T);

function TREE_TYPE (T:TREE) : DESCRIPTOR;

Palauttaa puun T kuvaajan. Käytetään lähinnä tilanteessa, jossa ei ohjelmoitaessa tiedetä minkätyyppinen puu joudutaan luomaan. Uusi puu U, joka on samaa tyyppiä kuin puu T, luodaan komennolla TREE_CREATE(U, TREE_TYPE(T));.

Aikavaativuus : O(1)

TREE_LESS (T, x, y)

TREE_SAME (T, x, y)
int TREE_LESS (TREE T, ELEMENT x, ELEMENT y);

int TREE_SAME (TREE T, ELEMENT x, ELEMENT y);

function TREE_LESS (T:TREE; x,y:ELEMENT) : boolean;

function TREE_SAME (T:TREE; x,y:ELEMENT) : boolean;

Palauttavat tiedon siitä ovatko puun T kuvaajan määräämää tyyppiä olevat elementit x ja y samoja (SAME), tai onko x järjestyksessä ennen y:tä (LESS). Elementtien x ja y pitää olla samaa tyyppiä kuin puun T alkiot (muttei niiden ole pakko olla puun T alkioita). Jos x=y, niin TREE_SAME palauttaa siis TRUE (!=0), ja jos x<y niin TREE_LESS palauttaa TRUE (!=0). Merkkijonopuussa vertaillaan merkkijonojen välistä aakkosjärjestystä.

Aikavaativuus : yksinkertaisille tyypeille O(1)

TREE_EMPTY (T)
int TREE_EMPTY (TREE T);

int INT_TREE_EMPTY(TREE T);

int FLOAT_TREE_EMPTY(TREE T);

int CHARP_TREE_EMPTY(TREE T);

int VOIDPTR_TREE_EMPTY(TREE T);

function TREE_EMPTY (T:TREE) : boolean;

function INT_TREE_EMPTY (T:TREE) : boolean;

function FLOAT_TREE_EMPTY (T:TREE) : boolean;

function CHARP_TREE_EMPTY (T:TREE) : boolean;

function VOIDPTR_TREE_EMPTY (T:TREE) : boolean;

Palauttaa tiedon siitä onko puu T tyhjä puu. C-kielessä palautusarvo on siis !=0, jos puu on tyhjä, ja 0 mikäli puu ei ole tyhjä. Pascalissa funktio palauttaa TRUE jos puu on tyhjä ja FALSE, jos puu ei ole tyhjä.

Aikavaativuus : O(1)