Browse Prior Art Database

Enumerating the Nodes of a Tree Compactly

IP.com Disclosure Number: IPCOM000088764D
Original Publication Date: 1977-Jul-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Rosenberg, AL: AUTHOR

Abstract

Disclosed herein is a technique for enumerating the nodes of a degree d rooted tree (total degree is intended here so, e.g., an interior node of binary tree has degree 3) in such a way that the node labelled k in the enumeration is at distance, at most, d from the node labelled k+1. Such a technique is of potential interest in areas such as data encoding [3] and tree-traversing algorithms [2, Section 2.3.1]. The advantages of this technique are twofold: it is patently efficient to program, and it operates in time linear in the number of nodes of the tree.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 2

Enumerating the Nodes of a Tree Compactly

Disclosed herein is a technique for enumerating the nodes of a degree d rooted tree (total degree is intended here so, e.g., an interior node of binary tree has degree 3) in such a way that the node labelled k in the enumeration is at distance, at most, d from the node labelled k+1. Such a technique is of potential interest in areas such as data encoding [3] and tree-traversing algorithms [2, Section 2.3.1]. The advantages of this technique are twofold: it is patently efficient to program, and it operates in time linear in the number of nodes of the tree.

One can derive quite directly from [4] a technique for tree-enumerating with the property that the distance between the nodes labelled k and k+1is at most 3, independent of d.

In common with the algorithm from [4], the present technique is readily extended to one that produces enumerations of the nodes of arbitrary connected graphs, with the same properties as the produced enumerations of trees. One merely prefixes either of these techniques with any standard procedure for producing a spanning tree for the input graph.

The Procedure. The existence is assumed of a coroutine NEXT which, upon repeated invocations, performs a depth-first traversal of the input tree, beginning at the tree's root. Each invocation of NEXT returns the address of the next node encountered in the depth-first traversal together with a flag, Last, which is set if this new node is being encountered for the last time. The first invocation yields the root's address. When the entire tree has been traversed (i.e., when the root is enco...