|
|
#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__
////////////////////////////////////////////////////////////////////////////////////////////////////////
// Author A.Milev
// Email amil@abv.bg
// Implementation of binary tree
// to use it just include this header to your project
////////////////////////////////////////////////////////////////////////////////////////////////////////
//if you work with negative numbers should change it:
#define INVALID_VALUE -1
//Binary Tree Node
template <class Xtype>
class BTNode
{
public:
BTNode();
BTNode(Xtype x);
bool Delete_Tree(BTNode<Xtype>* Root);
BTNode(BTNode<Xtype>* k1, BTNode<Xtype>* k2);
BTNode<Xtype> *Left, *Right, *Parent;
BTNode<Xtype>* place(BTNode<Xtype>* T);
BTNode<Xtype>* insert( Xtype x);
bool insert( BTNode<Xtype>* node );
void remove();
/////////////////// balancing ////////////////////////////////////////////
int count_childs();
BTNode<Xtype>* FillLeft(bool FatherOrientation);
BTNode<Xtype>* FillRight(bool FatherOrientation);
BTNode<Xtype>* MoveRight(bool FatherOrientation) ;
BTNode<Xtype>* MoveLeft(bool FatherOrientation) ;
BTNode<Xtype>* Balance(int max_depth, bool FatherOrientation);
Xtype x;
//////////////////////////////////////////////////////////////////////////
};
// constructors
template <class Xtype>
BTNode<Xtype>::BTNode()
{
Left = NULL;
Right = NULL;
Parent = NULL;
}
template <class Xtype>
BTNode<Xtype>::BTNode(BTNode<Xtype>* k1, BTNode<Xtype>* k2)
{
Left = k1;
Right = k2;
Parent = NULL;
}
template <class Xtype>
BTNode<Xtype>::BTNode(Xtype xKey)
{
Left = NULL;
Right = NULL;
Parent = NULL;
x = xKey;
}
//places x to left or right of the node
template <class Xtype>
BTNode<Xtype>* BTNode<Xtype>::place (BTNode<Xtype>* x)
{
if(x < xKey)
return Left;
else
return Right;
}
template <class Xtype>
void BTNode<Xtype>::remove()
{
BTNode<Xtype>* pLeft = Left;
BTNode<Xtype>* pRight = Right;
delete this;
if(pLeft) pLeft->remove();
if(pRight)pRight->remove();
}
template <class Xtype>
int BTNode<Xtype>::count_childs()
{
int nChilds = 1;
if(Left) nChilds+= Left->count_childs();
if(Right) nChilds+= Right->count_childs() ;
return nChilds ;
}
/* Reorder childs and make sure that there is a neighbour on the left
P P
/ \ / \
L -> LR
/ \ / \
0 LR ...........
/ \ /
......... L
*/
template <class Xtype>
BTNode<Xtype>* BTNode<Xtype>::FillLeft(bool FatherOrientation)
{
if(Left)
return this ; //no need of this routine!
if(!Right) //LR is 0! something is wrong, this is a end node without childs!
return false;
if(Parent)
{
Right->Parent = Parent ;
FatherOrientation? Parent->Left = Right : Parent->Right = Right ;
}
//search down a new place for L
BTNode<Xtype>* pNext = Right; //Right now is LR!
while(pNext->Left)
pNext = pNext->Left ;
pNext->Left = this ;
Parent = pNext ;
BTNode<Xtype>* LR = Right ;
Left = Right = NULL ;
return LR;// balance may continue
}
/* Reorder childs and make sure that there is a neighbour on the right
P P
\ / \
R -> RL
/ \ \
RL 0 ...........
/ \ \
......... R
FatherOrientation - because Parent link do not tells in which direction
Left or Right is the node wrt its parent, orientation is given as parameter
*/
template <class Xtype>
BTNode<Xtype>* BTNode<Xtype>::FillRight(bool FatherOrientation)
{
if(Right)
return this ; //no need of this routine!
if(!Left) //RL is 0! something is wrong, this is a end node without childs!
return NULL;
if(Parent)
{
Left->Parent = Parent ;
FatherOrientation? Parent->Left = Left : Parent->Right = Left ;
}
//search down a new place for L
BTNode<Xtype>* pNext = Left; //Left now is RL!
while(pNext->Right)
pNext = pNext->Right ;
pNext->Right = this ;
Parent = pNext ;
BTNode<Xtype>* RL = Left ;
Left = Right = NULL ;
return RL;// balance may continue
}
/* Reorder tree , increase number of childs on the right,
FillLeft() and FillRight() assure that P has L and R different then NULL
P L
/ \ / \
L R -> LL LR
/ \ / \ / \ / \
LL LR RL .......... R.
/ \ / / \
......... RL RR
/
P
FatherOrientation - because pParent link do not tells in which direction
Left or Right wrt parent, it is given as parameter
*/
template <class Xtype>
BTNode<Xtype>* BTNode<Xtype>::MoveRight(bool FatherOrientation)
{
if(!Left) //Root can not be NULL
return NULL;
if(Parent)
{
Left->Parent = Parent ;
FatherOrientation? Parent->Left = Left : Parent->Right = Left ;
}
BTNode<Xtype>* pNext = Left; //Left is now at the place of P
while(pNext->Right)
pNext = pNext->Right;
if(Right) //search place for R
{
pNext->Right = Right ;
Right->Parent = pNext;
}
else //search place for P
{
pNext->Right = this ;
Parent = pNext ;
Left = NULL ;
Right = NULL ;
return true ;
}
pNext = Right; //search place for P
while(pNext->Left)
pNext = pNext->Left;
pNext->Left = this ;
Parent = pNext ;
BTNode<Xtype>* L = Left;
Left = Right = NULL ;
return L;// re-placing of left to right may continue
}
/* Reorder tree , increase the number of childs on left,with 2
FillLeft() and FillRight() assure that P has L and R different then NULL
P R
/ \ / \
L R -> RL RR
/ \ / \ / \ / \
LL LR RL RR L. .
/ \ / / \
......... LL LR
\
P
FatherOrientation - because pParent link do not tells in which direction
Left or Right wrt parent, it is given as parameter
*/
template <class Xtype>
BTNode<Xtype>* BTNode<Xtype>::MoveLeft(bool FatherOrientation)
{
if(!Right) //Root can not be NULL
return NULL;
if(Parent)
{
Right->Parent = Parent ;
FatherOrientation? Parent->Left = Right : Parent->Right = Right ;
}
BTNode<Xtype>* pNext = Right; //Left is now at the place of P
while(pNext->Left)
pNext = pNext->Left;
if(Left) //search place for L
{
pNext->Left = Left ;
Left->Parent = pNext;
}
else //search place for P
{
pNext->Left = this ;
Parent = pNext ;
Left = NULL ;
Right = NULL ;
return true ;
}
pNext = Left; //search place for P
while(pNext->Right)
pNext = pNext->Right;
pNext->Right = this ;
Parent = pNext ;
BTNode<Xtype>* R = Right ;
Left = NULL ;
Right = NULL ;
return R;// re-placing of left to right may continue
}
template <class Xtype>
BTNode<Xtype>* BTNode<Xtype>::Balance(int depth, bool FatherOrientation)
{
int N = 0; //the number of replaced nodes
int nChildsLeft = 0;
int nChildsRight = 0;
if(Left)
nChildsLeft = Left->count_childs();
if(Right)
nChildsRight = Right->count_childs();
int nDiff = abs(nChildsRight - nChildsLeft);
if(nDiff<=2)
return this;
BTNode<Xtype> *pNext, *Root ;
BTNode<Xtype> *pOrgParent = Parent ;
Root = this ;
if(nChildsRight - nChildsLeft >= 2)//move tree left
{
for(int n=0; n<nDiff/2; n++)
{
if( !Root->Right)
{
if(!(pNext = Root->FillRight(1)))
return Root ;
Root = pNext ;
}
if(!(pNext = MoveLeft(1, FatherOrientation)))
return Root ;
}
}
return Root ;
}
//delete from memory the whole tree
template <class Xtype>
bool Delete_Tree(BTNode<Xtype>* &Root)
{
if(Root)
Root->remove();
Root = NULL;
return true;
}
//insert node to the tree, starts from current node
template <class Xtype>
bool
BTNode<Xtype>::insert( BTNode<Xtype>* node )
{
BTNode<Xtype>* pNext = this;
BTNode<Xtype>* pFather;
while(pNext) //do not insert if already exist
{
pFather = pNext;
if(node->x < pNext->x)
pNext = pNext->Left;
else if(node->x > pNext->x)
pNext = pNext->Right;
else
return 0;
}
if(!pNext) //empty place, do not insert value twice
{
node->Parent = pFather;
if(node->x < pFather->x)
{
pFather->Left = node;
}
else
{
pFather->Right = node;
}
return 1;
}
return 0;
}
//create and insert node to the tree, starts from current node
template <class Xtype>
BTNode<Xtype>*
BTNode<Xtype>::insert( Xtype x)
{
BTNode<Xtype>* node = new BTNode<Xtype>(x);
if(!insert(node))
{
delete node;
return NULL;
}
else
return node;
}
//add node to the tree
template <class Xtype>
BTNode<Xtype>* append(BTNode<Xtype>* &Root, Xtype X)
{
if(!Root)
{
Root = new BTNode<Xtype>(X);
return Root;
}
else
return Root->insert(X);
}
//finds if exact match exist
template <class Xtype>
bool exist(BTNode<Xtype>* Root, Xtype x)
{
BTNode<Xtype>* pNext = Root;
BTNode<Xtype>* pFather;
while(pNext)
{
pFather = pNext;
if(x<pNext->x)
pNext = pNext->Left;
else if(x>pNext->x)
pNext = pNext->Right;
else
return 1;
}
return 0;
}
/* nearest neighbour search
input:
Root - the root of the tree
output:
l - the left limiting value or INVALID_VALUE if there is no neighbour to left
r - the right limiting value or INVALID_VALUE if there is no neighbour to right
returns:
- the closest value to x
- INVALID_VALUE - empty tree
*/
template <class Xtype>
Xtype FindNearest(BTNode<Xtype>* Root, Xtype x, Xtype* l, Xtype* r)
{
float left,right;
BTNode<Xtype>* pNext = Root;
BTNode<Xtype>* pFather;
while(pNext)
{
pFather = pNext;
if(x<pNext->x)
pNext = pNext->Left;
else if(x>pNext->x)
pNext = pNext->Right;
else
{
*l = pNext->x;
*r = pNext->x;
return pNext->x;
}
}
if(x<pFather->x)
{
right = pFather->x;
//search for the left limit, go up in the tree
while(pFather && pFather->x > x)
{
pFather = pFather->Parent;
}
if(!pFather)
{
*l = INVALID_VALUE; //no neighbour to the left
*r = right;
return right;
}
else
{
*l = pFather->x;
*r = right;
return (x-pFather->x < right-x ? pFather->x:right);
}
}
else if(x>pFather->x)
{
left = pFather->x;
//search for the left limit, go up in the tree
while(pFather && pFather->x < x)
{
pFather = pFather->Parent;
}
if(!pFather)
{
*l = left;
*r = INVALID_VALUE; //no neighbour to the right
return left;
}
else
{
*l = left;
*r = pFather->x;
return (x-left < pFather->x-x ? left:pFather->x);;
}
}
return INVALID_VALUE;
}
#endif
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.
Submit an article or tip