BSTreeConv

balanced search trees can can be converted

• to a textual representation,
• to a sequence of datas,
• or to a tree.

Signature of BSTreeConv

List of Import References :
See BOOL
See BSTree
See Char
See DENOTATION
See Nat
See Option
See Pair
See Seq
See String
See Tree

SIGNATURE BSTreeConv[data, <]

$Date: 2010-09-30 18:24:17 +0200 (Do, 30. Sep 2010) $ ($Revision: 616 $)

IMPORT BSTree[data, <] ONLY bstree[data, <]
       Tree[data] ONLY tree
       Seq[data] ONLY seq
       Seq[seq[data]] ONLY seq
       String ONLY string

Parameter

SORT data
FUN < : data ** data -> bool

Converting into Textual Representation

Trees are represented as follows:

empty Trees

are translated to "BS[/\]"

leaves

are translated to "BS[/data\]"

other tree[data, <]s

are represented as "BS[/data,left child,right child\]"

FUN ` : (data -> denotation) -> bstree[data, <] -> denotation

FUN ` : (data -> string)     -> bstree[data, <] -> string

These functions produce a twodimensional output of the tree. This works only for fixed width fonts, of course. The output assumes arbitrarily long lines. The function aborts, if one representation has zero length.

FUN graphic : (data -> denotation) -> bstree[data, <] -> denotation
FUN graphic : (data -> string    ) -> bstree[data, <] -> string

Converting into a Sequence

There are three possibilities: you can get the datas either in inorder -- left/node/right, in preorder -- node/left/right, or in postorder -- left/right/node.

FUN asSeqIn  asSeqPre asSeqPost : bstree[data, <] -> seq[data]

asSeqBreadth gives you a sequence of sequence of datas. The ith element of the sequence contains all elements of level i from left to right.

FUN asSeqBreadth : bstree[data, <] -> seq[seq[data]]

Converting into a Tree

You can get the underlying tree structure or convert a tree to a tree[data, <]

FUN asBSTree: tree[data] -> bstree[data, <]
FUN asTree: bstree[data, <] -> tree[data]

next node: BSTreeFilter,
prev node: BSTreeCompare,
up to node: Subsystem Balanced Search Trees