二叉查找树(Binary Search Tree)

今天下午闲着无聊，复习了一下“二叉查找树”，并用代码温习了一下。

对于二叉查找树，一般支持的操作有：查找关键字，最大值，最小值，前驱和后继等等的查询，对于高度为h的树，它们都可以在O(h)时间内完成。

BinaryTree.h

#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__

template < typename Key, typename Data > class BinaryTree;

/*! 树的节点 */
template < typename Key, typename Data >
class TreeNode
{
public:
	//! 默认构造函数
	TreeNode()
		: m_pParent( NULL ),
		  m_pLChild( NULL ),
		  m_pRChild( NULL )
	{
	}

	//! 构造函数
	TreeNode( Key k, const Data & d )
		: m_pParent( NULL ),
		  m_pLChild( NULL ),
		  m_pRChild( NULL ),
		  m_key( k ),
		  m_data( d )
	{
	}

	//! 拷贝构造函数
	TreeNode( const TreeNode< Key, Data > & node )
		: m_pParent( NULL ),
		  m_pLChild( NULL ),
		  m_pRChild( NULL ),
		  m_key( node.m_key ),
		  m_data( node.m_data )
	{
	}

	//! 赋值函数
	TreeNode< Key, Data > & operator=( const TreeNode< Key, Data > & rhs )
	{
		m_key = rhs.m_key;
		m_data = rhs.m_data;
		return *this;
	}

	//! 获取键值
	Key GetKey() const { return m_key; }
	//! 获取数据
	Data GetData() const { return m_data; }
	//! 设置数据
	void SetData( const Data & d ) { m_data = d; }

private:
	Key			m_key;					//!< 关键字
	Data		m_data;					//!< 数据
	TreeNode	*m_pParent;				//!< 父节点
	TreeNode	*m_pLChild;				//!< 左子节点
	TreeNode	*m_pRChild;				//!< 右子节点

	friend class BinaryTree< Key, Data >;
};

/*! 二叉查找树 */
template < typename Key, typename Data >
class BinaryTree
{
public:
	BinaryTree()
		:m_pRoot( NULL )
	{
	}

	~BinaryTree()
	{
		while ( m_pRoot != NULL )
		{
			DeleteNode( m_pRoot );
		}
	}

	typedef TreeNode< Key, Data > _TreeNode;

	//! 查找
	_TreeNode * Search( const Key & destK ) const;

	//! 最小值
	_TreeNode * Minimum( _TreeNode * pNode ) const;

	//! 最大值
	_TreeNode * Maximum( _TreeNode * pNode ) const;

	//! 后继
	_TreeNode * Successor( _TreeNode * pNode ) const;

	//! 前任
	_TreeNode * Predecessor( _TreeNode * pNode ) const;

	//! 添加节点
	void AddNode( const _TreeNode * pNode );

	//! 删除节点
	void DeleteNode( _TreeNode * pNode );

	//! 获取根节点
	_TreeNode * GetRootNode() const { return m_pRoot; }

private:
	_TreeNode	*m_pRoot;	//! 根节点
};

template < typename Key, typename Data >
void BinaryTree< Key, Data >::AddNode( const _TreeNode * pNode )
{
	assert( NULL != pNode &&
		"pNode cannot be NULL" );

	_TreeNode *newNode = new _TreeNode( *pNode );
	_TreeNode *n1 = m_pRoot;
	_TreeNode *n2 = NULL;
	while ( NULL != n1 )
	{
		n2 = n1;
		if ( newNode->m_key < n2->m_key )
		{
			n1 = n2->m_pLChild;
		}
		else
		{
			n1 = n2->m_pRChild;
		}
	}
	if ( NULL == m_pRoot )
	{
		m_pRoot = newNode;
	}
	else
	{
		if ( newNode->m_key < n2->m_key )
		{
			n2->m_pLChild = newNode;
		}
		else
		{
			n2->m_pRChild = newNode;
		}
		newNode->m_pParent = n2;
	}
}

template < typename Key, typename Data >
void BinaryTree< Key, Data >::DeleteNode( _TreeNode * pNode )
{
	assert( NULL != pNode &&
		"pNode cannot be NULL" );

	_TreeNode * n1 = NULL;
	_TreeNode * n2 = NULL;

	//! n1是要删除的节点
	if ( NULL == pNode->m_pLChild || NULL == pNode->m_pRChild )
	{
		//! 没有或者只有1个子节点，删除的节点时pNode
		n1 = pNode;
	}
	else
	{
		//! 左右子节点都有，先删除pNode的后继结点
		n1 = Successor( pNode ); // 该后继一定没有左节点
	}

	//! n2是n1唯一的一个子节点
	if ( NULL != n1->m_pLChild )
	{
		n2 = n1->m_pLChild;
	}
	else
	{
		n2 = n1->m_pRChild;
	}
	
	//! 为删除n1所作的指针修改
	if ( NULL != n2 )
	{
		n2->m_pParent = n1->m_pParent;
	}
	if ( NULL == n1->m_pParent )
	{
		// Root是唯一的一个父节点为空的节点
		m_pRoot = n2;
	}
	else
	{
		if ( n1 == n1->m_pParent->m_pLChild )
		{
			n1->m_pParent->m_pLChild = n2;
		}
		else
		{
			n1->m_pParent->m_pRChild = n2;
		}
	}

	if ( n1 != pNode )
	{
		//! pNode左右子节点都有的情况，
		//! 用pNode的后继结点的关键字和附加数据替换掉pNode的关键字和附加数据
		pNode->m_key = n1->m_key;
		pNode->m_data = n1->m_data;
	}

	delete n1;
}

template < typename Key, typename Data >
TreeNode< Key, Data > * BinaryTree< Key, Data >::Search( const Key & destK ) const
{
	_TreeNode *n = m_pRoot;
	while ( NULL != n && destK != n->m_key )
	{
		if ( destK < n->m_key )
		{
			n = n->m_pLChild;
		}
		else
		{
			n = n->m_pRChild;
		}
	}

	return n;
}

template < typename Key, typename Data >
TreeNode< Key, Data > * BinaryTree< Key, Data >::Minimum( _TreeNode * pNode ) const
{
	assert( NULL != pNode &&
		"pNode cannot be NULL" );

	while ( NULL != pNode->m_pLChild )
	{
		pNode = pNode->m_pLChild;
	}

	return pNode;
}

template < typename Key, typename Data >
TreeNode< Key, Data > * BinaryTree< Key, Data >::Maximum( _TreeNode * pNode ) const
{
	assert( NULL != pNode &&
		"pNode cannot be NULL" );

	while ( NULL != pNode->m_pRChild )
	{
		pNode = pNode->m_pRChild;
	}

	return pNode;
}

template < typename Key, typename Data >
TreeNode< Key, Data > * BinaryTree< Key, Data >::Successor( _TreeNode * pNode ) const
{
	assert( NULL != pNode &&
		"pNode cannot be NULL" );

	//! 2 cases
	if ( NULL == pNode->m_pRChild )
	{
		//! 1: 右子树为空
		//! 向上查找直到遇到某个是其父节点的左儿子的节点时为止
		while ( NULL != pNode->m_pParent && pNode->m_pParent->m_pLChild != pNode )
		{
			pNode = pNode->m_pParent;
		}
		return pNode->m_pParent;
	}
	else
	{
		//! 2: 右子树不为空，后继即为右子树中的最左节点
		return Minimum( pNode->m_pRChild );
	}
}

template < typename Key, typename Data >
TreeNode< Key, Data > * BinaryTree< Key, Data >::Predecessor( _TreeNode * pNode ) const
{
	assert( NULL != pNode &&
		"pNode cannot be NULL" );

	//! 2 cases
	if ( NULL == pNode->m_pRChild )
	{
		//! 1: 左子树为空
		//! 向上查找直到遇到某个是其父节点的右儿子的节点时为止
		while ( NULL != pNode->m_pParent && pNode->m_pParent->m_pRChild != pNode )
		{
			pNode = pNode->m_pParent;
		}
		return pNode->m_pParent;
	}
	else
	{
		//! 2: 左子树不为空，前任即为左子树中的最右节点
		return Maximum( pNode->m_pLChild );
	}
}

#endif

测试BST

#include "BinaryTree.h"

int num[11] = { 15, 6, 18, 3, 2, 4, 7, 13, 9, 17, 20 };

int _tmain(int argc, _TCHAR* argv[])
{
	BinaryTree< int, int > myTree;
	typedef TreeNode< int, int > Node;
	
	for ( int i = 0; i < 11; i ++ )
	{
		int x = num[i];
		Node n( x, 0 );

		myTree.AddNode( n );
	}

	Node *pRoot = myTree.GetRootNode();
	Node *min = myTree.Minimum( pRoot );
	Node *max = myTree.Maximum( pRoot );

	Node *someNode = myTree.Search( 17 );
	Node *pre = myTree.Predecessor( someNode );
	Node *suc = myTree.Successor( someNode );

	myTree.DeleteNode( suc );

	return 0;
}

参考资料：算法导论P151-P158