Browse Prior Art Database

Representation of Tree Data Structures as Matrices Suitable for User Defined Traversing

IP.com Disclosure Number: IPCOM000076837D
Original Publication Date: 1972-Apr-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 2 page(s) / 33K

Publishing Venue

IBM

Related People

Koch, K: AUTHOR

Abstract

The disclosed method refers to the economical mapping of trees, such as the parsing tree in Fig. 1, as matrices into computer memories. The matrix structure is statically organized, that means a fixed amount of core storage space is required for describing a node, assuming the nonterminal and terminal names have a uniform length.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 80% of the total text.

Page 1 of 2

Representation of Tree Data Structures as Matrices Suitable for User Defined Traversing

The disclosed method refers to the economical mapping of trees, such as the parsing tree in Fig. 1, as matrices into computer memories. The matrix structure is statically organized, that means a fixed amount of core storage space is required for describing a node, assuming the nonterminal and terminal names have a uniform length.

The proposed matrix comprises three lines and a number of columns, one column each being required for describing a nonterminal and a terminal node, respectively. Within the matrix the nodes of a tree are represented consecutively, without gaps. The order in which the nodes appear depends on the traverse technique used for processing the trees.

Fig. 2 shows the matrix structure for the parsing tree in Fig. 1, the nodes represented in the order in which they are visited by preorder traversal (visit root, traverse leftmost subtree, traverse remaining subtrees in preorder). The matrix shown in Fig. 2 is described below: NONTERMINAL/TERMINAL INDICATOR (1 bit).

This indicates whether the node described in the subsequent lines is a nonterminal (1) or a terminal (0) node. NONTERMINAL NAME/TERMINAL NAME.

For nonterminal nodes the NONTERMINAL NAME denoters the respective nonterminal.

For terminal nodes the TERMINAL NAME denotes the respective terminal. FATHER POINTER.

This line comprises pointers which refer to the matrix column describing the father of a given...