探究：是否可以通过编码的形式计算树节点的一些属性

1 引入

图1: 二叉树示例

对于一个二叉树，从根节点出发，使用由LR组成的字符串表示路径，则对于每一条路径可以唯一表示每一个节点。如图1所示：4号节点可以对应字符串 LR，2号节点对应字符串R。特别的，根节点对应的字符串为空字符串。

1.1 更加一般的情况

类比于二叉树，可以通过扩展LR的字符集，来适应一个节点有超过两个孩子节点的情形，例如图2中的4号节点，可以用字符串C来表示。

图2：一般的树结构

1.2 符号说明

1. 设是树的节点集合，则可以通过上述过程，将每一个节点映射成一个字符串，设字符串的集合为；
2. 定义函数，使得以及；
3. 定义 是一个集合，该集合的所有节点均是的祖先节点；
4. 定义为节点和节点之间的距离；
5. 定义是一个节点，表示号节点于号节点的最近公共祖先。在图1中，而；
6. 假设是一个长度为的字符串，则，用于表示字符串所有的前缀的集合；
7. 假设是一个字符串结合，，是中最长的字符串之一，且在最长的字符串中字典序最大；
8. 假设是一个字符串，表示字符串的长度。

1.3 性质

• 对于任意的字符串和，分别对应树中的节点和，有：
  1. 如果，那么节点。
  2. 。
  3. 

2 特殊场景

2.1 满二叉树编码表示

图3：二叉树

对于一个满二叉树，如果将节点按照层序遍历的顺序从1开始编号，就可以根据节点的二进制位表示，来获取到对应的字符串。如图3所示。值得注意的是，该编码与第一节相比，每一个字符串多了一个字符1。