遍历二叉树的方法数量

Question

考虑n个节点的二叉树.为了举例,请考虑以下树:

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

有多少种不同的方法可以从根(顶部)节点开始完全遍历树,只移动到直接连接到已访问过的节点的未访问节点(即我可以从1到2到4但是然后到3)？

Answer 1

你可能会有更多的运气询问数学堆栈交换.

您要求将二进制树的线性扩展数视为一个poset.虽然我看不到通用公式,但可以递归地解决这个问题,如下所示:

找到遍历左右子树的方法的数量(以一种方式简单地遍历空树).调用这些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种遍历树的方法.