algorithm - 遍历二叉树的方法数

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种遍历树的方式。