btree.h and btree.cpp

/***************************************************************************
 *   Copyright (C) 2006 by Madan Nain   *
 *   mnain@yahoo.com   *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/
 
#include <iostream>
using namespace std;
 
struct node
{
  int key_value;
  node *left;
  node *right;
};
 
class btree
{
    public:
        btree();
        ~btree();
 
        void insert(int key);
        node *search(int key);
        void destroy_tree();
        node *getRoot() { return root; }
        node *getLeft(node *n) { return n->left; }
        node *getRight(node *n) { return n->right; }
 
  private:
        void destroy_tree(node *leaf);
        void insert(int key, node *leaf);
        node *search(int key, node *leaf);
        node *root;
};
 
btree::btree()
{
  root=NULL;
}
 
btree::~btree()
{
  destroy_tree();
}
 
void btree::insert(int key, node *leaf)
{
  if(key< leaf->key_value)
  {
    if(leaf->left!=NULL)
     insert(key, leaf->left);
    else
    {
      leaf->left=new node;
      leaf->left->key_value=key;
      leaf->left->left=NULL;    //Sets the left child of the child node to null
      leaf->left->right=NULL;   //Sets the right child of the child node to null
    }  
  }
  else if(key>=leaf->key_value)
  {
    if(leaf->right!=NULL)
      insert(key, leaf->right);
    else
    {
      leaf->right=new node;
      leaf->right->key_value=key;
      leaf->right->left=NULL;  //Sets the left child of the child node to null
      leaf->right->right=NULL; //Sets the right child of the child node to null
    }
  }
}
 
node *btree::search(int key, node *leaf)
{
  if(leaf!=NULL)
  {
    if(key==leaf->key_value)
      return leaf;
    if(key<leaf->key_value)
      return search(key, leaf->left);
    else
      return search(key, leaf->right);
  }
  else return NULL;
}
 
void btree::insert(int key)
{
  if(root!=NULL)
    insert(key, root);
  else
  {
    root=new node;
    root->key_value=key;
    root->left=NULL;
    root->right=NULL;
  }
}
 
node *btree::search(int key)
{
  return search(key, root);
}
 
void btree::destroy_tree()
{
  destroy_tree(root);
}
 
 
void btree::destroy_tree(node *leaf)
{
  if(leaf!=NULL)
  {
    destroy_tree(leaf->left);
    destroy_tree(leaf->right);
    delete leaf;
  }
}
 
node * inorder(btree *leaf) {
  if (leaf != NULL) 
    cout << leaf->key_value << endl;
  else
    return NULL;
  if (leaf->left != NULL)
    inorder(leaf->left);
  else
    inorder(leaf->right);
}
 
node * preorder(node *leaf) {
  if (leaf->left != NULL) 
    preorder(leaf->left);
  if (leaf != NULL)
    cout << leaf->key_value << endl;
  else
    return NULL;
  if (leaf->right != NULL)
    preorder(leaf->right);
}
 
node * postorder(node *leaf) {
  if (leaf->left != NULL)
    postorder(leaf->left);
  if (leaf->right != NULL)
    postorder(leaf->right);
  if (leaf != NULL) 
    cout << leaf->key_value << endl;
  else
 
    return NULL;
}

btree.cpp.txt · Last modified: 2014/10/25 21:52 (external edit)
CC Attribution-Share Alike 3.0 Unported
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0