不知大家在学习二进制或状态压缩时又没有想过这样一个问题：好像一个n位的二进制数码和一个高度为n+1的满二叉树相差不大，都可以表示$2^n$个状态？今天，我想分享一下我的思考。 如图展示的是一棵满二叉树： 每一条边上都标注了数字0或1（按照边从左到右的顺序升序标注数字） 令满二叉树的深度为k（此处k=4），$E_u$表示从根节点1号到u号节点的简单路径，$P(u,v)$表示边$(u,v)$上标注的数字，$D_u$表示u号节点的深度，注意到有如下方程：

$u=2^{k} + \sum_{(u,v) \in E_u} 2^{k-D_v}P(u,v)$ 成立 不妨来看几个例子： 从1到6的简单路径为$\{(1,3),(3,6)\}$，让我们对这个路径中每一条边取P值，得$P_6=\{1,0\}$。上述方程描述的实际上就是 对于节点u构造一个二进制数，将数码“1”放在最前面，然后将我们先前得到的$P_u$序列中的数码依次写在后面，最终得到的二进制数与u相等的结论（对于6，操作过程为：1->11->110，注意到$(110)_2=6$） 大家可以尝试一下：对于任意满n叉树，都可以使用此方法得到相同的结论。（实际上是不想画图了） 丢个公式（其中N代表进制数）： $u=N^k+\sum_{(u,v) \in E_u}N^{k-D_v}P(u,v)$ 总结：n进制数码的每一位可以表达从上一个状态推进到这一个状态的过程，而满n叉树上的节点则是过程得到的结果 (仅仅是我的想法) PS：如果不是满n叉树，情况又会怎样呢？请听下回分解