/* insert_leaf(X, Tree, Tree1) is true if Tree1 is the result of inserting */ /* the element X as a leaf in the ordered binary tree Tree. If the */ /* element X is already in the tree, the tree is unchanged. */ insert_leaf(X, void, tree(X,void,void)):-!. insert_leaf(X, Tree, Tree):- Tree=tree(X,_,_), !. insert_leaf(X, tree(Y,L,R), tree(Y,L1,R)):- X < Y, !, insert_leaf(X, L, L1). insert_leaf(X, tree(Y,L,R), tree(Y,L,R1)):- insert_leaf(X, R, R1). /* delete_node(X, Tree, Tree1) is true if Tree1 is the result of deleting */ /* the element X from the ordered binary tree Tree. */ delete_node(X, tree(X,L,void), L):-!. delete_node(X, tree(X,L,R), Tree):-!, left_rest(R, Y, R1), Tree=tree(Y,L,R1). delete_node(X, tree(Y,L,R), tree(Y,L1,R)):- X < Y, !, delete_node(X, L, L1). delete_node(X, tree(Y,L,R), tree(Y,L,R1)):- delete_node(X, R, R1). /* left_rest(Tree, Left, Rest) is true if Left is the leftmost element in */ /* the binary tree Tree, and Rest is the rest of the tree. */ left_rest(tree(X,void,R), X, R):-!. left_rest(tree(X,L,R), Y, tree(X,L1,R)):-left_rest(L, Y, L1). /* pre_order(Tree, L) is true if L is a pre-order traversal of the binary */ /* tree Tree. */ pre_order(T, L):-pre_order_dl(T, L, []). pre_order_dl(tree(X,L,R), [X|Xs], Zs):- pre_order_dl(R, Ys, Zs), pre_order_dl(L, Xs, Ys). pre_order_dl(void, Xs, Xs). /* in_order(Tree, L) is true if L is an in-order traversal of the binary */ /* tree Tree. */ in_order(T, L):-in_order_dl(T, L, []). in_order_dl(tree(X,L,R), Xs, Zs):- in_order_dl(R, Ys, Zs), in_order_dl(L, Xs, [X|Ys]). in_order_dl(void, Xs, Xs). /* post_order(Tree, L) is true if L is a post-order traversal of the */ /* binary tree Tree. */ post_order(T, L):-post_order_dl(T, L, []). post_order_dl(tree(X,L,R), Xs, Zs):- post_order_dl(R, Ys, [X|Zs]), post_order_dl(L, Xs, Ys). post_order_dl(void, Xs, Xs). /* breadth_order(BinaryTree, List) is true if List is the level-by-level */ /* traversal of BinaryTree. */ /* This procedure uses a queue implemented as a difference list with a */ /* counter. It can be used backwards, that is, it can be used to */ /* enumerate, by backtracking, every BinaryTree for which List is the */ /* level-by-level traversal. For a list of n elements, the number of */ /* binary trees is the n-th Catalan number - see "Data Structures and */ /* Program Design in C" by Kruse, Leung and Tondo. */ breadth_order(Tree, List):- breadth_order_1(s(zero), [Tree|Trees], Trees, List). breadth_order_1(zero, Trees, Trees, []). breadth_order_1(s(N), [void|Trees0], Trees, List):- breadth_order_1(N, Trees0, Trees, List). breadth_order_1(s(N), [tree(X,L,R)|Trees0], [L,R|Trees], [X|List]):- breadth_order_1(s(s(N)), Trees0, Trees, List).