摘要：标号树的编码是一串能够映射一棵标号树结构的标号序列，由于在现代优化算法中便于运算而常常被采用。本文对四种常见的标号树的编解码方法进行了综述，并就标号树直观的边集表示和编码表示之间的转换算法进行讨论，实现了四种标号树编解码的线性算法。
　　关键词：标号树；Prufer编码；Nevile编码；DM编码
　　● 引言
　　标号树是计算机领域中常见的一种数据组织形式，它的传统存储方法通常有双亲表示法、孩子表示法、孩子兄弟表示法、边集表示法等，这些表示方法，在遗传、粒子群等现代优化算法中，由于很难进行运算，所以很少被使用。而标号树的编码是一串可以映射一棵标号树的标号序列，由于其存储简单、便于运算，常常被采用，因而对于标号树编码的深入讨论，无论在计算机的理论还是应用上，都有着十分重要的意义。
　　1918年Prufer在证明Cayley定理时，最先提出了Prufer编码，1953年Neville提出了三种编码方法，其中第一种和Prufer码一样，后两种称之为Neville2码、Neville3码，近年来Deo和Micikevicius又提出了一种新的编码方法。我们将上述四种编码简称为PR、N2、N3、DM码。
　　根据编码定义，以上四种编码除DM编解码的算法时间为О（n），其他三种都为О（n2）。近年来一些文献用算法语言给出了它们的线性算法思想。本文在综述上述四种编解码规则之后，用C语言，就标号树直观的边集表示和编码表示之间的转换，给出了编码和解码的线性算法。
　　● 标号树的编码
　　1.编码方法
　　总的来说，四种编码方法都是以叶节点的删除为基础，直至只剩下一条边为止，按照n-2个叶节点的删除顺序，依次将其在删除前的邻接点编号组成一个数字序列，就是其标号树的编码。四种编码的不同在于叶节点的删除顺序不同。
　　（1）PR编码
　　删除标号树中最小编号的叶节点；重复第一步，直至该标号树剩一条边。
　　如图1所示的标号树，PR编码的叶子节点删除顺序应为3、4、5、6、8、1、2、9，其相应的邻接点顺序为（6，10，6，7，1，2，7，7）。
　　（2）N2编码
　　按升序将标号树的叶节点整批删除；在修正过的标号树上重复第一步，直至该标号树剩一条边。
　　如图1，N2编码的叶子节点删除顺序应为第一层的3、4、5、8、9和第二层的1、6、10，其相应的邻接点顺序为（6，10，6，1，7，2，7，7）。
　　（3）N3编码
　　从最小叶节点开始，逐个删除其所在链上的节点，直至该链被删除；重复第一步，直至该标号树剩一条边。
　　如图1，N3编码的叶节点删除顺序应为第一条链3，第二条链4、10，第三条链5、6，第四条链8、1、2，其相应的邻接点顺序为（6，10，7，6，7，1，2，7）。
　　（4）DM编码
　　按升序将标号树的叶节点整批删除；对修正过的标号树按照其叶节点出现的先后顺序进行整批删除；重复第二步，直至该标号树剩一条边。
　　如图1，DM编码的叶子节点删除顺序应为第一层的3、4、5、8、9和第二层的10，6，1，其相应的邻接点顺序为（6，10，6，1，7，7，7，2）。
　　2.编码算法
　　（1）存储结构
　　typedef struct node
　　{ int data；
　　struct node *next；
　　} Node；
　　typedef Node LTree[N 1]；
　　LTree t；
　　标号树的存储结构采用了图的邻接表存储形式，其说明语句如上，标号树的邻接表存储示意图见图2。将标号树中每个节点i的度数存放在t[i]的data域中，将与该节点i相邻的所有邻接点，以链表链接在t[i]的next域中，为了节点i和t数组下标的一致，这里数组的长度定义为N 1。
　　（2）PR编码算法
　　PR编码算法的思想：在邻接表t中顺序查找出第一个度数为1的节点j（t[j].data=1），当前最小的叶节点u=j，求出和u相邻的节点v，写入编码数组，删除最小叶节点u（t[u].data--，t[v].data--）；比较v和j，如果v　　PR编码算法实现见函数PR（ ），c数组存放标号树的PR编码；函数GetAdjvex（ ）实现标号树t中求解u节点的邻接点运算。
　　PR（ LTree t，int c[] ）
　　{ int i，j，u，v；
　　u=v=j=0；
　　for（i=1；i　　* { if（v