树数据结构（案例研究）

到目前为止，我们已经在 Prolog 中看到了逻辑编程的不同概念。现在我们将看到一个关于 Prolog 的案例研究。我们将了解如何使用 Prolog 实现树数据结构，并且我们将创建自己的运算符。那么让我们开始计划吧。

假设我们有一棵树，如下所示 -

树数据结构

我们必须使用 prolog 来实现这棵树。我们有一些操作如下 -

  • op(500，xfx，'is_parent')。

  • op(500, xfx, 'is_sibling_of').

  • op(500, xfx, 'is_at_same_level').

  • 另一个谓词，即 leaf_node(Node)

在这些运算符中，您看到一些参数为 (500, xfx, <operator_name>)。第一个参数（此处为 500）是该运算符的优先级。'xfx' 指示这是一个二元运算符，<operator_name> 是运算符的名称。

这些运算符可用于定义树数据库。我们可以按如下方式使用这些运算符 -

  • a is_parent b 或 is_parent(a, b)。所以这表明节点a是节点b的父节点。

  • X is_sibling_of Y 或 is_sibling_of(X,Y)。这表明 X 是节点 Y 的兄弟节点。因此，规则是，如果另一个节点 Z 是 X 的父节点，并且 Z 也是 Y 的父节点，并且 X 和 Y 不同，则 X 和 Y 是兄弟节点。

  • 叶节点（节点）。当一个节点没有子节点时，该节点被称为叶节点。

  • X is_at_same_level Y，或 is_at_same_level(X,Y)。这将检查 X 和 Y 是否处于同一水平。所以条件是当 X 和 Y 相同时，则返回 true，否则 W 是 X 的父级，Z 是 Y 的父级，并且 W 和 Z 处于同一级别。

如上所示，代码中定义了其他规则。因此，让我们看看该计划以获得更好的视野。

程序

/* The tree database */

:- op(500,xfx,'is_parent').

a is_parent b. c is_parent g. f is_parent l. j is_parent q.
a is_parent c. c is_parent h. f is_parent m. j is_parent r.
a is_parent d. c is_parent i. h is_parent n. j is_parent s.
b is_parent e. d is_parent j. i is_parent o. m is_parent t.
b is_parent f. e is_parent k. i is_parent p. n is_parent u.
n 
is_parent v.
/* X and Y are siblings i.e. child from the same parent */

:- op(500,xfx,'is_sibling_of').

X is_sibling_of Y :- Z is_parent X,
                     Z is_parent Y,
                     X \== Y.
leaf_node(Node) :- \+ is_parent(Node,Child). % Node grounded

/* X and Y are on the same level in the tree. */

:-op(500,xfx,'is_at_same_level').
X is_at_same_level X .
X is_at_same_level Y :- W is_parent X,
                        Z is_parent Y,
                        W is_at_same_level Z.

输出

| ?- [case_tree].
compiling D:/TP Prolog/Sample_Codes/case_tree.pl for byte code...
D:/TP Prolog/Sample_Codes/case_tree.pl:20: warning: singleton variables [Child] for leaf_node/1
D:/TP Prolog/Sample_Codes/case_tree.pl compiled, 28 lines read - 3244 bytes written, 7 ms

yes
| ?- i is_parent p.

yes
| ?- i is_parent s.

no
| ?- is_parent(i,p).

yes
| ?- e is_sibling_of f.

true ?

yes
| ?- is_sibling_of(e,g).

no
| ?- leaf_node(v).

yes
| ?- leaf_node(a).

no
| ?- is_at_same_level(l,s).

true ?

yes
| ?- l is_at_same_level v.

no
| ?-

有关树数据结构的更多信息

在这里，我们将看到对上面给定的树数据结构执行的更多操作。

让我们在这里考虑同一棵树 -

节点

我们将定义其他操作 -

  • 路径（节点）

  • 定位（节点）

当我们创建了最后一个数据库时，我们将创建一个新程序来保存这些操作，然后查阅新文件以在我们预先存在的程序上使用这些操作。

那么让我们看看这些运算符的目的是什么 -

  • path(Node) - 这将显示从根节点到给定节点的路径。为了解决这个问题，假设X是Node的父节点，然后找到path(X)，然后写入X。当到达根节点'a'时，它将停止。

  • locate(Node) - 这将从树的根部定位一个节点（Node）。在这种情况下，我们将调用路径（Node）并编写 Node.js 文件。

程序

让我们看看正在执行的程序 -

path(a).                             /* Can start at a. */
path(Node) :- Mother is_parent Node, /* Choose parent, */
              path(Mother),          /* find path and then */ 
              write(Mother),
              write(' --> ').
              
/* Locate node by finding a path from root down to the node */
locate(Node) :- path(Node),
                write(Node),
                nl.

输出

| ?- consult('case_tree_more.pl').
compiling D:/TP Prolog/Sample_Codes/case_tree_more.pl for byte code...
D:/TP Prolog/Sample_Codes/case_tree_more.pl compiled, 9 lines read - 866 bytes written, 6 ms

yes
| ?- path(n).
a --> c --> h -->

true ?

yes
| ?- path(s).
a --> d --> j -->

true ?

yes
| ?- path(w).

no
| ?- locate(n).
a --> c --> h --> n

true ?

yes
| ?- locate(s).
a --> d --> j --> s

true ?

yes
| ?- locate(w).

no
| ?-

树数据结构的进展

现在让我们在同一树数据结构上定义一些高级操作。

先进的 TDS

在这里，我们将了解如何使用 Prolog 内置谓词 setof/3 查找节点的高度，即从该节点出发的最长路径的长度。该谓词采用（模板、目标、集合）。这将 Set 绑定到满足目标 Goal 的所有 Template 实例的列表。

我们之前已经定义了树，因此我们将参考当前代码来执行这组操作，而无需再次重新定义树数据库。

我们将创建一些谓词如下 -

ht(节点，H)。这样就找到了高度。它还检查节点是否是叶子节点，如果是，则将高度 H 设置为 0，否则递归查找 Node 子节点的高度，并将其加 1。

最大值（[X|R]，M，A）。这会计算列表中的最大元素和值 M。因此，如果 M 是最大值，则返回 M，否则返回列表中大于 M 的最大元素。为了解决这个问题，如果给定列表为空，返回 M 作为最大元素，否则检查 Head 是否大于 M，如果是，则使用尾部和值 X 调用 max()，否则使用 tail 和值 M 调用 max()。

高度（N，H）。这使用 setof/3 谓词。这将使用模板 Z 的目标 ht(N,Z) 找到结果集，并将其存储到名为 Set 的列表类型变量中。现在找到Set的最大值，值为0，将结果存储到H中。

现在让我们看看正在执行的程序 -

程序

height(N,H) :- setof(Z,ht(N,Z),Set),
               max(Set,0,H).
               
ht(Node,0) :- leaf_node(Node),!.
ht(Node,H) :- Node is_parent Child,
              ht(Child,H1),
              H is H1 + 1.
max([],M,M).
max([X|R],M,A) :- (X > M -> max(R,X,A) ; max(R,M,A)).

输出

| ?- consult('case_tree_adv.pl').
compiling D:/TP Prolog/Sample_Codes/case_tree_adv.pl for byte code...
D:/TP Prolog/Sample_Codes/case_tree_adv.pl compiled, 9 lines read - 2060 bytes written, 9 ms

yes
| ?- ht(c,H).

H = 1 ? a

H = 3

H = 3

H = 2

H = 2

yes
| ?- max([1,5,3,4,2],10,Max).

Max = 10

yes
| ?- max([1,5,3,40,2],10,Max).

Max = 40

yes
| ?- setof(H, ht(c,H),Set).

Set = [1,2,3]

yes
| ?- max([1,2,3],0,H).

H = 3

yes
| ?- height(c,H).

H = 3

yes
| ?- height(a,H).

H = 4

yes
| ?-