遍历二叉树的方式数量

Question

考虑一棵有n个节点的二叉树。举例来说，考虑以下树形结构：

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

从根节点开始，只移动到已经访问过的直接连接节点（例如，我可以从1到2到4，然后到3），我有多少种完全遍历树的不同方式？

- mntruell

---

请查看：https://en.wikipedia.org/wiki/Tree_traversal - user206428

@sharky 你能详细说明一下吗？我看过这个页面，但是没有找到我的问题的答案。 - mntruell

你的意思是探索次数，而不是遍历次数，因为遍历意味着按照路径进行。例如，如果你已经访问了{1,2}，那么你可以访问4、5或3吗？ - sve

@svs 是的，我的意思是如果你已经访问了{1, 2}，那么你可以访问4、5或3。 - mntruell

答案不仅取决于n。例如，只有左节点的二叉树只有一种枚举。 - Raymond Chen

Answer 1

您可以在数学堆栈交换上询问，或许会更幸运。

您所询问的是将二叉树视为偏序集合时的线性扩展数量。虽然我找不到通用公式，但可以按照以下递归方法解决：

找出遍历左子树和右子树的方式数（空树可以用一种方式遍历）。称这些数分别为T_L和T_R。设#L和#R分别为左子树和右子树的基数（大小）。那么整棵树的遍历方式数应为

T_L * T_R * (#L + #R choose #L)

因为我们可以以T_L种方式遍历左子树、以T_R种方式遍历右子树（与如何遍历右子树无关）并以(#L + #R choose #L)种方式交错遍历左右子树。

在您的例子中，有两种遍历左子树的方式，三种遍历右子树的方式，(7 choose 3)为35，因此遍历该树的方式有2*3*35=210种。

- deinst

---

#R choose #L 是什么意思？ - mntruell

这是二项式系数，(n选择k)是从n个不同的物品中选择k个物品的方式数量。公式为n!/(k! * (n-k)!)，其中!表示阶乘。 - deinst

Answer 2

使用Prolog进行@deinst答案的程序化验证：

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).

这确实返回了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.

- user206428