在Prolog中合并两个二叉搜索树

我正在处理一个SWI-Prolog程序，我将两个二叉搜索树合并在一起，但是我收到了错误的输出。 BST T2是将来自BST T1的每个节点插入BST T的结果。在Prolog中合并两个二叉搜索树

merge(T,T1,T2).

，我现在所拥有的代码：

add_BST(T , T1 , T2). 
add_BST(t(L , T1 , R) , t(L , T2 , R), t(t(L , ROOT , RIGHT) , T1 , NT)) :- 
    T1 < T2 , add_BST(T2 , T1 , NT). 
add_BST(t(L , T1 , R) , t(L , T2 , R), t(NT1 , T1 ,t(LEFT , ROOT ,R))) :- 
    T1 > T2 , add_BST(T2 , T1 ,NT1).

输出此：

?- add_BST(t(nil , 1 , nil) , t(nil , 2 , nil) , NT). 

true; 

NT=t(t(nil,_G1601, _G1602),1,_G1598)

我希望得到的输出二进制搜索树和不知道是什么我做错了。任何帮助将不胜感激。

来源

2016-03-06 user3765848

你有一些不使用变量的情况。例如，在你的第二条规则中，应该使用什么变量“ROOT”？ –

ROOT是为了存储树的屋顶 – user3765848

我猜你试图编译这段代码时会得到警告。不要忽视它们：如果你弄清楚为什么你会得到警告，以及如何避免它们，你可以自己解决问题。 – 2016-03-06 21:01:58

从小开始。先从你已经知道：

add_BST(t(nil , 1 , nil) , t(nil , 2 , nil) , NT) :-

这是一个非常有效的一段代码，断言其与t(nil , 2 , nil)合并t(nil , 1 , nil)涉及的头。我们对这种情况了解多少？

1 < 2,

其结果应该很明显是

NT = t(t(nil , 1 , nil) , 2, nil).

试试：

?- add_BST(t(nil , 1 , nil) , t(nil , 2 , nil) , NT).

，或者

?- A=1, B=2, add_BST(t(nil , A , nil) , t(nil , B , nil) , NT).

这一个希望让我们重新编写的想法它作为

add_BST(t(nil , A , nil) , t(nil , B , nil) , NT) :- 
    A < B, 
    NT = t(t(nil , A , nil) , B, nil).

您应该能够从这里进一步推广，并涵盖更多可能的情况（如A > B等）。

来源

2016-03-07 22:32:01

@ user3765848好，这对你有帮助吗？你有什么问题吗？ –

在Prolog中合并两个二叉搜索树

回答

相关问题