Nwlapcug.com


Come implementare un albero binario utilizzando Pascal

Alberi binari possono formare i blocchi predefiniti di ricerca efficiente e algoritmi di ordinamento e per questo motivo hanno ampia applicazione in informatica. Come Pascal ha supporto per record e tipi di puntatore, è possibile implementare elegantemente alberi binari in esso. Utilizzare il programma di Pascal come base di una coda di priorità di heap binario o modificarla per supportare qualsiasi tipo di dati comparabili.

Istruzioni

1

Aprire un nuovo file di Pascal nel vostro editor di testo o IDE.

2

Aggiungere la seguente riga al file:
programma bintree;

3

Digitare la successiva sezione di codice nel tuo editor per definire i tipi di base per l'albero binario:
Tipo

BinTree = ^Node;
Node = Record
I: integer;
L, R: BinTree;
end;
4

Copiare quanto segue nell'editor per costruire una struttura vuota:
funzione MakeTree: BinTree;
iniziare

MakeTree := nil

fine;

5

Inserire il seguente codice sorgente nel file per testare l'albero vuoto:
funzione IsEmptyTree (b: BinTree): Boolean;
iniziare

IsEmptyTree := (B = nil);

fine;

6

Includere le seguenti righe nello script per costruire un nodo figlio con il valore integer specificato:
funzione MakeNode (I: integer): BinTree;
var
Res: BinTree;
iniziare
Nuovo (Res);
Res ^. Io: = I;
Res ^. L: = MakeTree;
Res ^. R: = MakeTree;
MakeNode: = Res;
fine;

7

Aggiungere queste righe per liberare un albero dal nodo radice specificata:
procedura DeallocateTree (var b: BinTree);
iniziare
Se non IsEmptyTree (B) quindi iniziare

DeallocateTree (B^.L);
DeallocateTree (B^.R);
Dispose (B);

fine
fine;

8

Inserire la successiva sezione di codice nel file per inserire il valore determinato nella sua posizione ordinata nell'albero binario.:
procedura InsertInTree (integer I:; var b: BinTree);
iniziare
Se IsEmptyTree (B) poi

B := MakeNode (I)

ElseIf io < B ^. Ho poi

InsertInTree (I, B^.L)

altro

InsertInTree (I, B^.R)

fine;

9

Aggiungere il seguente codice di origine per cercare un albero per un determinato valore:
funzione FindInTree (s: integer; B: BinTree): Boolean;
iniziare
Se IsEmptyTree (B) poi

FindInTree := False

ElseIf S < B ^. Ho poi

FindInTree := FindInTree (S, B^.L)

ElseIf B ^. Io < S quindi

FindInTree := FindInTree (S, B^.R)

altrimenti iniziare

FindInTree := True

fine
fine;

10

Incollare la procedura successiva nel vostro programma di Pascal per vedere il contenuto dell'albero in base all'ordine di:
procedura PrintTree (b: BinTree);
iniziare
Se non IsEmptyTree (B) quindi iniziare

PrintTree (B^.L);
writeln (B^.I);
PrintTree (B^.R)

fine
fine;

11

Aggiungere queste ultime righe al tuo file per finire il programma di Pascal:
iniziare
fine.