--- pl:prolog:pllib:insert_into_tree_2 [2019/06/27 15:50]
+++ pl:prolog:pllib:insert_into_tree_2 [2019/06/27 15:50] (aktualna)
@@ Linia 1: / Linia 1: @@
+====== Insert into tree 2 ======
+{{tag>trees}}
+===== Description =====
+Insertion into the binary dictionary at any level of the tree.
+**Source**:  PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.
+===== Download =====
+Program source code: {{insert_into_tree_2.pl}}
+===== Listing =====
+<code prolog>
+% Figure 9.15  Insertion into the binary dictionary at any level of the tree.
+% add( Tree, X, NewTree):
+%   inserting X at any level of binary dictionary Tree gives NewTree
+add( Tree, X, NewTree)  :-
+   addroot( Tree, X, NewTree).               % Add X as new root
+add( t( L, Y, R), X, t( L1, Y, R))  :-       % Insert X into left subtree
+   gt( Y, X),
+   add( L, X, L1).
+add( t( L, Y, R), X, t( L, Y, R1))  :-       % Insert X into right subtree
+   gt( X, Y),
+   add( R, X, R1).
+% addroot( Tree, X, NewTree):
+%   inserting X as the root into Tree gives NewTree
+addroot( nil, X, t( nil, X, nil)).           % Insert into empty tree
+addroot( t( L, Y, R), X, t( L1, X, t( L2, Y, R)))  :-
+   gt( Y, X),
+   addroot( L, X, t( L1, X, L2)).
+addroot( t( L, Y, R), X, t( t( L, Y, R1), X, R2))  :-
+   gt( X, Y),
+   addroot( R, X, t( R1, X, R2)).
+gt(X,Root):-X>Root.
+</code>
+===== Comments =====

pl/prolog/pllib/insert_into_tree_2.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)

AIwiki

Menu