Listing 1. Binary Tree

/*
 * Binary Tree
 */
using System;
using com.db4o;

namespace PersistentTrees
{
        /// <summary>
        /// Description of BinaryTree.
        /// </summary>
        public class BinaryTree
        {

                // The tree's root
                private TreeNode root;

                public BinaryTree()
                {
                        root = null;
                }

                public static BinaryTree nullfactory()
                {
                        return(new BinaryTree());
                }

                // insert
                // Add key to tree with associated object reference
                public void insert(string _key, Object _data)
                {
                        // Use recursion for this
                        root = insert(root, _key, _data);
                }

                // insert
                // This is worker method for inserting key and data
                // Insert _key into subtree t with _data associated
                private TreeNode insert(TreeNode t, string _key, Object
_data)
                {
                        // If this subtree is empty, build a new node
                        if(t == null)
                                t = new TreeNode(_key, _data);
                        else
                                if(_key.CompareTo(t.Key)<=0)
                                        t.Left = insert(t.Left,_key,
_data);
                                else
                                        t.Right = insert(t.Right,_key,
_data);

                        return(t);
                }

                // search
                // Search for a key in the tree.
                // Return the array from the TreeNode if found, null if
                // not
                // db is the ObjectContainer holding the tree.
                public Object[] search(string _key,
                                      ObjectContainer db)
                {
                        TreeNode t = search(root, _key, db);
                        if(t==null) return(null);       // Not found
                        db.activate(t,4);                       //
Activate to get data
                        return(t.getData());
                }

                // search
                // This is the worker method for searching.
                private TreeNode search(TreeNode t,
                                        string _key,
                                       ObjectContainer db)
                {
                        // Empty tree?
                        if(t==null) return(null);
                        if(_key.CompareTo(t.Key)==0) return(t);
                        if(_key.CompareTo(t.Key)<0)
                        {
                                db.activate(t.Left,2);
                                return(t = search(t.Left,_key,db));
                        }
                        db.activate(t.Right,2);
                        return(t = search(t.Right,_key,db));
                }

        }
}