BOOL CBinTree::RemoveNode(CBinTreeNode* pSearchNode) { CBinTreeNode* pNode = Find(pSearchNode); if (!pNode) return FALSE; int iCount = mCount;
CBinTreeNode* pParent = pNode->GetParent(); // Ok, so it has a parent, then we'll simply just disconnect it. if (pParent) { if (pParent->GetLeftChild() == pNode) { pParent->SetLeftChild(NULL); } else { ASSERT(pParent->GetRightChild() == pNode); pParent->SetRightChild(NULL); } } else { // No parent? Then we're deleting the root node. ASSERT(pNode == mRoot); mRoot = NULL; } // Disconnected, now we reconnect its children (if any) // just by adding them as we add any other node. Their // respective children will come along, since Insert doesnt // tamper with the inserted node's children. if (pNode->GetLeftChild()) Insert(pNode->GetLeftChild()); if (pNode->GetRightChild()) Insert(pNode->GetRightChild()); mCount = iCount-1; // Give the subclass a chance to do stuff to the removed node. OnRemoveNode(pNode); return TRUE;}
void CBinTree::Insert(CBinTreeNode* pNode) { if (mRoot==NULL) { mRoot = pNode; mCount = 1; mHeight = 1; mRoot->SetParent(NULL); } else { mHeightTmp = 1; InsertBelow(mRoot,pNode); mCount++; if (mHeightTmp>mHeight) mHeight = mHeightTmp; }}void CBinTree::InsertBelow(CBinTreeNode* mParent,CBinTreeNode* mNewNode) { int i = Compare(mNewNode,mParent); mHeightTmp++; switch(i) { case -1: // mNewNode < mParent if (mParent->GetLeftChild()==NULL) { // No left child? Okie then, mNewNode is the new left child mParent->SetLeftChild(mNewNode); mNewNode->SetParent(mParent); } else { InsertBelow(mParent->GetLeftChild(),mNewNode); }; break; case 0: case 1: // mNewNode >= mParent if (mParent->GetRightChild()==NULL) { // No right child? Okie then, mNewNode is the new right child mParent->SetRightChild(mNewNode); mNewNode->SetParent(mParent); } else { InsertBelow(mParent->GetRightChild(),mNewNode); }; break; default: ASSERT(FALSE); }; }void CBinTree::Traverse(TraverseOrder to, TraverseCallBack func, void* pParam) { mFunc = func; mParam = pParam; switch(to) { case Ascending: DoTraverse_Ascending(mRoot); break; case Descending: DoTraverse_Descending(mRoot); break; case ParentFirst: DoTraverse_ParentFirst(mRoot); break; case ParentLast: DoTraverse_ParentLast(mRoot); break; default: ASSERT(FALSE); }}void CBinTree::DoTraverse_Ascending(CBinTreeNode* pNode) { if (!pNode) return; DoTraverse_Ascending(pNode->GetLeftChild()); mFunc(pNode,mParam); DoTraverse_Ascending(pNode->GetRightChild()); }void CBinTree::DoTraverse_Descending(CBinTreeNode* pNode) { if (!pNode) return; DoTraverse_Descending(pNode->GetRightChild()); mFunc(pNode,mParam); DoTraverse_Descending(pNode->GetLeftChild()); }void CBinTree::DoTraverse_ParentFirst(CBinTreeNode* pNode) { if (!pNode) return; mFunc(pNode,mParam); DoTraverse_ParentFirst(pNode->GetLeftChild()); DoTraverse_ParentFirst(pNode->GetRightChild()); }void CBinTree::DoTraverse_ParentLast(CBinTreeNode* pNode) { if (!pNode) return; DoTraverse_ParentLast(pNode->GetLeftChild()); DoTraverse_ParentLast(pNode->GetRightChild()); mFunc(pNode,mParam); }CBinTreeNode* CBinTree::Find(CBinTreeNode* pSearchNode) { mpSearchNode = pSearchNode; mComparisons = 0; return DoTraverse_Find(mRoot); }// DoTraverse_Find will, unlike the other DoTraverse_xxx, not // go through _all_ nodes, but stop when node is found or // is decided can't be found.CBinTreeNode* CBinTree::DoTraverse_Find(CBinTreeNode* node) { // Reached a dead end, node couldn't be found. if (!node) return NULL; mComparisons++; int iComp = Compare(node,mpSearchNode); // Found the node we were looking for, return it. if (iComp == 0) return node; // node > mpSearchNode, look if it is by the left if (iComp > 0) return DoTraverse_Find(node->GetLeftChild());
// node < mpSearchNode, look if it is by the right // if (iComp < 0) return DoTraverse_Find(node->GetRightChild()); }// tcb_Balance: TraverseCallBack // Add the node into the array. // pParam is the tree (so we can get the array) void tcb_Balance(CBinTreeNode* pNode,void* pParam) { CBinTree* pTree = (CBinTree*) pParam; pTree->mBalArray[pTree->mBalArrayCount] = pNode; pTree->mBalArrayCount++; }// Bring balance to the force. void CBinTree::Balance() { // Setup an array that will hold the nodes mBalArray = new CBinTreeNode*[mCount]; mBalArrayCount=0; // Put the nodes into the array in ascending order (ie sorted) Traverse(Ascending,tcb_Balance,this); // Clarifying the array now holds all the elements ASSERT(mCount == mBalArrayCount); // Remove the nodes from the tree (easily done). // We will put 'em back soon enough. CBinTree::Clear(); // Reset the nodes so they don't have any children, // they will be given new as nodes get inserted back into to the tree. for (int i=0;i<mBalArrayCount;i++) { mBalArray[i]->SetLeftChild(NULL); mBalArray[i]->SetRightChild(NULL); mBalArray[i]->SetParent(NULL); } // Insert the nodes back to the tree in a balanced fashion. GetFromOrderedArray(0,mBalArrayCount-1); // Clarifying all elements have been inserted back from the array ASSERT(mCount == mBalArrayCount); delete mBalArray; }// DoBalance. // Insert the node in the middle position between // low and hi from the mBalArray array. // Recurse and the array elements < middlePos and > middlePos. void CBinTree::GetFromOrderedArray(int low, int hi) { if (hi<low) return; int middlePos; middlePos = low+(hi-low)/2; Insert(mBalArray[middlePos]); GetFromOrderedArray(low,middlePos-1); GetFromOrderedArray(middlePos+1,hi); }BOOL CBinTree::RemoveNode(CBinTreeNode* pSearchNode) { CBinTreeNode* pNode = Find(pSearchNode); if (!pNode) return FALSE; int iCount = mCount;
CBinTreeNode* pParent = pNode->GetParent(); // Ok, so it has a parent, then we'll simply just disconnect it. if (pParent) { if (pParent->GetLeftChild() == pNode) { pParent->SetLeftChild(NULL); } else { ASSERT(pParent->GetRightChild() == pNode); pParent->SetRightChild(NULL); } } else { // No parent? Then we're deleting the root node. ASSERT(pNode == mRoot); mRoot = NULL; } // Disconnected, now we reconnect its children (if any) // just by adding them as we add any other node. Their // respective children will come along, since Insert doesnt // tamper with the inserted node's children. if (pNode->GetLeftChild()) Insert(pNode->GetLeftChild()); if (pNode->GetRightChild()) Insert(pNode->GetRightChild()); mCount = iCount-1; // Give the subclass a chance to do stuff to the removed node. OnRemoveNode(pNode); return TRUE;}
class CBinTreeNode { CBinTreeNode* mLeftChild; CBinTreeNode* mRightChild; // The node also has a pointer to its parent (NULL for the // root node). This is to make deletion a bit easier, but // technically you could live without it since it is a bit redundant // information. CBinTreeNode* mParent; public: // Constructor CBinTreeNode():mLeftChild(NULL),mRightChild(NULL),mParent(NULL){} // Get methods CBinTreeNode* GetLeftChild() const { return mLeftChild; } CBinTreeNode* GetRightChild() const { return mRightChild; } CBinTreeNode* GetParent() const { return mParent; } // Set methods void SetLeftChild(CBinTreeNode* p) { mLeftChild=p; } void SetRightChild(CBinTreeNode* p) { mRightChild=p; } void SetParent(CBinTreeNode* p) { mParent=p; } };// CBinTree. Holder of the tree structure. Must be subclassed, // has a method, Compare, that's pure virtual and thus must // be defined elsewhere. class CBinTree { // The top node. NULL if empty. CBinTreeNode* mRoot; // Used in traversing TraverseCallBack mFunc; void* mParam; CBinTreeNode* mpSearchNode; int mComparisons; int mCount; int mHeight; int mHeightTmp;public: // TraverseOrder. Input parameter to the Traverse function. // Specifies in what way the tree should be traversed. // Ascending : 1,2,3,4,5.... // Descedning : 9,8,7,6,5.... // ParentFirst : The parent node will be handeled before its children. // Typically use when the structure is saved, so that // the (possibly balanced) structure wont be altered. // ParentLast : The parent node will be handeled after its children. // Typically use when tree is deleted; got to delete the // children before deleting their parent. enum TraverseOrder { Ascending=0,Descending,ParentFirst,ParentLast }; // Constructor. CBinTree():mRoot(NULL),mComparisons(0),mCount(0),mHeight(0){} // Insert. Adds a node to the tree at the right place. void Insert(CBinTreeNode* pNode); // Return the first CBinTreeNode in the tree where // Compare (node,pSearchNode)==0, or NULL if not found. CBinTreeNode* Find(CBinTreeNode* pSearchNode); // Remove a node.Return non-zero if the node could // be found in the tree. // The first node where Compare (node,pSearchNode)==0 // gets zapped. BOOL RemoveNode(CBinTreeNode* pSearchNode); // Returns the number of comparisons required for the last // call to Find. Gives a hint on how balanced the tree is. int GetComparisons() const { return mComparisons; } // Traverse will call the supplied function, func, for every node in the tree, // passing it a pointer to the node, so you can act opon it. // func: The callback function, like void somefunction(CBinTreeNode*,void*); // The pParam will also be passed to the function and is a pointer to something. // You decide to what, or ignore if you dont need it. void Traverse(TraverseOrder to, TraverseCallBack func, void* pParam=NULL); // Number of nodes in the tree. int GetCount() const { return mCount; } // The height of the tree, indicates how balanced it is. // The height is the maximum number of comparisons needed to be // made (worst case) when searching for an element. int GetHeight() const { return mHeight; } // Balance minimizes the height, optimizing it. void Balance(); // These two thingies are temp. stuff used in balancing. CBinTreeNode** mBalArray; // Array of pointers to nodes int mBalArrayCount; protected: // Compare: // p1 < p2 shall return -1 // p1 = p2 shall return 0 // p1 > p2 shall return 1 // You have to redefine it in a subclass, CBinTree can't know // what data is significant for comparison in your node virtual int Compare(CBinTreeNode* p1,CBinTreeNode* p2) const = 0; // Remove all nodes without deleting them. // Not really hard now is it. virtual void Clear() { mRoot = NULL; mCount=0;mHeight=0;} // Override if you want to take some special actions when a // node gets removed from the tree. virtual void OnRemoveNode(CBinTreeNode* pNode) {};
// Called by Insert. void InsertBelow(CBinTreeNode* pParent,CBinTreeNode* pNewNode); // Called by Traverse. All similar except for the order in which they call the children. void DoTraverse_Ascending(CBinTreeNode* pNode); void DoTraverse_Descending(CBinTreeNode* pNode); void DoTraverse_ParentFirst(CBinTreeNode* pNode); void DoTraverse_ParentLast(CBinTreeNode* pNode); // Called by Find. Does the real work. CBinTreeNode* DoTraverse_Find(CBinTreeNode* pNode); // Called by Balance. void GetFromOrderedArray(int low, int hi); }; #endif // _BINTREE_H_
{
CBinTreeNode* pNode = Find(pSearchNode);
if (!pNode)
return FALSE; int iCount = mCount;
CBinTreeNode* pParent = pNode->GetParent(); // Ok, so it has a parent, then we'll simply just disconnect it.
if (pParent)
{
if (pParent->GetLeftChild() == pNode)
{
pParent->SetLeftChild(NULL);
}
else
{
ASSERT(pParent->GetRightChild() == pNode);
pParent->SetRightChild(NULL);
}
}
else
{
// No parent? Then we're deleting the root node.
ASSERT(pNode == mRoot);
mRoot = NULL;
} // Disconnected, now we reconnect its children (if any)
// just by adding them as we add any other node. Their
// respective children will come along, since Insert doesnt
// tamper with the inserted node's children.
if (pNode->GetLeftChild())
Insert(pNode->GetLeftChild());
if (pNode->GetRightChild())
Insert(pNode->GetRightChild()); mCount = iCount-1; // Give the subclass a chance to do stuff to the removed node.
OnRemoveNode(pNode);
return TRUE;}
{
if (mRoot==NULL)
{
mRoot = pNode;
mCount = 1;
mHeight = 1;
mRoot->SetParent(NULL);
}
else
{
mHeightTmp = 1;
InsertBelow(mRoot,pNode);
mCount++; if (mHeightTmp>mHeight)
mHeight = mHeightTmp;
}}void CBinTree::InsertBelow(CBinTreeNode* mParent,CBinTreeNode* mNewNode)
{
int i = Compare(mNewNode,mParent);
mHeightTmp++;
switch(i)
{
case -1:
// mNewNode < mParent
if (mParent->GetLeftChild()==NULL)
{
// No left child? Okie then, mNewNode is the new left child
mParent->SetLeftChild(mNewNode);
mNewNode->SetParent(mParent);
}
else
{
InsertBelow(mParent->GetLeftChild(),mNewNode);
};
break;
case 0:
case 1:
// mNewNode >= mParent
if (mParent->GetRightChild()==NULL)
{
// No right child? Okie then, mNewNode is the new right child
mParent->SetRightChild(mNewNode);
mNewNode->SetParent(mParent);
}
else
{
InsertBelow(mParent->GetRightChild(),mNewNode);
};
break;
default:
ASSERT(FALSE);
};
}void CBinTree::Traverse(TraverseOrder to, TraverseCallBack func, void* pParam)
{
mFunc = func;
mParam = pParam; switch(to)
{
case Ascending:
DoTraverse_Ascending(mRoot);
break;
case Descending:
DoTraverse_Descending(mRoot);
break;
case ParentFirst:
DoTraverse_ParentFirst(mRoot);
break;
case ParentLast:
DoTraverse_ParentLast(mRoot);
break;
default:
ASSERT(FALSE);
}}void CBinTree::DoTraverse_Ascending(CBinTreeNode* pNode)
{
if (!pNode)
return; DoTraverse_Ascending(pNode->GetLeftChild());
mFunc(pNode,mParam);
DoTraverse_Ascending(pNode->GetRightChild());
}void CBinTree::DoTraverse_Descending(CBinTreeNode* pNode)
{
if (!pNode)
return; DoTraverse_Descending(pNode->GetRightChild());
mFunc(pNode,mParam);
DoTraverse_Descending(pNode->GetLeftChild());
}void CBinTree::DoTraverse_ParentFirst(CBinTreeNode* pNode)
{
if (!pNode)
return; mFunc(pNode,mParam);
DoTraverse_ParentFirst(pNode->GetLeftChild());
DoTraverse_ParentFirst(pNode->GetRightChild());
}void CBinTree::DoTraverse_ParentLast(CBinTreeNode* pNode)
{
if (!pNode)
return; DoTraverse_ParentLast(pNode->GetLeftChild());
DoTraverse_ParentLast(pNode->GetRightChild());
mFunc(pNode,mParam);
}CBinTreeNode* CBinTree::Find(CBinTreeNode* pSearchNode)
{
mpSearchNode = pSearchNode;
mComparisons = 0;
return DoTraverse_Find(mRoot);
}// DoTraverse_Find will, unlike the other DoTraverse_xxx, not
// go through _all_ nodes, but stop when node is found or
// is decided can't be found.CBinTreeNode* CBinTree::DoTraverse_Find(CBinTreeNode* node)
{
// Reached a dead end, node couldn't be found.
if (!node)
return NULL; mComparisons++;
int iComp = Compare(node,mpSearchNode); // Found the node we were looking for, return it.
if (iComp == 0)
return node; // node > mpSearchNode, look if it is by the left
if (iComp > 0)
return DoTraverse_Find(node->GetLeftChild());
// node < mpSearchNode, look if it is by the right
// if (iComp < 0)
return DoTraverse_Find(node->GetRightChild());
}// tcb_Balance: TraverseCallBack
// Add the node into the array.
// pParam is the tree (so we can get the array)
void tcb_Balance(CBinTreeNode* pNode,void* pParam)
{
CBinTree* pTree = (CBinTree*) pParam;
pTree->mBalArray[pTree->mBalArrayCount] = pNode;
pTree->mBalArrayCount++;
}// Bring balance to the force.
void CBinTree::Balance()
{
// Setup an array that will hold the nodes
mBalArray = new CBinTreeNode*[mCount];
mBalArrayCount=0; // Put the nodes into the array in ascending order (ie sorted)
Traverse(Ascending,tcb_Balance,this); // Clarifying the array now holds all the elements
ASSERT(mCount == mBalArrayCount); // Remove the nodes from the tree (easily done).
// We will put 'em back soon enough.
CBinTree::Clear();
// Reset the nodes so they don't have any children,
// they will be given new as nodes get inserted back into to the tree.
for (int i=0;i<mBalArrayCount;i++)
{
mBalArray[i]->SetLeftChild(NULL);
mBalArray[i]->SetRightChild(NULL);
mBalArray[i]->SetParent(NULL);
} // Insert the nodes back to the tree in a balanced fashion.
GetFromOrderedArray(0,mBalArrayCount-1); // Clarifying all elements have been inserted back from the array
ASSERT(mCount == mBalArrayCount); delete mBalArray;
}// DoBalance.
// Insert the node in the middle position between
// low and hi from the mBalArray array.
// Recurse and the array elements < middlePos and > middlePos.
void CBinTree::GetFromOrderedArray(int low, int hi)
{ if (hi<low)
return; int middlePos;
middlePos = low+(hi-low)/2; Insert(mBalArray[middlePos]); GetFromOrderedArray(low,middlePos-1);
GetFromOrderedArray(middlePos+1,hi);
}BOOL CBinTree::RemoveNode(CBinTreeNode* pSearchNode)
{
CBinTreeNode* pNode = Find(pSearchNode);
if (!pNode)
return FALSE; int iCount = mCount;
CBinTreeNode* pParent = pNode->GetParent(); // Ok, so it has a parent, then we'll simply just disconnect it.
if (pParent)
{
if (pParent->GetLeftChild() == pNode)
{
pParent->SetLeftChild(NULL);
}
else
{
ASSERT(pParent->GetRightChild() == pNode);
pParent->SetRightChild(NULL);
}
}
else
{
// No parent? Then we're deleting the root node.
ASSERT(pNode == mRoot);
mRoot = NULL;
} // Disconnected, now we reconnect its children (if any)
// just by adding them as we add any other node. Their
// respective children will come along, since Insert doesnt
// tamper with the inserted node's children.
if (pNode->GetLeftChild())
Insert(pNode->GetLeftChild());
if (pNode->GetRightChild())
Insert(pNode->GetRightChild()); mCount = iCount-1; // Give the subclass a chance to do stuff to the removed node.
OnRemoveNode(pNode);
return TRUE;}
{
CBinTreeNode* mLeftChild;
CBinTreeNode* mRightChild; // The node also has a pointer to its parent (NULL for the
// root node). This is to make deletion a bit easier, but
// technically you could live without it since it is a bit redundant
// information.
CBinTreeNode* mParent;
public:
// Constructor
CBinTreeNode():mLeftChild(NULL),mRightChild(NULL),mParent(NULL){} // Get methods
CBinTreeNode* GetLeftChild() const { return mLeftChild; }
CBinTreeNode* GetRightChild() const { return mRightChild; }
CBinTreeNode* GetParent() const { return mParent; } // Set methods
void SetLeftChild(CBinTreeNode* p) { mLeftChild=p; }
void SetRightChild(CBinTreeNode* p) { mRightChild=p; }
void SetParent(CBinTreeNode* p) { mParent=p; }
};// CBinTree. Holder of the tree structure. Must be subclassed,
// has a method, Compare, that's pure virtual and thus must
// be defined elsewhere.
class CBinTree
{
// The top node. NULL if empty.
CBinTreeNode* mRoot; // Used in traversing
TraverseCallBack mFunc;
void* mParam;
CBinTreeNode* mpSearchNode; int mComparisons;
int mCount;
int mHeight;
int mHeightTmp;public:
// TraverseOrder. Input parameter to the Traverse function.
// Specifies in what way the tree should be traversed.
// Ascending : 1,2,3,4,5....
// Descedning : 9,8,7,6,5....
// ParentFirst : The parent node will be handeled before its children.
// Typically use when the structure is saved, so that
// the (possibly balanced) structure wont be altered.
// ParentLast : The parent node will be handeled after its children.
// Typically use when tree is deleted; got to delete the
// children before deleting their parent.
enum TraverseOrder { Ascending=0,Descending,ParentFirst,ParentLast }; // Constructor.
CBinTree():mRoot(NULL),mComparisons(0),mCount(0),mHeight(0){} // Insert. Adds a node to the tree at the right place.
void Insert(CBinTreeNode* pNode); // Return the first CBinTreeNode in the tree where
// Compare (node,pSearchNode)==0, or NULL if not found.
CBinTreeNode* Find(CBinTreeNode* pSearchNode); // Remove a node.Return non-zero if the node could
// be found in the tree.
// The first node where Compare (node,pSearchNode)==0
// gets zapped.
BOOL RemoveNode(CBinTreeNode* pSearchNode); // Returns the number of comparisons required for the last
// call to Find. Gives a hint on how balanced the tree is.
int GetComparisons() const { return mComparisons; } // Traverse will call the supplied function, func, for every node in the tree,
// passing it a pointer to the node, so you can act opon it.
// func: The callback function, like void somefunction(CBinTreeNode*,void*);
// The pParam will also be passed to the function and is a pointer to something.
// You decide to what, or ignore if you dont need it.
void Traverse(TraverseOrder to, TraverseCallBack func, void* pParam=NULL); // Number of nodes in the tree.
int GetCount() const { return mCount; } // The height of the tree, indicates how balanced it is.
// The height is the maximum number of comparisons needed to be
// made (worst case) when searching for an element.
int GetHeight() const { return mHeight; } // Balance minimizes the height, optimizing it.
void Balance(); // These two thingies are temp. stuff used in balancing.
CBinTreeNode** mBalArray; // Array of pointers to nodes
int mBalArrayCount; protected:
// Compare:
// p1 < p2 shall return -1
// p1 = p2 shall return 0
// p1 > p2 shall return 1
// You have to redefine it in a subclass, CBinTree can't know
// what data is significant for comparison in your node
virtual int Compare(CBinTreeNode* p1,CBinTreeNode* p2) const = 0; // Remove all nodes without deleting them.
// Not really hard now is it.
virtual void Clear() { mRoot = NULL; mCount=0;mHeight=0;} // Override if you want to take some special actions when a
// node gets removed from the tree.
virtual void OnRemoveNode(CBinTreeNode* pNode) {};
// Called by Insert.
void InsertBelow(CBinTreeNode* pParent,CBinTreeNode* pNewNode); // Called by Traverse. All similar except for the order in which they call the children.
void DoTraverse_Ascending(CBinTreeNode* pNode);
void DoTraverse_Descending(CBinTreeNode* pNode);
void DoTraverse_ParentFirst(CBinTreeNode* pNode);
void DoTraverse_ParentLast(CBinTreeNode* pNode);
// Called by Find. Does the real work.
CBinTreeNode* DoTraverse_Find(CBinTreeNode* pNode); // Called by Balance.
void GetFromOrderedArray(int low, int hi);
};
#endif // _BINTREE_H_