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;
4
Node = Record
I: integer;
L, R: BinTree;
end;
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.