二分木の問題です。拙作のページ「二分探索木」と重複する問題がありますが、あしからずご了承くださいませ。
二分木の「節 (node) 」を複合項で次のように表すことにします。
node(Data, Left, Rigth)
Data にデータが入り、Left には左の子、Right には右の子が入ります。簡単な二分木とその複合項を図に表すと、次のようになります。
12
／ ＼ => node(12, node(11, nil, nil), node(13, nil, nil))
11 13
図 : 二分木
nil は終端 (空の木) を表します。なお、今回の問題は Data を数値とします。
Tree が二分探索木か判定する述語 istree(Tree) を定義してください。
?- istree(node(5, node(4, nil, nil), node(6, nil, nil))). true ; false. ?- istree(node(5, node(4, nil, nil), node(3, nil, nil))). false.
二分探索木 Tree から数値 N を探す述語 search_tree(N, Tree) を定義してください。
?- search_tree(5, node(5, node(4, nil, nil), node(6, nil, nil))). true ; false. ?- search_tree(1, node(5, node(4, nil, nil), node(6, nil, nil))). false.
二分探索木 Tree に数値 N を挿入する述語 insert_tree(N, Tree, NewTree) を定義してください。
?- insert_tree(1, node(5, node(4, nil, nil), node(6, nil, nil)), X). X = node(5, node(4, node(1, nil, nil), nil), node(6, nil, nil)) ; false. ?- insert_tree(9, node(5, node(4, nil, nil), node(6, nil, nil)), X). X = node(5, node(4, nil, nil), node(6, nil, node(9, nil, nil))) ; false.
二分探索木 Tree から最大値 Max を探す述語 search_max(Tree, Max) を定義してください。
?- search_max(node(5, node(4, nil, nil), node(6, nil, nil)), X). X = 6 ; false.
二分探索木 Tree から最小値 Min を探す述語 search_min(Tree, Min) を定義してください。
?- search_min(node(5, node(4, nil, nil), node(6, nil, nil)), X). X = 4 ; false.
二分探索木 Tree から最大値を削除する述語 delete_max(Tree, Newtree) を定義してください。
?- delete_max(node(5, node(4, nil, nil), node(6, nil, nil)), X). X = 6 ; false.
二分探索木 Tree から最小値を削除する述語 delete_min(Tree, Newtree) を定義してください。
?- delete_min(node(5, node(4, nil, nil), node(6, nil, nil)), X). X = 4 ; false.
二分探索木 Tree から数値 N を削除する述語 delete_tree(N, Tree, NewTree) を定義してください。
?- delete_tree(5, node(5, node(4, nil, nil), node(6, nil, nil)), X). X = node(6, node(4, nil, nil), nil) ; false. ?- delete_tree(4, node(5, node(4, nil, nil), node(6, nil, nil)), X). X = node(5, nil, node(6, nil, nil)) ; false. ?- delete_tree(6, node(5, node(4, nil, nil), node(6, nil, nil)), X). X = node(5, node(4, nil, nil), nil). ?- delete_tree(0, node(5, node(4, nil, nil), node(6, nil, nil)), X). false.
二分木 Tree を「通りがけ (in-order) 」で巡回する述語 traverse_tree(X, Tree) を定義してください。
?- traverse_tree(X, node(5, node(4, nil, nil), node(6, nil, nil))). X = 4 ; X = 5 ; X = 6 ; false.
二分探索木 Tree を「行きがけ (pre-order) 」で巡回する述語 pre_traverse_tree(X, Tree) を定義してください。
?- pre_traverse_tree(X, node(5, node(4, nil, nil), node(6, nil, nil))). X = 5 ; X = 4 ; X = 6 ; false.
二分探索木 Tree を「帰りがけ (post-order) 」で巡回する述語 post_traverse_tree(X, Tree) を定義してください。
?- post_traverse_tree(X, node(5, node(4, nil, nil), node(6, nil, nil))). X = 4 ; X = 6 ; X = 5.
リスト Ls を二分探索木 Tree に変換する述語 tree_of_list(Ls, Tree) を定義してください。
?- tree_of_list([3,4,1,2,5], X). X = node(3, node(1, nil, node(2, nil, nil)), node(4, nil, node(5, nil, nil))) ; false.
二分探索木 Tree をリスト Ls に変換する述語 list_of_tree(Tree, Ls) を定義してください。
?- list_of_tree(node(5, node(4, nil, nil), node(6, nil, nil)), X). X = [4, 5, 6].
二分木の高さ X を求める述語 height_tree(Tree, X) を定義してください。
?- height_tree(node(5, node(4, nil, nil), node(6, nil, nil)), X). X = 2.
二分木の節の個数を求める述語 count_node(Tree, X) を定義してください。
?- count_node(node(5, node(4, nil, nil), node(6, nil, nil)), X). X = 3.
二分木の要素の合計値を求める述語 sum_tree(Tree, X) を定義してください。
?- sum_tree(node(5, node(4, nil, nil), node(6, nil, nil)), X). X = 15.
Prolog の場合、二分木の終端 (nil) を「自由変数」で表すことができます。この方法を使って、問題 51 から問題 66 のプログラムを書き直してください。
二分木が無順序木であれば、istree はとても簡単に定義できます。次のリストを見てください。
リスト : 二分木の判定 (無順序木の場合) istree(nil). istree(node(_, Left, Right)) :- istree(Left), istree(Right).
最初の規則は、空の木 (nil) は二分木であることを表しています。空の木でなければ、次の規則で istree を再帰呼び出しして、左部分木 Left が二分木であることと、右部分木 Right が二分木であることを確認します。
上記プログラムは無順序木の判定なので、下記例のように二分探索木の条件を満たしていない二分木でも成功します。
?- istree(node(5, node(3, nil, node(7, nil, nil)), node(6, nil, nil))). Yes
二分探索木は順序木なので、データの大小関係をチェックします。次のリストを見てください。
リスト : 二分探索木の判定
% 左部分木のチェック
check_left(X, node(Y, _, _)) :- Y < X.
check_left(_, nil).
% 右部分木のチェック
check_right(X, node(Y, _, _)) :- X < Y. % 修正(2014/08/17)
check_right(_, nil).
% 二分探索木か
istree(nil).
istree(node(X, Left, Right)) :-
check_left(X, Left),
istree(Left),
check_right(X, Right),
istree(Right).
check_left は節のデータ X と左の子のデータ Y を比較して、条件 Y < X を満たしているか、または左の子が nil かチェックします。check_right は節のデータ X と右の子のデータ Y を比較して、条件 X < Y を満たしているか、または右の子が nil かチェックします。
ところが、このプログラムは節 node(X, Left, Right) の X と Left のデータ、X と Right のデータをチェックしているだけなので、下記例のように二分探索木の条件を満たしていない二分木でも成功してしまいます。
?- istree(node(5, node(3, nil, node(7, nil, nil)), node(6, nil, nil))). Yes
節 5 と節 3、節 5 と節 6、節 3 と節 7 は順序木の条件を満たしていますが、節 5 の左部分木にある節 7 は条件を満たしていません。そこで、二分木を通りがけ順に巡回して、節のデータが昇順に並んでいるかチェックすることにします。次のリストを見てください。
リスト : 二分探索木の判定 (修正版 2014/08/17)
check(_, nil) :- !.
check(X, Y) :- X =< Y.
istree(nil, A, A).
istree(node(X, Left, Right), A, B) :-
istree(Right, A, C),
check(X, C),
istree(Left, X, B).
istree(Node) :- istree(Node, nil, _).
istree/1 は istree/3 を呼び出します。istree/3 の第 2 引数には、今まで探索した木の最小値または nil をセットします。第 3 引数は木を探索したあとの最小値がセットされます。最初は第 2 引数に nil を渡して呼び出します。
最初に右部分木をたどります。すると、変数 C にその部分木の最小値または nil がセットされます。述語 check でこの値と X を比較して、X が小さいことを確認します。それから左部分木をたどります。このとき、X が今まで探索した木の最小値になるので、これを第 2 引数に渡して istree を呼び出します。これで、順序木を満たしているかチェックすることができます。
リスト : データの探索 search_tree(X, node(X, _, _)). search_tree(X, node(Y, Left, _)) :- X < Y, search_tree(X, Left). search_tree(X, node(Y, _, Right)) :- X > Y, search_tree(X, Right).
最初の規則がデータを見つけた場合です。次の規則で、X が Y よりも小さければ左の部分木をたどり、最後の規則で X が Y よりも大きければ右の木をたどります。二分木の定義そのままのプログラムですね。
リスト : データの挿入
insert_tree(X, nil, node(X, nil, nil)).
insert_tree(X, node(X, Left, Right), node(X, Left, Right)).
insert_tree(X, node(Y, Left, Right), node(Y, New_node, Right)) :-
X < Y, insert_tree(X, Left, New_node).
insert_tree(X, node(Y, Left, Right), node(Y, Left, New_node)) :-
X > Y, insert_tree(X, Right, New_node).
最初の規則が、空の木にデータを挿入する場合です。次の規則は同じデータが見つかった場合で、データを挿入しないように同じ木を返すだけです。3 番目の規則で、X が節の値 Y よりも小さければ、左部分木に X を挿入します。New_node がデータを挿入した部分木を表しています。これを左部分木と置き換えればいいわけです。最後が、右部分木にデータを挿入する規則です。
リスト : 最大値を求める search_max(node(X, _, nil), X). search_max(node(_, _, Right), X) :- search_max(Right, X).
最大値は簡単に求めることができます。右の子を順番にたどっていき、右の子がない節に行き着いたとき、その節のデータが最大値になります。最初の規則で右の子が nil であれば、その節のデータ X が最大値になります。次の規則で、右の子 Right が nil でなければ search_max を再帰呼び出しして右の子をたどります。
リスト : 最小値を求める search_min(node(X, nil, _), X). search_min(node(_, Left, _), X) :- search_min(Left, X).
最小値は簡単に求めることができます。左の子を順番にたどっていき、左の子がない節に行き着いたとき、その節のデータが最小値になります。最初の規則で左の子が nil であれば、その節のデータ X が最小値になります。次の規則で、左の子 Left が nil でなければ search_min を再帰呼び出しして左の子をたどります。
最大値または最小値の節は「葉」もしくは子を一つだけ持っています。データの削除は今までと違って少々面倒ですが、削除するデータが「葉」の場合や子を一つだけ持っている節の場合は簡単です。最初に、葉を削除する場合を説明します。下図を見てください。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 15 nil
↑
17 を削除する 削除
図 : データの削除 (葉の場合)
17 を削除する場合を考えてみましょう。17 は「葉」にあたるので、それを削除するだけで大丈夫です。親の Right を nil にするだけです。
次に、子が一つある場合を考えてみましょう。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 15
／ ＼ ／ ／ ＼
11 13 15 11 13
16 を削除する
図 : データの削除 (子が一つの場合)
16 を削除する場合、その子である 15 と置き換えれば二分探索木の構成は保たれます。これも簡単ですね。プログラムは次のようになります。
リスト : 最大値の節を削除
delete_max(node(_, Left, nil), Left).
delete_max(node(X, Left, Right), node(X, Left, New_node)) :-
delete_max(Right, New_node).
述語 delete_min は最大値を格納している節を削除します。右の子が nil の節を探すのは search_max と同じです。見つけたら、もう一つの子 Left がデータを削除した木になります。葉の場合、Left は nil になるので、単純に削除されることになります。
右の子があれば delete_max を再帰呼び出しして、その右部分木の中から最大値を探し出して削除します。そして、削除した部分木 New_node を新しい節の右の子にセットします。これで最大値の節を削除することができます。
リスト : 最小値の節を削除
delete_min(node(_, nil, Right), Right).
delete_min(node(X, Left, Right), node(X, New_node, Right)) :-
delete_min(Left, New_node).
述語 delete_min は最小値を格納している節を削除します。左の子が nil の節を探すのは search_min と同じです。見つけたら、もう一つの子 Right がデータを削除した木になります。葉の場合、Right は nil になるので、単純に削除されることになります。
左の子があれば delete_min を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。そして、削除した部分木 New_node を新しい節の左の子にセットします。これで最小値の節を削除することができます。
木の途中のデータを削除する場合、二分木の構成を崩さないように注意しないといけません。特に、子が二つある節を削除する場合はちょっと面倒です。次の図を見てください。
14 15 <- 最小値と置き換え
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 nil 17
↑
14 を削除する 削除
図 : データの削除 (子が二つの場合)
この場合、削除するデータの右部分木の中から最小値のデータ [*1] を探し、それと削除するデータと置き換えれば「右部分木 < 節 < 左部分木」の構成を崩さなくてすみます。上図で、14 を削除することを考えてみましょう。右部分木の中で 15 が最小値なので、それと 14 を置き換えます。そして、15 を格納していた節は削除します。節が最小値を格納している場合、その節の左の子は存在しないので、その節を削除することは簡単です。
プログラムは次のようになります。
リスト : データの削除
delete_tree(X, node(X, Left, nil), Left) :- !.
delete_tree(X, node(X, nil, Right), Right) :- !.
delete_tree(X, node(X, Left, Right), node(Min_value, Left, New_node)) :-
search_min(Right, Min_value),
delete_min(Right, New_node).
delete_tree(X, node(Y, Left, Right), node(Y, New_node, Right)) :-
X < Y, delete_tree(X, Left, New_node).
delete_tree(X, node(Y, Left, Right), node(Y, Left, New_node)) :-
X > Y, delete_tree(X, Right, New_node).
最初の規則は右の子がない節を削除する場合です。左の子 Left が削除した木になります。節が葉の場合、Left が nil になるので、この規則でデータを削除することができます。次の規則で左の子がない節を削除します。
左右の子がある場合は search_min で右部分木 Right から最小値 Min_value を求め、delete_min で Right から最小値を格納している節を削除します。そして、節 node(Min_value, Left, New_node) がデータを削除した新しい部分木になります。あとの規則で delete_tree を再帰呼び出しして、X と等しいデータを探します。
リスト : 巡回 (通りがけ) traverse_tree(X, node(_, Left, _)) :- traverse_tree(X, Left). traverse_tree(X, node(X, _, _)). traverse_tree(X, node(_, _, Right)) :- traverse_tree(X, Right).
通りがけの場合、最初の規則で左部分木をたどり、次の規則で第 1 引数と節のデータ X をマッチングさせます。それから最後の規則で右部分木をたどります。
リスト : 巡回 (行きがけ) pre_traverse_tree(X, node(X, _, _)). pre_traverse_tree(X, node(_, Left, _)) :- pre_traverse_tree(X, Left). pre_traverse_tree(X, node(_, _, Right)) :- pre_traverse_tree(X, Right).
行きがけの場合、最初の規則で第 1 引数と節のデータ X をマッチングさせます。それから次の規則で左部分木をたどり、最後の規則で右部分木をたどります。
リスト : 巡回 (帰りがけ) post_traverse_tree(X, node(_, Left, _)) :- post_traverse_tree(X, Left). post_traverse_tree(X, node(_, _, Right)) :- post_traverse_tree(X, Right). post_traverse_tree(X, node(X, _, _)).
帰りがけの場合、最初の規則で左部分木をたどり、次の規則で右部分木をたどります。最後の規則で、第 1 引数と節のデータ X をマッチングさせます。
リスト : リストを二分木に変換
tree_of_list(Xs, Tree) :- tree_of_list(Xs, nil, Tree).
tree_of_list([], Tree, Tree).
tree_of_list([X|Xs], Node, Tree) :-
insert_tree(X, Node, New_node), tree_of_list(Xs, New_node, Tree).
tree_of_list/2 は tree_of_list/3 を呼び出します。第 2 引数が累積変数で、空の木 (nil) を初期値とします。あとは、第 1 引数のリストから要素を順番に取り出して、insert_tree で第 2 引数の二分木に挿入していくだけです。
リスト : 二分木をリストに変換 list_of_tree(Tree, Xs) :- findall(X, traverse_tree(X, Tree), Xs).
list_of_tree は集合述語 findall を使うと簡単です。traverse_tree で二分木を巡回して要素 X を取り出し、それを findall でリストに格納するだけです。
リスト : 木の高さを求める
height_tree(nil, 0).
height_tree(node(_, Left, Right), H) :-
height_tree(Left, H1),
height_tree(Right, H2),
(H1 > H2 -> H is H1 + 1; H is H2 + 1).
最初の規則は、空の木 (nil) の高さは 0 であることを表しています。あとは、height_tree を再帰呼び出しして左右の部分木の高さを求め、大きいほうの高さに 1 を加えたものが、その部分木の高さ H になります。
リスト : 節の個数を求める count_node(nil, 0). count_node(node(_, Left, Right), N) :- count_node(Left, N1), count_node(Right, N2), N is N1 + N2 + 1.
節の個数を求める count_node も簡単です。最初の規則は空の木 (nil) には節がないことを表しています。次の規則で、count_node を再帰呼び出しして左右の部分木の節の個数 N1, N2 を求め、N1 + N2 + 1 がその部分木の節の個数になります。
リスト : データの合計値を求める
sum_tree(nil, 0).
sum_tree(node(X, Left, Right), N) :-
sum_tree(Left, N1),
sum_tree(Right, N2),
N is N1 + N2 + X.
データの合計値を求める sum_tree も簡単です。最初の規則は空の木 (nil) の合計値は 0 であることを表しています。次の規則で、sum_tree を再帰呼び出しして左右の部分木の合計値 N1, N2 を求め、N1 + N2 + X がその部分木の合計値になります。
リスト : 二分木の終端を自由変数とする場合
% 問題 51 : 二分探索木の判定 (修正 2014/08/17)
check(_, nil) :- !.
check(X, Y) :- X =< Y.
istree(Node, A, A) :- var(Node), !.
istree(node(X, Left, Right), A, B) :-
istree(Right, A, C),
check(X, C),
istree(Left, X, B).
istree(Node) :- istree(Node, nil, _).
% 問題 52 : データの探索
search_tree(_, Node) :- var(Node), !, fail.
search_tree(X, node(X, _, _)).
search_tree(X, node(Y, Left, _)) :- X < Y, search_tree(X, Left).
search_tree(X, node(Y, _, Right)) :- X > Y, search_tree(X, Right).
% 問題 53 : データの挿入
insert_tree(X, node(X, _, _)) :- !.
insert_tree(X, node(Y, Left, _)) :- X < Y, insert_tree(X, Left).
insert_tree(X, node(Y, _, Right)) :- X > Y, insert_tree(X, Right).
% 問題 54 : 最大値を探す
search_max(node(X, _, Right), X) :- var(Right), !.
search_max(node(_, _, Right), X) :- search_max(Right, X).
% 問題 55 : 最小値を探す
search_min(node(X, Left, _), X) :- var(Left), !.
search_min(node(_, Left, _), X) :- search_min(Left, X).
% 問題 56 : 最大値の節を削除
delete_max(node(_, Left, Right), Left) :- var(Right), !.
delete_max(node(X, Left, Right), node(X, Left, New_node)) :-
delete_max(Right, New_node).
% 問題 57 : 最小値の節を削除
delete_min(node(_, Left, Right), Right) :- var(Left), !.
delete_min(node(X, Left, Right), node(X, New_node, Right)) :-
delete_min(Left, New_node).
% 問題 58 : データの削除
delete_tree(_, Node, _) :- var(Node), !, fail. % データが見つからない場合
delete_tree(X, node(X, Left, Right), Left) :- var(Right), !.
delete_tree(X, node(X, Left, Right), Right) :- var(Left), nonvar(Right), !.
delete_tree(X, node(X, Left, Right), node(Min_value, Left, New_node)) :-
search_min(Right, Min_value),
delete_min(Right, New_node).
delete_tree(X, node(Y, Left, Right), node(Y, New_node, Right)) :-
X < Y, delete_tree(X, Left, New_node).
delete_tree(X, node(Y, Left, Right), node(Y, Left, New_node)) :-
X > Y, delete_tree(X, Right, New_node).
% 問題 59 : 巡回 (通りがけ)
traverse_tree(_, Node) :- var(Node), !, fail.
traverse_tree(X, node(_, Left, _)) :- traverse_tree(X, Left).
traverse_tree(X, node(X, _, _)).
traverse_tree(X, node(_, _, Right)) :- traverse_tree(X, Right).
% 問題 60 : 巡回 (行きがけ)
pre_traverse_tree(_, Node) :- var(Node), !, fail.
pre_traverse_tree(X, node(X, _, _)).
pre_traverse_tree(X, node(_, Left, _)) :- pre_traverse_tree(X, Left).
pre_traverse_tree(X, node(_, _, Right)) :- pre_traverse_tree(X, Right).
% 問題 61 : 巡回 (帰りがけ)
post_traverse_tree(_, Node) :- var(Node), !, fail.
post_traverse_tree(X, node(_, Left, _)) :- post_traverse_tree(X, Left).
post_traverse_tree(X, node(_, _, Right)) :- post_traverse_tree(X, Right).
post_traverse_tree(X, node(X, _, _)).
% 問題 62 : リストを二分木に変換
tree_of_list([], _).
tree_of_list([X|Xs], Node) :-
insert_tree(X, Node), tree_of_list(Xs, Node).
% 問題 63 : 二分木をリストに変換
list_of_tree(Tree, Xs) :- findall(X, traverse_tree(X, Tree), Xs).
% 問題 64 : 木の高さを求める
height_tree(Node, 0) :- var(Node), !.
height_tree(node(_, Left, Right), H) :-
height_tree(Left, H1),
height_tree(Right, H2),
(H1 > H2 -> H is H1 + 1; H is H2 + 1).
% 問題 65 : 節の個数を求める
count_node(Node, 0) :- var(Node), !.
count_node(node(_, Left, Right), N) :-
count_node(Left, N1),
count_node(Right,N2),
N is N1 + N2 + 1.
% 問題 66 : データの合計値を求める
sum_tree(Node, 0) :- var(Node), !.
sum_tree(node(X, Left, Right), N) :-
sum_tree(Left, N1),
sum_tree(Right, N2),
N is N1 + N2 + X.
?- istree(node(5, node(4, _, _), node(6, _, _))). true ; false. ?- istree(node(5, node(7, _, _), node(6, _, _))). false. ?- search_tree(5, node(5, node(4, _, _), node(6, _, _))). true ; false. ?- search_tree(6, node(5, node(4, _, _), node(6, _, _))). true ; false. ?- search_tree(0, node(5, node(4, _, _), node(6, _, _))). false. ?- insert_tree(5, X). X = node(5, _G362, _G363). ?- insert_tree(5, X), insert_tree(4, X). X = node(5, node(4, _G498, _G499), _G495) ; false. ?- insert_tree(5, X), insert_tree(4, X), insert_tree(6, X). X = node(5, node(4, _G633, _G634), node(6, _G637, _G638)) ; false. ?- search_max(node(5, node(4, _, _), node(6, _, _)), X). X = 6. ?- search_min(node(5, node(4, _, _), node(6, _, _)), X). X = 4. ?- delete_max(node(5, node(4, _, _), node(6, _, _)), X). X = node(5, node(4, _G507, _G508), _G511). ?- delete_min(node(5, node(4, _, _), node(6, _, _)), X). X = node(5, _G508, node(6, _G511, _G512)). ?- delete_tree(5, node(5, node(4, _, _), node(6, _, _)), X). X = node(6, node(4, _G531, _G532), _G536) ; false. ?- delete_tree(4, node(5, node(4, _, _), node(6, _, _)), X). X = node(5, _G531, node(6, _G535, _G536)) ; false. ?- delete_tree(6, node(5, node(4, _, _), node(6, _, _)), X). X = node(5, node(4, _G531, _G532), _G535). ?- delete_tree(0, node(5, node(4, _, _), node(6, _, _)), X). false. ?- traverse_tree(X, node(5, node(4, _, _), node(6, _, _))). X = 4 ; X = 5 ; X = 6 ; false. ?- pre_traverse_tree(X, node(5, node(4, _, _), node(6, _, _))). X = 5 ; X = 4 ; X = 6 ; false. ?- post_traverse_tree(X, node(5, node(4, _, _), node(6, _, _))). X = 4 ; X = 6 ; X = 5. ?- tree_of_list([5, 4, 6], X). X = node(5, node(4, _G441, _G442), node(6, _G445, _G446)) ; false. ?- list_of_tree(node(5, node(4, _, _), node(6, _,_)), X). X = [4, 5, 6]. ?- height_tree(node(5, node(4, node(3, _, _), _), node(6, _,_)), X). X = 3. ?- count_node(node(5, node(4, node(3, _, _), _), node(6, _,_)), X). X = 4. ?- sum_tree(node(5, node(4, node(3, _, _), _), node(6, _,_)), X). X = 18.