flibs/binarytree - Binary trees
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 genericity, 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 TREE_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:
Create a new tree with the given data associated to the root. The data are copied and stored in that root.
The variable that will be used for accessing the tree's root
The data to be stored in the root
Destroy the tree. All nodes contained in it will be destroyed as well.
The tree to be destroyed
Function to return the number of nodes in the tree.
The tree in question
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 =>.
The (parent) node in a tree or the root of a tree
Whether to return the right (.true.) or the left (.false.) child node.
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.
The node in the tree that should get a child node
The data to be stored in the child node
Whether to append on the right (.true.) or the left (.false.) side.
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!)
The node in the tree that should get a child node
The tree to be appended as the child node
Whether to append on the right (.true.) or the left (.false.) side.
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.
The element in the tree after which to insert a new one.
The subtree that was removeds the child node
Whether to remove on the right (.true.) or the left (.false.) side.
Return the data belonging to a node
The node of the tree in question
Put new data at a given node
The node of the tree in question
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>