0

这是一个家庭作业问题，我已经完成了几乎其余的代码，我要做的最后一部分是创建一个插入算法。

insert(I,T1,T2) - is true if T2 is the binary tree resulting from I being 
inserted into binary tree T1.

到目前为止，我这部分的代码是......

    insert(I,T1,T2) :- bTTree(T1(X,L,_), bTTree(T2(X,L,I).
    insert(I,T1,T2) :- bTTree(T1(nil,nil,nil),bTTree(T2(I,nil,nil).
    insert(I,T1,T2) :- bTTree(T1(X,L,_),bTTree(T2(X,L,I).

我不知道我是否朝着正确的方向前进。任何帮助将不胜感激。

我完成的代码（如果需要）：

isempty(nil) :- !.
isempty(tree(nil,nil,nil)).

bTTree(tree(_,Left,Right)) :- binaryTree(Left), binaryTree(Right).

% 遍历。

%preorder -- N,左,右

preorder(tree(N,_,_),N).
preorder(tree(_,Left,_),N) :- preorder(Left,N).
preorder(tree(_,_,Right),N) :- preorder(Right,N).

%inorder -- 左、N、右。

inorder(tree(_,Left,_), N) :- inorder(Left,N).
inorder(tree(N,_,_), N).
inorder(tree(_,_,Right), N) :- inorder(Right,N).

%postorder -- 左、右、N

postorder(tree(_,Left,_),N) :- postorder(Left,N).
postorder(tree(_,_,Right),N) :- postorder(Right,N).
postorder(tree(N,_,_),N).


search(t,I) :- bTTree(t(I,_,_)).
search(t,I) :- bTTree(t(_,I,_)).
search(t,I) :- bTTree(t(_,_,I)).
search(t,I) :- bTTree(t(_,N,_)), search(N,I).
search(t,I) :- bTTree(t(_,_,N)), search(N,I).


height(t,H) :- bTTree(t(nil,nil,nil)), H is 0.
height(t,H) :- bTTree(t(N,nil,nil)), H is 1.
height(t,H) :- bTTree(t(_,Left,Right)),
               height(Left, H1),
           height(Right, H2),
               H is max(H1,H2) + 1.

insert(I,t1,t2) :- bTTree(t1(X,L,_)),    
                   bTTree(t2(X,L,I)).
insert(I,t1,t2) :- bTTree(t1(nil,nil,nil)),
                   bTTree(t2(I,nil,nil)).
insert(I,t1,t2) :- bTTree(t1(X,L,_)),
                   bTTree(t2(X,L,I)).
4

1 回答 1

0

bTTree(T1(X,L,_))是一个语法错误（除了在 SWI-Prolog 中，在启用扩展之后set_prolog_flag(allow_variable_name_as_functor, true)）。

另一个问题是 bTTree/1 错过了基本情况，它在完成递归后总是会失败。它的目的是什么？在 Prolog 中，函子通常被假定为正式声明的符号，没有必要使用像 bBBtree/1 这样的“间接”来引入像 tree/3 这样的术语。

当然，对于程序中的数据结构，您应该坚持相同的表示：现在您使用tree, or t, or t1, or t2, ...

我认为在插入之前应该解决这些问题......

于 2013-07-29T17:10:49.743 回答