二叉排序树的范围检索(100分)

有个搜索的程序要作,想找一个现成的二叉排序树(要求是平衡树)的类实现,
我以前找了一个不过没有范围检索,请高手帮忙,谁提供具体的代码,分就给谁.

哎哟，二叉树我都搞忘了，不过个人认为可能用汇编要好些吧

难道没人做数据结构了吗?

头文件:
#ifndef _BINTREE_H_
#define _BINTREE_H_
class CBinTreeNode;
// TraverseCallBack, a callback function, like
// void somefunction(CBinTreeNode*,void*);

// see CBinTree::Traverse method below.
typedef void (*TraverseCallBack)(CBinTreeNode*,void*);

// CBinTreeNode. The tree is built by CBinTreeNodes.
// To have any real use, you should subclass it to
// a class that actually hold some data
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 else
where.
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 youdo
nt 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.
voiddo
Traverse_Ascending(CBinTreeNode* pNode);
voiddo
Traverse_Descending(CBinTreeNode* pNode);
voiddo
Traverse_ParentFirst(CBinTreeNode* pNode);
voiddo
Traverse_ParentLast(CBinTreeNode* pNode);

// Called by Find.do
es the real work.
CBinTreeNode*do
Traverse_Find(CBinTreeNode* pNode);
// Called by Balance.
void GetFromOrderedArray(int low, int hi);
};
#endif // _BINTREE_H_

实现:
#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:
do
Traverse_Ascending(mRoot);
break;
case Descending:
do
Traverse_Descending(mRoot);
break;
case ParentFirst:
do
Traverse_ParentFirst(mRoot);
break;
case ParentLast:
do
Traverse_ParentLast(mRoot);
break;
default:
ASSERT(FALSE);
}
}
void CBinTree:oTraverse_Ascending(CBinTreeNode* pNode)
{
if (!pNode)
return;
DoTraverse_Ascending(pNode->GetLeftChild());
mFunc(pNode,mParam);
DoTraverse_Ascending(pNode->GetRightChild());
}
void CBinTree:oTraverse_Descending(CBinTreeNode* pNode)
{
if (!pNode)
return;
DoTraverse_Descending(pNode->GetRightChild());
mFunc(pNode,mParam);
DoTraverse_Descending(pNode->GetLeftChild());
}
void CBinTree:oTraverse_ParentFirst(CBinTreeNode* pNode)
{
if (!pNode)
return;
mFunc(pNode,mParam);
DoTraverse_ParentFirst(pNode->GetLeftChild());
DoTraverse_ParentFirst(pNode->GetRightChild());
}
void CBinTree:oTraverse_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;
returndo
Traverse_Find(mRoot);
}
//do
Traverse_Find will, unlike the otherdo
Traverse_xxx, not
// go through _all_ nodes, but stop when node is found or
// is decided can't be found.
CBinTreeNode* CBinTree:oTraverse_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)
returndo
Traverse_Find(node->GetLeftChild());

// node < mpSearchNode, look if it is by the right
// if (iComp < 0)
returndo
Traverse_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 (easilydo
ne).
// We will put 'em back soon enough.
CBinTree::Clear();

// Reset the nodes so theydo
n'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->SetLeftChild(NULL);
mBalArray->SetRightChild(NULL);
mBalArray->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;
}
//do
Balance.
// 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 Insertdo
esnt
// 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 todo
stuff to the removed node.
OnRemoveNode(pNode);
return TRUE;
}

to leechange:
有没有DELPHI的,C++的用不上,我又不熟悉C++,翻译不过来,另外,我看了一下公有方法
里好象没有范围检索,只有值检索,你要是能帮我翻译到DELPHI,再另送100大洋,谢谢

用decal试试看，提供平衡树的实现（红黑树）。可以上sourceforge.net下载。

多人接受答案了。