flibs/binarytree(n) 1.0 "flibs"
flibs/binarytree - Linked lists
TABLE OF CONTENTS
SYNOPSIS
DESCRIPTION
ROUTINES
COPYRIGHT
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:
-
The module MYDATA_MODULE is used, but the derived type
MYDATA is renamed to the (fixed) name LIST_DATA. (This
is the name used in the generic source file.)
-
The source code for the actual routines is simply included via the
INCLUDE statement.
-
Nothing more is required, we can close the source text for the module.
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.
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:
-
The binary trees can only store data of the same derived type. In
that sense the code is not generic.
-
Currently, the trees can only store derived types that do not require
an explicit destruction. If you want to store a derived type with
pointers to allocated memory, you can do that however, by supplying an
assignment operator. This would lead to a memory leak though. It is best
to wait for a next version that will allow such derived types to be
stored.
Copyright © 2005 Arjen Markus <arjenmarkus@sourceforge.net>