|
arbres binaires peuvent former les blocs de construction des algorithmes de recherche et de tri efficaces et de ce fait avoir une large application dans l'informatique . Comme Pascal a un support pour les dossiers et types pointeur , vous pouvez élégamment mettre en œuvre les arbres binaires en elle. Utilisez votre programme Pascal comme la base d'une file d'attente prioritaire de tas binaire ou le modifier pour supporter tout type de données comparables. Instructions
1 ouvrir un nouveau fichier Pascal dans votre éditeur de texte ou IDE
2 Ajoutez la ligne suivante dans le fichier : . Programme bintree ;
3 type de la section de code suivante dans votre éditeur de définir les types de base de l'arbre binaire : TypeBinTree = ^ Node ; Node = recordi : integer; l, R : Bintree end;
4 Copiez le suivant dans l'éditeur pour construire un arbre vide : fonction MakeTree : Bintree ; beginMakeTree : = nilend ;
5 Placez le code source suivant dans votre fichier pour tester l'arbre à vide : fonction IsEmptyTree (B : Bintree ): Boolean ; beginIsEmptyTree : = (B = nil ) ; fin ;
6 inclure les lignes suivantes dans votre script pour construire un nœud enfant avec la valeur entière donnée : fonction MakeNode ( I: integer) : Bintree ; Varres : Bintree ; beginNew ( Res ) ; Res ^ I: . = I; Res ^ L: . = MakeTree ; Res ^ R : . = MakeTree ; MakeNode : = Res end;
7 Ajouter ces lignes à libérer un arbre à partir du nœud racine donnée : Procédure DeallocateTree (var B: Bintree ) ; beginif pas IsEmptyTree (B) puis beginDeallocateTree (B ^ l . ) ; DeallocateTree (B . ^ R); Dispose ( B); endend ;
8 place la section de code suivante dans votre fichier pour insérer la valeur donnée à son emplacement ordonné dans l'arbre binaire : . procédure InsertInTree ( I : integer; var B: Bintree ) ; beginif IsEmptyTree (B) thenB : . . . = MakeNode (I) else if I < B ^ je thenInsertInTree (I, B ^ L) elseInsertInTree (I, B ^ R ) end;
9 Ajoutez le code source suivant pour rechercher un arbre pour une valeur donnée : fonction FindInTree (S : integer; B: Bintree ): Boolean ; beginif IsEmptyTree (B) thenFindInTree : = Falseelse si S < , B ^ je thenFindInTree : . = FindInTree (S , B ^ L ). else if B ^ I < S thenFindInTree : = FindInTree (S , B ^ R ). autre beginFindInTree : . = Trueendend ;
10 collez la procédure suivante dans votre programme Pascal pour voir le contenu de l'arbre dans l'ordre de tri : Procédure PrintTree (B : Bintree ) ; beginif pas IsEmptyTree (B) puis beginPrintTree ( . B ^ l); writeln (B ^ . I); PrintTree (B ^ R) endend ;
11 Ajouter ces dernières lignes de votre fichier pour terminer le programme Pascal : . . beginend
|
