flibs/binarytree(n) 1.0 "flibs"

NAME

flibs/binarytree - Linked lists

TABLE OF CONTENTS

    TABLE OF CONTENTS
    SYNOPSIS
    DESCRIPTION
    ROUTINES
    COPYRIGHT

SYNOPSIS

call btree_create( btree, data)
call btree_destroy(btree )
count = btree_count( btree )
child => btree_child_node( node, right )
call btree_append_data( node, data, right )
call btree_append_subtree( node, subtree, right )
call btree_remove_subtree( node, subtree, right )
data = btree_get_data( node )
call btree_put_data( node, data )

DESCRIPTION

The binarytree.f90 source file allows you to implement binary trees of any (derived) type without having to edit the supplied source code. (The resulting binary tree is not balanced, that would require a method of ordering the data.) To achieve genericty, a simple technique is used, which is best illustrated by an example:

 
module MYDATA_MODULE

type MYDATA
    character(len=20) :: string
end type MYDATA

end module

module MYDATA_BTREES
    use MYDATA_MODULE, TREE_DATA => MYDATA

    include "binarytree.f90"
end module MYDATA_BTREES

The above code defines a module MYDATA_MODULE with the derived type that is to be stored in the binary trees. The name of that derived type can be anything.

It also defines a module MYDATA_BTREES which will be the module that holds the functionality to use binary trees:

To use a single type of binary trees in a program, we can just use the MYDATA_BTREES module. If you need more than one type of data in binary trees, then apply the same renaming trick on using the specific binary trees modules.

In fact the example in the source file "two_lists.f90" shows the general technique of how to accomplish this for linked lists. The same applies to binary trees.

ROUTINES

The source file binarytree.f90 provides the following routines:

call btree_create( btree, data)
Create a new tree with the given data associated to the root. The data are copied and stored in that root.

type(BINARY_TREE), pointer btree
The variable that will be used for accessing the tree's root

type(TREE_DATA), intent(in) data
The data to be stored in the root


call btree_destroy(btree )
Destroy the tree. All nodes contained in it will be destroyed as well.

type(BINARY_TREE), pointer btree
The list to be destroyed


count = btree_count( btree )
Function to return the number of nodes in the tree.

type(BINARY_TREE), pointer btree
The tree in question


child => btree_child_node( node, right )
Function to return the left or right child node of a given node in the tree. As each node is itself a tree, you can traverse the tree by repeatedly using this function on the result.

Note: it returns a pointer to the child node, so you must use =>.

type(BINARY_TREE), pointer node
The (parent) node in a tree or the root of a tree

logical right
Whether to return the right (.true.) or the left (.false.) child node.


call btree_append_data( node, data, right )
Append a new node to the left or right to the given node. (Note that no balancing is taken care of). If the node already has a child node, nothing is done.

type(BINARY_TREE), pointer node
The node in the tree that should get a child node

type(TREE_DATA), intent(in) data
The data to be stored in the child node

logical right
Whether to append on the right (.true.) or the left (.false.) side.


call btree_append_subtree( node, subtree, right )
Append a subtree to the left or right to the given node. If the node already has a child node, nothing is done. (Note: the subtree is referred to, not copied!)

type(BINARY_TREE), pointer node
The node in the tree that should get a child node

type(BINARY_TREE), pointer subtree
The tree to be appended as the child node

logical right
Whether to append on the right (.true.) or the left (.false.) side.


call btree_remove_subtree( node, subtree, right )
Remove a subtree to the left or right to the given node. A pointer to the subtree is returned in the "subtree" argument, so that this can be destroyed or used independently of the original tree.

type(BINARY_TREE), pointer node
The element in the list after which to insert a new one.

type(BINARY_TREE), pointer subtree
The subtree that was removeds the child node

logical right
Whether to remove on the right (.true.) or the left (.false.) side.


data = btree_get_data( node )
Return the data belonging to a node

type(BINARY_TREE), pointer node
The node of the tree in question


call btree_put_data( node, data )
Put new data at a given node

type(BINARY_TREE), pointer node
The node of the tree in question

type(TREE_DATA), intent(in) data
The data to be stored in the node
Notes:

COPYRIGHT

Copyright © 2005 Arjen Markus <arjenmarkus@sourceforge.net>