单次遍历树生成前后序编码的方法

摘要

本发明公开了一种通过单次遍历便可同时构建XML文档前序编码和后序编码的方法，属于数据结构与算法领域。本发明通过把XML节点的遍历序和编码序分开，然后合并前序编码和后序编码中相同的遍历序，关键的技术点为正确地定位入、出节点的时机，并同时维护两个独立增长的前序编码序和后序编码序，当完成对XML树的一次扫描时每个节点都将得到自己的唯一的前序编码和后序编码。本发明把两次扫描的消耗降低到一次，当数据量很大时，单次扫描生成前后序编码的方法减少了一半的时间开销，大大加速了XML文档构建索引的过程。

主权项

一种构建XML前序和后序编码的方法，其特征在于，所述方法对XML文档的遍历次数为一次；其实现方法为：定义函数V，其参数为树的节点n，该函数的实现方法如下：1).如果参数n为null，则退出本函数；否则执行2)；2).构建前序编码；3).把参数n定义为其左子节点，递归调用函数V；4).构建后序编码；5).构建前序编码；6).把参数n定义为其右子节点，递归调用函数V；7).构建后序编码；8).函数结束。