| 摘要 |
<p>A method for traversing multi-bit trie tree is disclosed in order to solve the conflict between the performance of traversal and consumption of memory. The method in accordance with the invention employs a preorder traversal of the multi-bit trie tree, and before processing a node first compares the node with the record of the processed nodes, if the node has been processed then traverses the next node, otherwise processes the node with the processing function; when processing of the node is completed, the position information, the prefix information corresponding to the position as well as set pointers and IP prefix information of all the parent nodes are recoded. The method reduces the number of memory accesses and doesn't require allocation and release of the memory as well as caching the prefix information of IP prefixes of the same level. The processing sequence is also guaranteed due to the employment of the preorder traversal of the multi-bit trie tree at the same time.</p> |
