二叉树T的叶节点中的值列表 [英] list of the values in the leaf nodes of binary tree T

问题描述

List是二叉树的叶子节点中的值的列表，我试图弄清楚如何输出.这给了我所有的节点，但是我只需要叶子.

List is the list of values in leaf nodes of a binary tree and I am trying to figure out how to output just that. This is giving me all the nodes but I need just the leaves.

lea(nil,[]).
lea(t(X,L,R),[X|L]) :-
   lea(L,L1), 
   lea(R,L2), 
   append(L1,L2,L).

运行此命令可以给我:

?- lea(t(a,t(b,t(d,nil,nil),t(e,nil,nil)),t(c,nil,t(f,t(g,nil,nil),nil))),
       List). 
List = [a, b, d, e, c, f, g]

但我需要

List = [d, e,g] 

有可能.

推荐答案

首先，我们扩展 if_/3 进行工作使用DCG:

First, we extend if_/3 to work with DCG's:

if_(C_1, Then_0, Else_0) -->                    % if_//3
   { call(C_1, Truth) },
   { functor(Truth, _, 0) },                    % safety check
   (  { Truth == true  } -> phrase(Then_0)
   ;  { Truth == false },   phrase(Else_0)
   ).

使用if_//3和 (=)/3 ，我们可以使用一个子句(而不是两个子句)处理非零树节点. ):

Using if_//3 and (=)/3 we can handle non-nil tree nodes with one clause (instead of two):

lea3(T, Ls) :-
   phrase(leaves(T), Ls).

leaves(nil) --> [].
leaves(t(X,L,R)) -->
   if_(L-R = nil-nil, [X], []),
   leaves(L),
   leaves(R).

这篇关于二叉树T的叶节点中的值列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！