binarytree.cpp

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

 // BinaryTree.cpp

#include "BinaryTree.h"

// 构造函数
CBinaryTree::CBinaryTree()
{
	m_pRootNode = NULL;
}

CBinaryTree::~CBinaryTree()
{
}

/**********************************************************************
函数名：AddNode
用途：  在二叉树中增加一个节点
参数：  key[in]，节点的关键字
		item[in],节点的数据元素
返回值：
**********************************************************************/
BOOL CBinaryTree::AddNode(KEY key,CItem& item)
{
	CNode* pSubTree;
    //创建新节点
	CNode* pNewNode = new CNode;
	if (!pNewNode)
	{
		return FALSE;
	}
	
	// 填入节点数据
	pNewNode->m_Key = key;
	pNewNode->m_Item = item;
	
	// 取得根节点指针
	pSubTree = m_pRootNode; 
	if (!m_pRootNode) // 是一棵空二叉树吗？
	{
		// 如果二叉树为空，则把新加入的节点作为
		// 二叉树的根结点
		m_pRootNode = pNewNode;
		return TRUE;
	}                 // 如果不为空，则在二叉树中查找合适的位置插入元素
	while (1)
	{
		// 如果加入的节点的关键字比根节点的小
		// 则加入到二叉树的左子树中
		if (EQ(key, pSubTree->m_Key) < ZERO) 
		{
			// 如果左孩子为空   
			if ( pSubTree->m_pLeftSon == NULL )
			{
				pSubTree->m_pLeftSon = pNewNode;
				return TRUE;
			}

			pSubTree = pSubTree->m_pLeftSon;
		}
		else // 加入到右子树中
		{
			if ( pSubTree->m_pRightSon == NULL )
			{
				pSubTree->m_pRightSon = pNewNode;
				return TRUE;
			}
			pSubTree = pSubTree->m_pRightSon;
		}
	}

	return TRUE;
}

/**********************************************************************
函数名：FindSucc
用途：  找到要删除节点的后继节点
参数：  ptrNode[in]，要删除的节点
返回值：如果成功返回指向后继节点的指针，否则返回NULL
**********************************************************************/
CNode* CBinaryTree::FindSucc(CNode* ptrNode)
{
	return (ptrNode->m_pRightSon ? FindMin(ptrNode->m_pRightSon) : NULL);
}

/**********************************************************************
函数名：Search
用途：  搜索指定节点的父节点
参数：  ptrRootNode[in]，指向根节点指针
		key[in],要搜索的节点的关键字
返回值：如果成功返回指向节点的指针，否则返回NULL
**********************************************************************/
CNode* CBinaryTree::Search(CNode* ptrRootNode, KEY key)
{
	if (ptrRootNode)
	{
		if (!EQ(key,ptrRootNode->m_Key))
			return ptrRootNode;										// 找到节点
		if (EQ(key,ptrRootNode->m_Key) < ZERO)
			return Search(ptrRootNode->m_pLeftSon, key);
		else if (EQ(key,ptrRootNode->m_Key) > ZERO)
			return Search(ptrRootNode->m_pRightSon, key);
	}
	return NULL;													// 子树为空
}

/**********************************************************************
函数名：FindMin
用途：  查找二叉树中关键值最小的节点
参数：  
返回值：如果成功返回一个指向该节点的指针
		否则返回NULL
**********************************************************************/
CNode* CBinaryTree::FindMin(CNode* ptrRootNode)
{
	// 二叉排序树中最左节点是关键字最小的节点
	if(ptrRootNode)
	{
		if(ptrRootNode->m_pLeftSon == NULL)
		{
			return m_pRootNode;
		}
		else
		{
			return FindMin(ptrRootNode->m_pLeftSon);
		}
	}
	return NULL;
}

/**********************************************************************
函数名：FindParent
用途：  查找一个指点节点的父节点
参数：  ptrRootNode[in],指向该根结点的指针
		key[in], 节点关键字
返回值：成功返回指向父节点的指针，否则返回NULL
**********************************************************************/

CNode* CBinaryTree::FindParent(CNode* ptrRootNode, KEY key)
{
	if(ptrRootNode)
	{
		if( (ptrRootNode->m_pLeftSon != NULL && EQ(ptrRootNode->m_pLeftSon->m_Key, key) == ZERO ) ||
			(ptrRootNode->m_pRightSon != NULL && EQ(ptrRootNode->m_pRightSon->m_Key, key) == ZERO))
		{
			return ptrRootNode;
		}
		if(EQ(ptrRootNode->m_Key, key) > ZERO)
		{
			return FindParent(ptrRootNode->m_pLeftSon, key);
		}
		else if (EQ(ptrRootNode->m_Key, key) < ZERO)
		{
			return FindParent(ptrRootNode->m_pRightSon, key);
		}
	}
	return NULL;
}

/**********************************************************************
函数名：TraversePreOrder
用途：  二叉树的前序遍历
参数：  ptrRootNode[in],指向要遍历的树的根结点指针
		pFunc[in],针对每一个节点要调用处理函数
返回值：
**********************************************************************/
void CBinaryTree::TraversePreOrder(CNode* ptrRootNode,PerItemFunc pFunc)
{
	if (ptrRootNode) // if ptr is not NULL (i.e., there is a node)
	{
		pFunc(&ptrRootNode->m_Item);
		TraversePreOrder(ptrRootNode->m_pLeftSon, pFunc);
		TraversePreOrder(ptrRootNode->m_pRightSon, pFunc);
	}
}

/**********************************************************************
函数名：TraverseInOrder
用途：  二叉树的中序遍历
参数：  ptrRootNode[in],指向要遍历的树的根结点指针
		pFunc[in],针对每一个节点要调用处理函数
返回值：
**********************************************************************/
void CBinaryTree::TraverseInOrder(CNode* ptrRootNode,PerItemFunc pFunc)
{
	if (ptrRootNode) 
	{
		TraverseInOrder(ptrRootNode->m_pLeftSon, pFunc);
		pFunc(&ptrRootNode->m_Item);
		TraverseInOrder(ptrRootNode->m_pRightSon, pFunc);
	}
}

/**********************************************************************
函数名：TraversePostOrder
用途：  二叉树的中序遍历
参数：  ptrRootNode[in],指向要遍历的树的根结点指针
		pFunc[in],针对每一个节点要调用处理函数
返回值：
**********************************************************************/
void CBinaryTree::TraversePostOrder(CNode* ptrRootNode,PerItemFunc pFunc)
{
	if (ptrRootNode) 
	{
		TraversePostOrder(ptrRootNode->m_pLeftSon, pFunc);
		TraversePostOrder(ptrRootNode->m_pRightSon, pFunc);
		pFunc(&ptrRootNode->m_Item);
	}
}