可用分押宝游戏火热进行中...	专题改版：Java Web 专题

关于二叉表算法类的问题？请各位关注一下吧，都有分哦

楼主dzds（天涯人）2004-05-01 22:31:33 在 VC/MFC / 图形处理/算法提问

以下第一个基础类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_
问题点数：50、回复次数：11Top

1 楼dzds（天涯人）回复于 2004-05-01 22:31:47 得分 0

以下为.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;

}
如何使用它呀，我只看懂了部分，请指教？Top

2 楼dzds（天涯人）回复于 2004-05-02 20:50:44 得分 0

自己顶，怎么没人来呀，真是悲哀Top

3 楼fyjin99（老饭）回复于 2004-05-03 10:00:55 得分 10

老兄这种东西看起来是很头疼的，你将你不懂的问题提炼出来再问。帮你顶顶！！Top

4 楼dzds（天涯人）回复于 2004-05-03 11:27:32 得分 0

这是一个二叉表的类。我主要是想如何在自已的程序中应用于它。即查找结点，并把结点中的信息读出来，先谢谢fyjin99(老饭)Top

5 楼dzds（天涯人）回复于 2004-05-05 11:54:24 得分 0

再顶，进者都有分哦Top

6 楼dzds（天涯人）回复于 2004-05-09 23:06:12 得分 0

顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶
顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶，顶Top

7 楼yj198261（蓝色街灯）回复于 2004-05-10 08:31:59 得分 10

那程序的问题是出在哪儿啊！？Top

8 楼lifengnm（我还是菜鸟）回复于 2004-05-10 08:43:12 得分 20

二叉表无非不就是查找、排序和添加删除结点么。你把cpp文件里的那几个操作函数好好看看。Top

9 楼dzds（天涯人）回复于 2004-05-10 09:08:20 得分 0

我就是不知在程序应用它呀，帮忙呀Top

10 楼Quady515（柱子）回复于 2004-05-10 11:19:09 得分 10

就那几个方法,有什么难用的?!Top

11 楼dzds（天涯人）回复于 2004-05-10 21:21:05 得分 0

举个例子吧Top