Browse Prior Art Database

Dynamic Placing of Tree Structures in Windows

IP.com Disclosure Number: IPCOM000108062D
Original Publication Date: 1992-Apr-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 3 page(s) / 86K

Publishing Venue

IBM

Related People

Hultin, PG: AUTHOR

Abstract

Disclosed is an algorithm for placing an arbitrary tree in an arbitrary rectangular window. Arbitrary means that each tree node can have 0, 1 or more children and the window can have any size. This method, described below, is very useful in an application where tree structures are to be placed in windows. Definitions Let T be a tree and let n be a node in the tree. Def. depth(n) = i if n belongs to the i:th generation in the tree T. This means that depth(n) = 1 if n is the root node, depth(n) = 2 if n is a child to the root and so on. Def. depth(T) = the maximum depth among all nodes in T. Def. breadth(T,i) = number of nodes in the tree T on depth i. Def. max_breadth(T) = the maximum of breadth(T,i) among all depths i.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Dynamic Placing of Tree Structures in Windows

       Disclosed is an algorithm for placing an arbitrary tree
in an arbitrary rectangular window.  Arbitrary means that each tree
node can have 0, 1 or more children and the window can have any size.
This method, described below, is very useful in an application where
tree structures are to be placed in windows.
Definitions
Let T be a tree and let n be a node in the tree.
Def. depth(n) = i if n belongs to the i:th generation in the tree T.
This means that depth(n) = 1 if n is the root node, depth(n) = 2
if n is a child to the root and so on.
Def. depth(T) = the maximum depth among all nodes in T.
Def. breadth(T,i) = number of nodes in the tree T on depth i.
Def. max_breadth(T) = the maximum of breadth(T,i) among all depths i.
Let x be the relative breadth coordinate which has 0 to the left and
1 to the right, and let y be the relative height coordinate with 0 at
the top and 1 at the bottom of the window.

      The relative y coordinate for a node n is set to (depth(n) -
0.5) / depth(T).

      All nodes are first placed on depth 1, then on depth 2 and so
on.

      To position the nodes on depth i: the nodes n1,n2,....,nm are
called from left to right.  Let Tj be the subtree with nj as root.
The relative x coordinate for a node nj is set to: ((S
max_breadth(Tk) where 1 & k < j) + 0.5 x max_breadth (Tj)) / (S
max_breadth(Tk) where 1 & k & m ).  This means that the node nj gets
breadth in proportion to max_breadth(...