以下第一个基础类BinTree.h#ifndef _BINTREE_H_
#define _BINTREE_H_class CBinTreeNode;typedef void (*TraverseCallBack)(CBinTreeNode*,void*); 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_
#define _BINTREE_H_class CBinTreeNode;typedef void (*TraverseCallBack)(CBinTreeNode*,void*); 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_
以下为.cpp文件#include "stdafx.h"
#include "BinTree.h"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;}
如何使用它呀，我只看懂了部分，请指教？