Total members 11791 |It is currently Sun Aug 18, 2019 1:33 am Login / Join Codemiles

Java

C/C++

PHP

C#

HTML

CSS

ASP

Javascript

JQuery

AJAX

XSD

Python

Matlab

R Scripts

Weka





Binary search tree C++
cpp code
//                                                    March 6, 1998
// Bert G. Wachsmuth
#include <iostream>
using namespace std;
#ifndef BINSTREE
#define BINSTREE


// you can change the type easily .
typedef int ElementType;
typedef int ValueType;

const int PRE_ORDER = 2;
const int IN_ORDER = 3;
const int POST_ORDER = 4;
const int LEVEL_ORDER = 5;
/*
Node class .
*/
class Node
{
// Left node pointer.
public: Node *left;
// right node pointer.
public: Node *right;
// ElementType integer in this case.
public: ElementType data;

// constructor
public: Node(void);
// constructor takes ElementType .
public: Node(ElementType);
};

/*
Binary Tree class
*/

class BinSTree
{ // Fields
private: Node *rootNode;
private: Node *currentNode;
private: int errorFlag;

// default Constructor and public methods
public: BinSTree(void);
// insert ElementType to tree.
public: void insert(ElementType);
// remove ElementType.
public: void remove(ValueType);
// get currentNode element.
public: ElementType retrieve(void);
// traverse the ree,
public: void traverse(int order);
// find a node by value.
public: void find(ValueType);
// destroy tree.
public: void destroy(void);
// check if the tree is full.
public: int isFull(void);
// check if the ree empty.
public: int isEmpty(void);
public: int hasError(void);

// private functions.
private: void preorder(Node *, int);
private: void postorder(Node *, int);
private: void inorder(Node *, int);
private: Node* findParentForNode(ValueType key);
private: Node* findNodeByValue(ValueType key);
// find the right node.
private: Node* findRightNode(Node *);
// delete a specific node.
private: void destroyNode(Node *);
};

Node::Node(void)
{
left = right = 0;
}

Node::Node(ElementType el)
{
left = right = 0;
data = el;
}



BinSTree::BinSTree(void)
{
rootNode = currentNode = 0;
errorFlag = false;
}


void BinSTree::find(ValueType key)
{
Node *p = findNodeByValue(key);
if (p == 0)
errorFlag = true;
else
{
errorFlag = false;
currentNode = p;
}
}

void BinSTree::insert(ElementType el)
{
if (rootNode == 0)
rootNode = new Node(el);
else
{
Node *p = findNodeByValue(el);
// if element not found before
if (p == 0)
{
// In case root node is parent.
Node *parent = rootNode;
if (p != rootNode)
parent = findParentForNode(el);
if (el > parent->data)
{
parent->right = new Node(el);
currentNode = parent->right;
}
else
{
parent->left = new Node(el);
currentNode = parent->left;
}
// everthing is ok .
errorFlag = false;
}

else
// duplicate key.
errorFlag = true;
}
}

void BinSTree::traverse(int order)
{
if (order == PRE_ORDER)
preorder(rootNode, 0);
else if (order == IN_ORDER)
inorder(rootNode, 0);
else if (order == POST_ORDER)
postorder(rootNode, 0);
else
cout << "order doesn't exists" << endl;
}

ElementType BinSTree::retrieve(void)
{
return currentNode->data;
}

int BinSTree::isFull(void)
{
return 0;
}

int BinSTree::isEmpty(void)
{
return (rootNode == 0);
}

int BinSTree::hasError(void)
{
return errorFlag;
}

void BinSTree::remove(ValueType key)
{

Node *p = findNodeByValue(key);
// check if node exists.
if (p == 0)
errorFlag = true;
// node exists .
else
{
// delete leaf node.
if ((p->right == 0) && (p->left == 0))
{
// (can find parent node.
if (p != rootNode)
{
Node *parent = findParentForNode(key);
if (parent->data < key)
parent->right = 0;
else
parent->left = 0;
}
else
rootNode = 0;
delete(p);
errorFlag = false;
currentNode = rootNode;
}
else if ((p->right == 0) && (p->left != 0)) // right subtree empty,
// left subtree not.
{
// can't find parent node .
if (p != rootNode)
{
Node *parent = findParentForNode(key);
if (parent->data < key)
parent->right = p->left;
else
parent->left = p->left;
}
else
rootNode = rootNode->left;
delete(p);
errorFlag = false;
currentNode = rootNode;
}
else if ((p->right != 0) && (p->left == 0)) // left subtree empty,
// right subtree not.
{
if (p != rootNode) // (can find parent now ...)
{
Node *parent = findParentForNode(key);
if (parent->data < key)
parent->right = p->right;
else
parent->left = p->right;
}
else
rootNode = p->right;
delete(p);
errorFlag = false;
currentNode = rootNode;
}
else // left and right
// subtrees not empty
{
Node *righty = findRightNode(p->left);
Node *parent = findParentForNode(righty->data);
p->data = righty->data; // swapping data with righty
if (parent != p)
parent->right = righty->left;
else
p->left = righty->left;
delete(righty);
errorFlag = false;
currentNode = rootNode;
}
}
}

void BinSTree::destroy(void)
{
destroyNode(rootNode);
}



void BinSTree::inorder(Node *p, int level)
{
if (p != 0)
{
inorder(p->left, level+1);
cout << "Node " << p->data << " at level " << level << endl;
inorder(p->right, level+1);
}
}

void BinSTree::preorder(Node *p, int level)
{
if (p != 0)
{
cout << "Node " << p->data << " at level " << level << endl;
preorder(p->left, level+1);
preorder(p->right, level+1);
}
}

void BinSTree::postorder(Node *p, int level)
{
if (p != 0)
{
postorder(p->left, level+1);
postorder(p->right, level+1);
cout << "Node " << p->data << " at level " << level << endl;
}
}

void BinSTree::destroyNode(Node *p)
{
if (p != 0)
{
destroyNode(p->left);
destroyNode(p->right);
delete(p);
}
}

Node* BinSTree::findParentForNode(ValueType key)
{
Node *p = rootNode, *q = 0;
while ((p != 0) && (p->data != key))
{
q = p;
if (p->data > key)
p = p->left;
else
p = p->right;
}
return q;
}

Node* BinSTree::findNodeByValue(ValueType key)
/* This function returns a pointer to the node containing the key
value 'key' if it is in the tree. Otherwise, it returns null */
{
Node *p = rootNode;
while ((p != 0) && (p->data != key))
if (p->data > key)
p = p->left;
else
p = p->right;
return p;
}

Node* BinSTree::findRightNode(Node *p)
{
Node *righty = p;
while (righty->right != 0)
righty = righty->right;
cout << "found right-most node to be: " << righty->data << "\n";
return righty;
}

#endif


int main(void)
{

return 0;
}





Author:
Mastermind
User avatar Posts: 2707
Have thanks: 74 time
Post new topic Reply to topic  [ 1 post ] 

  Related Posts  to : Binary search tree C++
 need help for creatinb binary tree in php     -  
 Java Binary Tree     -  
 binary search     -  
 Take tree nodes then create new tree with another root     -  
 A simple search page using Google AJAX Search API     -  
 Read Binary File in C++     -  
 convert string into binary     -  
 convert to binary number     -  
 convert binary number to decimal     -  
 conversion from binary to decimal numbers as string     -  



Topic Tags

C++ Data Structures
cron





Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
All copyrights reserved to codemiles.com 2007-2011
mileX v1.0 designed by codemiles team
Codemiles.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com