| 摘要 |
A compact representation of a tree data structure and techniques for navigating the compact representation. The compact representation is a list. Each element of th e list represents a node of the tree and the list is organized according to a preo rder traversal of the tree. Each list element contains only the index of a data dicti onary entry for the kind of item represented by the node corresponding to the list ele ment. The navigation techniques permit the location of the list element for the siblin g of the node corresponding to the given list element, the location of the list eleme nt for that node's parent, and in the case of a parent node, the location of the list e lement for any child of the parent. The navigation techniques work by finding the list elements for subtrees. The subtrees are found by techniques based on the fact th at the number of children of all of the nodes in a subtree minus the number of node s in the subtree always equals -1. The number of children of a given node is determin ed by a valence function which takes the index of the data dictionary entry as iits argument. |
