遍历二叉树的方法数

Question

考虑一个有 n 个节点的二叉树。为了举例考虑下面的树：

     1
   /   \
  2     3
 / \   / \
4   5 6   7
           \
            8

我可以通过多少种不同的方式完全遍历树，从根（顶部）节点开始，只移动到直接连接到已访问节点的未访问节点（即我可以从 1 到2 到 4，然后到 3)?

Answer 1

你在 Math Stack 交流中提问可能会更有运气。

你问的是被认为是一个偏序集的二叉树的线性扩展数。虽然我看不到通用公式，但可以按如下方式递归求解：

求遍历左右子树的路数（空树平凡遍历1路）。调用这些 T_L 和 T_R。设#L 和#R 分别为左树和右树的基数（大小）。那么整棵树的遍历方式数为

T_L * T_R * (#L + #R 选择#L)

因为我们可以用 T_L 种方式遍历左边的树，用 T_R 种方式遍历右边的树（与我们如何遍历右边的树无关），并且我们可以交错左右树在（#L + #R 选择#L）种方式。

在你的例子中有两种遍历左边树的方式，三种遍历右边树的方式并且（7选3）是35，所以有2*3*35 = 210种遍历树的方式.

Answer 2

@deinst 答案的程序验证，使用 Prolog：

traverse([], []) :- !.
traverse(F, [N|P]) :-
    % select a frontier node from F
    select(t(N,C), F, Rem),
    % append all new accessible children to the frontier
    append(C, Rem, NewF),
    % traverse the remaining set
    traverse(NewF, P).

tree(X) :-
    X = t(1,[t(2,[t(4,[]), t(5,[])]),t(3,[t(6,[]), t(7,[t(8,[])])])]).

do :-
    tree(X),
    findall(P, (traverse([X], P), write_ln(P)), Ps),
    length(Ps, L),
    write_ln(L).

这确实 return 210 种可能性，正如您的示例树所建议的那样。

?- do.
[1,2,4,5,3,6,7,8]
[1,2,4,5,3,7,8,6]
[1,2,4,5,3,7,6,8]
[1,2,4,3,6,7,8,5]
[1,2,4,3,6,7,5,8]
[1,2,4,3,6,5,7,8]
[1,2,4,3,7,8,6,5]
[1,2,4,3,7,8,5,6]
[1,2,4,3,7,6,8,5]
...
[1,3,2,7,6,4,8,5]
[1,3,2,7,6,4,5,8]
[1,3,2,7,6,5,8,4]
[1,3,2,7,6,5,4,8]
210
true.

遍历二叉树的方法数

Number Of Ways To Traverse a Binary Tree

algorithm

tree

binary-tree

binary-search-tree