Theory

Optimization is mature root of evil
Inheritance is source of error

R & B is key to FP
Object is key to OOP

BST

#ifndef TreeNode
#define TreeNode


#ifdef WIN32
// Windows Function


template
class treeNode
{
public:

T key;
T value;
int level;

treeNode *leftNode;
treeNode *rightNode;


treeNode() : key(T()), value(T()), level(1),
leftNode(0),
rightNode(0)
{}

treeNode(const T& aKey) : key(aKey),
value(T()), level(1)
leftNode(0),
rightNode(0)
{}

treeNode(const T& aKey, const T& aValue)
: key(aKey),
value(aValue), level(1)
leftNode(0),
rightNode(0)
{}

~treeNode()
{
}
};


#else
// POSIX Function


#endif



#endif



#ifndef BST
#define BST

#include
#include
#include "TreeNode.h"


#ifdef WIN32
// Window Function


template
class BSearchTree
{
private:

treeNode* root;
BSearchTree (treeNode *);
BSearchTree& operator=(const BSearchTree);

public:
BSearchTree();

~BSearchTree();

void Insert(const T&, const T&);
treeNode* InsertSearch(treeNode*, const T&);

void Remove(const T&);

void destroy()const;
void PostOrderDestroy(treeNode*)const;

// Root->Left->Right
void PreOrder()const;
void RecursivePreOrder(treeNode*)const;

// Left->Root->Right
void InOrder()const;
void RecursiveInOrder(treeNode*)const;

// Left->Right->Root
void PostOrder()const;
void RecursivePostOrder(treeNode*)const;


// Utility Function
int size()const;
int RecursiveCount(treeNode*, int&)const;

T& minValue()const;
T& maxValue()const;

int maxDepth()const;
int RecursiveMaxDepth(const treeNode*, int&, int&)const;

treeNode* successor(const T&)const;
treeNode* predecessor(const T&)const;
treeNode* search(const T&)const;

void mirrorSwap()const;
void RecursiveMirrorSwap(treeNode*)const;

void generatePath()const;
void RecursiveGeneratePaths(treeNode *, T [],
int)const;
void displayPath(T [], int)const;

void doubleTree();
void doubleTreeInsert(treeNode*, std::deque&, std::deque&);
void RecursiveDoubleTreeinsert(treeNode*, std::deque&, std::deque&);
void RecursiveCopy(treeNode*, std::deque&, std::deque&)const;

void display(treeNode*)const;

};

// ================================================
template
BSearchTree::BSearchTree() : root(0)
{
}
// ================================================
template
BSearchTree::~BSearchTree()
{
if (root != 0)
{
destroy();
}
}
// ================================================
template
void BSearchTree::Insert(const T &key, const T &value)
{
if (root != 0)
{
treeNode* newNode = new treeNode(key, value);
treeNode* iteratorNode = root;

iteratorNode = InsertSearch(this->root, key);

if (key <>key)
{
iteratorNode->leftNode = newNode;
}
else
{
iteratorNode->rightNode = newNode;
}
}
else
{
treeNode* newNode = new treeNode(key, value);
root = newNode;
}

/*
Top Down construction - Create root first
Bottom Up construction - Create child first
*/
}
// ================================================
template
treeNode* BSearchTree::InsertSearch(treeNode *iteratorNode,
const T& key)
{
if (iteratorNode != 0)
{
if (key <>key)
{
if (iteratorNode->leftNode != 0)
{
return InsertSearch(iteratorNode->leftNode, key);
}
}
else
{
if (iteratorNode->rightNode != 0)
{
return InsertSearch(iteratorNode->rightNode, key);
}
}
}

return iteratorNode;
}
// ================================================
template
void BSearchTree::Remove(const T &key)
{
/*
if no child, just delete
if one child, point by grandparent

if two children, swap with it with
inorder-successor
(Left child of right sub Tree)

Smallest in right sub tree
Traverse once to right , then continue
traverse to left

or inorder-predecessor
(Right child of Left sub Tree)
Largest in left sub tree
*/
if (root != 0 && (root->leftNode != 0
&& root->rightNode != 0))
{
treeNode* iteratorNode = root;
treeNode* parentRemoveNode = root;

while (iteratorNode->key != key
&& (iteratorNode->leftNode != 0
|| iteratorNode->rightNode != 0))
{
if (key <>key)
{
(iteratorNode->leftNode != 0)
? iteratorNode = iteratorNode->leftNode
: iteratorNode;

(iteratorNode->key != key)
? parentRemoveNode = parentRemoveNode->leftNode
: parentRemoveNode;
}
else
{
(iteratorNode->rightNode != 0)
? iteratorNode = iteratorNode->rightNode
: iteratorNode;

(iteratorNode->key != key)
? parentRemoveNode = parentRemoveNode->rightNode
: parentRemoveNode;
}
}

if (iteratorNode->key == key)
{
// Key is equal root's key/remove root
if (this->root->key == key
|| root->key == iteratorNode->key)
{
treeNode* iteratorNode = root;
treeNode* tempRightNode = root;
treeNode* previousLeftNode = root->leftNode;

// root got right node
if (iteratorNode->rightNode != 0)
{
iteratorNode = iteratorNode->rightNode;
tempRightNode = iteratorNode->rightNode;

if (iteratorNode->leftNode != 0)
{
while (iteratorNode->leftNode != 0)
{
iteratorNode = iteratorNode->leftNode;
}
}

treeNode* newRoot = iteratorNode;
treeNode* removeNode = root;

root = newRoot;
root->leftNode = previousLeftNode;
root->rightNode = tempRightNode;

delete removeNode;
/*
set delete memory to 0
in order to avoid bug
when delete twice happen
*/
removeNode = 0;

}// root no right node
else
{
treeNode* removeNode = root;
treeNode* newRoot = root;

if (root->leftNode != 0)
{
newRoot = root->leftNode;
root->leftNode = newRoot;
}
delete removeNode;
/*
set delete memory to 0
in order to avoid bug
when delete twice happen
*/
removeNode = 0;
}

} // remove child
else
{
// two children
if (iteratorNode->leftNode != 0
&& iteratorNode->rightNode != 0)
{
treeNode* removeNode = iteratorNode;
treeNode* tempLeftNode = iteratorNode->leftNode;

iteratorNode = iteratorNode->rightNode;
while(iteratorNode->leftNode != 0)
{
iteratorNode = iteratorNode->leftNode;
}

if (parentRemoveNode->key
> iteratorNode->key)
{
parentRemoveNode->leftNode = iteratorNode;
}
else
{
parentRemoveNode->rightNode = iteratorNode;
}

iteratorNode->leftNode = tempLeftNode;

delete removeNode;
/*
set delete memory to 0
in order to avoid bug
when delete twice happen
*/
removeNode = 0;
}
// one children
else if ((iteratorNode->leftNode != 0
&& iteratorNode->rightNode == 0)
|| (iteratorNode->leftNode == 0
&& iteratorNode->rightNode != 0))
{
if (iteratorNode->leftNode != 0
&& iteratorNode->rightNode == 0)
{
treeNode* removeNode = iteratorNode;
treeNode* nextNode = iteratorNode->leftNode;

parentRemoveNode->leftNode = nextNode;
delete removeNode;
}
else
{
treeNode* removeNode = iteratorNode;
treeNode* nextNode = iteratorNode->rightNode;

parentRemoveNode->rightNode = nextNode;
delete removeNode;
/*
set delete memory to 0
in order to avoid bug
when delete twice happen
*/
removeNode = 0;
}

}
// no children
else if (iteratorNode->leftNode == 0
&& iteratorNode->rightNode == 0)
{
if (parentRemoveNode->leftNode
== iteratorNode)
{
parentRemoveNode->leftNode = 0;
}
else
{
parentRemoveNode->rightNode = 0;
}

delete iteratorNode;
/*
set delete memory to 0
in order to avoid bug
when delete twice happen
*/
removeNode = 0;
}
}
}
else
{
cout << "\nKey Node not found\n"; } } else { cout << "\nRoot no child"; } } // ================================================ template
void BSearchTree::destroy() const
{
PostOrderDestroy(this->root);
}
// ================================================
template
void BSearchTree::PostOrderDestroy(treeNode *aTreeNode) const
{
if (aTreeNode != 0)
{
if (aTreeNode->leftNode != 0)
{
PostOrderDestroy(aTreeNode->leftNode);
}

if (aTreeNode->rightNode != 0)
{
PostOrderDestroy(aTreeNode->rightNode);
}

delete aTreeNode;
/*
set delete memory to 0
in order to avoid bug
when delete twice happen
*/
aTreeNode = 0;
}
}
// ================================================
template
void BSearchTree::PreOrder() const
{
if (root != 0)
{
cout << "Pre Order Display \n"; RecursivePreOrder(this->root);
}
}
// ================================================
template
void BSearchTree::RecursivePreOrder(treeNode *aTreeNode) const
{
if (aTreeNode != 0)
{
display(aTreeNode);

if (aTreeNode->leftNode != 0)
{
RecursivePreOrder(aTreeNode->leftNode);
}

if (aTreeNode->rightNode != 0)
{
RecursivePreOrder(aTreeNode->rightNode);
}
}
}
// ================================================
template
void BSearchTree::InOrder() const
{
if (root != 0)
{
cout << "In Order Display \n"; RecursiveInOrder(this->root);
}
}
// ================================================
template
void BSearchTree::RecursiveInOrder(treeNode *aTreeNode) const
{
if (aTreeNode != 0)
{
if (aTreeNode->leftNode != 0)
{
RecursiveInOrder(aTreeNode->leftNode);
}

display(aTreeNode);

if (aTreeNode->rightNode != 0)
{
RecursiveInOrder(aTreeNode->rightNode);
}
}
}
// ================================================
template
void BSearchTree::PostOrder() const
{
if (root != 0)
{
cout << "Post Order Display \n"; RecursivePostOrder(this->root);
}
}
// ================================================
template
void BSearchTree::RecursivePostOrder(treeNode *aTreeNode) const
{
if (aTreeNode != 0)
{
if (aTreeNode->leftNode != 0)
{
RecursivePostOrder(aTreeNode->leftNode);
}

if (aTreeNode->rightNode != 0)
{
RecursivePostOrder(aTreeNode->rightNode);
}

display(aTreeNode);
}
}
// ================================================

template
int BSearchTree::size()const
{
int numberNodes = 1;

if (this->root != 0)
{
numberNodes = RecursiveCount(this->root, numberNodes);
}

return numberNodes;
}
// ================================================
template
int BSearchTree::RecursiveCount(treeNode* aTreeNode,
int& numberNodes)const
{
if (aTreeNode != 0)
{
if (aTreeNode->leftNode != 0)
{
numberNodes++;
numberNodes = RecursiveCount(aTreeNode->leftNode, numberNodes);
}

if (aTreeNode->rightNode != 0)
{
numberNodes++;
numberNodes = RecursiveCount(aTreeNode->rightNode, numberNodes);
}
}

return numberNodes;
}
// ================================================
template
T& BSearchTree::minValue()const
{
treeNode* iteratorNode = root;

if (this->root != 0)
{
while(iteratorNode->leftNode != 0)
{
iteratorNode = iteratorNode->leftNode;
}
}

return iteratorNode->value;
}
// ================================================
template
T& BSearchTree::maxValue()const
{
treeNode* iteratorNode = root;

if (this->root != 0)
{
while(iteratorNode->rightNode != 0)
{
iteratorNode = iteratorNode->rightNode;
}
}

return iteratorNode->value;
}
// ================================================
template
int BSearchTree::maxDepth()const
{
int depth = 1, tempHeight = 1;
if (this->root != 0)
{
depth = RecursiveMaxDepth(root, depth, tempHeight);
}
return depth;
}
// ================================================
template
int BSearchTree::RecursiveMaxDepth(const treeNode* aTreeNode,
int& depth, int& tempHeight)const
{
if (aTreeNode != 0)
{
if (aTreeNode->leftNode != 0)
{
tempHeight++;
depth = tempHeight;
depth = RecursiveMaxDepth(aTreeNode->leftNode, depth, tempHeight);
--tempHeight;
}

if (aTreeNode->rightNode != 0)
{
tempHeight++;
depth = tempHeight;
depth = RecursiveMaxDepth(aTreeNode->rightNode, depth, tempHeight);
--tempHeight;
}
}

return depth;
}
// ================================================
template
treeNode* BSearchTree::successor(const T& key)const
{
treeNode* iteratorNode = root;
treeNode* successorNode = root;

while ((key != iteratorNode->key) &&
(iteratorNode->leftNode != 0
|| iteratorNode->rightNode != 0))
{
if (key <>key)
{
iteratorNode = iteratorNode->leftNode;
}
else
{
iteratorNode = iteratorNode->rightNode;
}
}

if (iteratorNode->leftNode != 0)
{
successorNode = iteratorNode->leftNode;
}

if (iteratorNode->rightNode != 0)
{
successorNode = iteratorNode->rightNode;
}

/*
return pointer was allowed here
because the pointee is in heap
Local pointer to pointee
&& references to local variable is
not allowed to return
*/
return successorNode;
}
// ================================================
template
treeNode* BSearchTree::predecessor(const T& key)const
{
treeNode* iteratorNode = root;
treeNode* parent = root;

while ((key != iteratorNode->key) &&
(iteratorNode->leftNode != 0
|| iteratorNode->rightNode != 0))
{
if (key <>key)
{
(iteratorNode->leftNode != 0)
? iteratorNode = iteratorNode->leftNode
: iteratorNode;

(iteratorNode->key != key)
? parent = iteratorNode->leftNode
: parent;
}
else
{
(iteratorNode->rightNode != 0)
? iteratorNode = iteratorNode->rightNode
: iteratorNode;

(iteratorNode->key != key)
? parent = parent->rightNode
: parent;
}
}

/*
return pointer was allowed here
because the pointee is in heap
Local pointer to pointee
&& references to local variable is
not allowed to return
*/
return parent;
}
// ================================================
template
treeNode* BSearchTree::search(const T& key)const
{
treeNode* iteratorNode = root;

while ((iteratorNode->key != key) &&
(iteratorNode->leftNode != 0
|| iteratorNode->rightNode != 0))
{
if (key <>key)
{
(iteratorNode->leftNode != 0)
? iteratorNode = iteratorNode->leftNode
: iteratorNode;
}
else
{
(iteratorNode->rightNode != 0)
? iteratorNode = iteratorNode->rightNode
: iteratorNode;
}
}
/*
return pointer was allowed here
because the pointee is in heap
Local pointer to pointee
&& references to local variable is
not allowed to return
*/
return iteratorNode;
}
// ================================================
template
void BSearchTree::mirrorSwap()const
{
if (this->root != 0)
{
RecursiveMirrorSwap(this->root);
}
}
// ================================================
template
void BSearchTree::RecursiveMirrorSwap(treeNode* aTreeNode)const
{
if (aTreeNode != 0)
{
if (aTreeNode->leftNode != 0)
{
if (aTreeNode->leftNode != 0
|| aTreeNode->rightNode!= 0)
{
treeNode* tempLeftNode = aTreeNode->leftNode;
aTreeNode->leftNode = aTreeNode->rightNode;
aTreeNode->rightNode = tempLeftNode;
}
RecursiveMirrorSwap(aTreeNode->leftNode);
}

if (aTreeNode->rightNode != 0)
{
RecursiveMirrorSwap(aTreeNode->rightNode);
}
}
}
// ================================================
template
void BSearchTree::generatePath()const
{
T valuePath[99];
if (this->root != 0)
{
valuePath[0] = this->root->value;
RecursiveGeneratePaths(this->root, valuePath, 1);
}
}
// ================================================
template
void BSearchTree::RecursiveGeneratePaths(treeNode *aTreeNode,
T valuePath [],
int index)const
{
if (aTreeNode != 0)
{
if (aTreeNode->leftNode == 0
&& aTreeNode->rightNode == 0)
{
displayPath(valuePath, index);
}

if (aTreeNode->leftNode != 0)
{
valuePath[index] = aTreeNode->leftNode->value;
index++;
RecursiveGeneratePaths(aTreeNode->leftNode, valuePath, index);
--index;
/*
Backtracking
Previous stack code here
Return from next stack to
previous stack
*/
}

if (aTreeNode->rightNode != 0)
{
valuePath[index] = aTreeNode->rightNode->value;
index++;
RecursiveGeneratePaths(aTreeNode->rightNode, valuePath, index);
--index;
/*
Backtracking
Previous stack code here
Return from next stack to
previous stack
*/
}
}
}
// ================================================
template
void BSearchTree::displayPath(T valuePath [], int index)const
{
int loop=0;
cout << "\nRoot to Leaf Path is : "; while (loop<<> ";
loop++;
}
}
// =================================================
template
void BSearchTree::doubleTree()
{
/*
std::queue is not itself a container, but
an adaptor (a facade) around a
container offering a limited interface.
Therefore, std::queue does not offer
iterators
*/
std::deque tempTreeKey;
std::deque tempTreeValue;

if (this->root != 0)
{
RecursiveCopy(this->root, tempTreeKey, tempTreeValue);
}

while (!tempTreeKey.empty()
&& !tempTreeValue.empty())
{
doubleTreeInsert(this->root, tempTreeKey, tempTreeValue);

tempTreeKey.pop_front();
tempTreeValue.pop_front();
}
}
// =================================================
template
void BSearchTree::RecursiveCopy(treeNode* aTreeNode,
std::deque& tempTreeKey, std::deque& tempTreeValue)const
{
if (aTreeNode != 0)
{
tempTreeKey.push_back(aTreeNode->key);
tempTreeValue.push_back(aTreeNode->value);

if (aTreeNode->leftNode != 0)
{
RecursiveCopy(aTreeNode->leftNode, tempTreeKey, tempTreeValue);
}

if (aTreeNode->rightNode != 0)
{
RecursiveCopy(aTreeNode->rightNode, tempTreeKey, tempTreeValue);
}
}
}
// ================================================
template
void BSearchTree::doubleTreeInsert(treeNode* aTreeNode,
std::deque& tempTreeKey,
std::deque& tempTreeValue)
{
if (aTreeNode != 0)
{
RecursiveDoubleTreeinsert(aTreeNode,
tempTreeKey, tempTreeValue);
}
}
// ================================================
template
void BSearchTree::RecursiveDoubleTreeinsert(treeNode* aTreeNode,
std::deque& tempTreeKey,
std::deque& tempTreeValue)
{
if (aTreeNode != 0)
{
if (tempTreeKey.front() <= aTreeNode->key)
{
if (aTreeNode->leftNode != 0)
{
RecursiveDoubleTreeinsert(aTreeNode->leftNode,
tempTreeKey, tempTreeValue);
}
else
{
treeNode* newNode = new treeNode(tempTreeKey.front(), tempTreeValue.front());
aTreeNode->leftNode = newNode;
}
}
else
{
if (aTreeNode->rightNode != 0)
{
RecursiveDoubleTreeinsert(aTreeNode->rightNode,
tempTreeKey, tempTreeValue);
}
else
{
treeNode* newNode = new treeNode(tempTreeKey.front(), tempTreeValue.front());
aTreeNode->rightNode = newNode;
}
}
}
}
// ================================================
template
void BSearchTree::display(treeNode* aTreeNode) const
{
cout << "Key is " <<>key << "\n"; cout << "Value is " <<>value << "\n";
}
// ================================================






#else

// POSIX function

#endif



#endif