binarytree.h

二叉排序树相关操作示例 二叉排序树相关操作示例

// BinaryTree.h

#ifndef _BINARYTREE_H
#define _BINARYTREE_H

#include <string.h>
#include <afx.h>

// 这儿可以定义自己的节点关键字类型，
// 此处把它定义为整数
typedef int KEY;

// 这儿可以改变EQ的参数，这样只需更改EQ的的相应定义
// 而不需更改其它代码就可以实现代码的重用，比如
// 使用下面的定义就可以判断两个字符串是否相等
// #define EQ(key1,key2) (strcmp((key1),(key2)))
#define EQ(key1, key2) (((key1) > (key2)) - ((key1) < (key2)))

#define ZERO 0
#define ZERO_SMALLER (-1)
#define ZERO_GREATER 1


//节点的数据元素类
class CItem
{
public:
	CItem(){};
	CItem(int nIndex,CString strValue)
	{
		m_nIndex = nIndex;
		m_strValue = strValue;
	}
	~CItem(){};

public:
	int		m_nIndex;
	CString m_strValue; 
};

//节点类
class CNode
{
public:
	CNode()
	{
		m_pLeftSon = NULL;
		m_pRightSon = NULL;
	}
	~CNode(){};

public:
	CItem  m_Item;      // 节点的数据元素
	KEY    m_Key;       // 节点的关键字标识，每个节点的该值都不相同
	CNode* m_pLeftSon;    // 节点的左孩子，如果为NULL，说明该节点没有左孩子
	CNode* m_pRightSon;   // 节点的右孩子，如果为NULL，说明该节点没有右孩子
	
};

// 二叉树类
typedef void (*PerItemFunc)(CItem *pItem);  //针对每一个节点元素要调用的函数

class CBinaryTree
{
public:
	CBinaryTree();
	~CBinaryTree();

	BOOL AddNode(KEY key,CItem& item);

	CNode* FindSucc(CNode* ptrNode);
	CNode* Search(CNode* root, KEY key);
    CNode* FindMin(CNode* ptrRootNode);
	CNode* FindParent(CNode* ptrRootNode, KEY key);

	void TraversePreOrder(CNode* ptrRootNode,PerItemFunc pFunc);
	void TraverseInOrder(CNode* ptrRootNode,PerItemFunc pFunc);
	void TraversePostOrder(CNode* ptrRootNode,PerItemFunc pFunc);

public:
	CNode* m_pRootNode; //根结点为NULL表示是一棵空的二叉树
};


#endif   // _BINARYTREE_H