Differences

This shows you the differences between two versions of the page.

Link to this comparison view

btree.cpp [2014/10/26 01:52] (current)
Line 1: Line 1:
 +==== btree.h and btree.cpp ====
 +
 +<code lang="​c">​
 +
 +/​***************************************************************************
 + ​* ​  ​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;
 +}
 +
 +</​code>​
 +
 +----
 +
 +  * [[cplusplus|Back to C++]]
  
btree.cpp.txt ยท Last modified: 2014/10/26 01: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