C++模板实现的二叉排序（查找）树

浏览数：42 / 时间：2015年06月08日

C++模板实现的二叉排序（查找）树

二叉排序树定义：

二叉排序树是这样的树，结点左边的值都小于结点的值，结点右边的值都大于结点的值，所以按照二叉树的中序遍历的话，得到的的将是按顺序排列的值。

二叉排序树的主要操作：

1：插入

插入的操作非常简单，从根结点开始，如果插入值大于根节点值，则向右遍历，如果小于根节点值，则想左遍历，知道遇到一个叶子结点为止。按插入值大于叶子则将插入值作为叶子结点的右孩子，否则左孩子。中间过程中如果遇到跟插入值相等的，则插入失败。

2：删除

关于有三种情况需要不同对待。

<1>如果是叶子结点，那么直接删除就行（注意相关的孩子指针要变成NULL）。

<2>如果要删除的结点只有左孩子或者右孩子，这样也好办，我们只需要把相应的孩子赋值          给待删除结点的双亲结点的孩子指针即可，孙子升级当儿子。

<3>如果要删除的结点既有左孩子，又有右孩子，那么情况就稍微有点麻烦，在这里我们可以采取两种策略来实现，第一种是“前驱不动，移动右孩子法”，第二种是“右孩子不动，移动前驱法”。具体如下图所示：（P是待删除的节点）


3：遍历

遍历采用递归方法，遍历的实现就很简单了。

4：清除

在清除树的所有结点的时候，采取了递归思想，判断左孩子是否为空，如果不空则清空做孩子；再判断右孩子是否为空，不为空则清空右孩子；只有当结点左右孩子结点都为空的时候，才释放该结点的空间。

5：查找

查找要利用二叉排序树的自身优点来进行，每次根据与结点的比较结果选择再继续跟左孩子比较还是跟右孩子比较。

 

实现代码：

//BSTrees.h
#ifndef DDXX_BSTREES_H
#define DDXX_BSTREES_H
#include <iostream>
using namespace std;
template<typename Type>
class BSTrees
{
public:
	BSTrees();
	~BSTrees();
public:
	struct Node
	{
		Type	e;
		Node*	leftChild;
		Node*	rightChild;
		Node()
		{
		}
		Node(Type _e)
		{
			e			= _e;
			leftChild	= NULL;
			rightChild	= NULL;
		}
	};
public:
	bool	insert(Type e);
	bool	erase1(Type e);
	bool	erase2(Type e);
	void	clear();
	bool	isEmpty();
	int		getLength();
	Node*	find(Type e);
	Node*	getRoot();
	Node*	getParent(Node* p);
	void	traverse(Node* ptr);
private:
	void	clears(Node* &p);
private:
	Node*	m_root;
	int		m_Length;
};

template<typename Type> BSTrees<Type>::BSTrees()
{
	m_root = NULL;
	m_Length = 0;
}

template<typename Type> bool BSTrees<Type>::insert(Type e)
{
	Node* ptr = new Node(e);
	if ( ptr == NULL )
	{
		cout<<"Allocate memory for the element failed"<<endl;
		return false;
	}

	if( m_root == NULL)
	{
		m_root = ptr;
		m_Length++;
		return true;
	}

	Node* p			= m_root;
	Node* pParent	= m_root;
	while( p != NULL)
	{
		if( e == p->e)
		{
			cout<<"the element is already exist"<<endl;
			return false;
		}

		pParent = p;
		if( e > p->e)
		{
			p = p->rightChild;
		}
		else
		{
			p = p->leftChild;
		}
	}
	
	if( e < pParent->e )
	{
		pParent->leftChild = ptr;
	}
	if( e > pParent->e)
	{
		pParent->rightChild = ptr;
	}

	m_Length++;
	return true;
}

template<typename Type> bool BSTrees<Type>::erase1(Type e)
{
	Node *p = find(e);
	if ( p == NULL )
	{
		cout<<"There‘s no this element to delete"<<endl;
		return false;
	}

	if ( p->leftChild == NULL)
	{
		Node* pParent = getParent(p);
		if( pParent->leftChild == p )
			pParent->leftChild = p->rightChild;
		else
			pParent->rightChild = p->rightChild;
		delete p;
		p = NULL;

		m_Length--;
		return true;
	}

	if ( p->rightChild == NULL)
	{
		Node* pParent = getParent(p);
		if( pParent->leftChild == p)
			pParent->leftChild = p->leftChild;
		else
			pParent->rightChild = p->leftChild;
		delete p;
		p = NULL;

		m_Length--;
		return true;	
	}

	if ( p->leftChild != NULL && p->rightChild != NULL)
	{
		Node* pParent = getParent(p);
		Node* pPre = p->leftChild;
		Node* ptmp = pPre;
		while( pPre->rightChild != NULL )
		{
			ptmp = pPre;
			pPre = pPre->rightChild;
		}
		if( ptmp != pPre)
		{	ptmp->rightChild = pPre->leftChild;
			pPre->leftChild = p->leftChild;
			pPre->rightChild = p->rightChild;
		}
		else
			pPre->rightChild = p->rightChild;

		if( pParent == NULL )
			m_root = pPre;
		else 
			if( pParent->leftChild == p)  
				pParent->leftChild = pPre;
			else
				pParent->rightChild = pPre;
		
		delete p;
		p = NULL;

		m_Length--;
		return true;
	}
	
}

template<typename Type> bool	BSTrees<Type>::erase2(Type e)
{
	Node *p = find(e);
	if ( p == NULL )
	{
		cout<<"There‘s no this element to delete"<<endl;
		return false;
	}

	if ( p->leftChild == NULL)
	{
		Node* pParent = getParent(p);
		if( pParent->leftChild == p )
			pParent->leftChild = p->rightChild;
		else
			pParent->rightChild = p->rightChild;
		delete p;
		p = NULL;

		m_Length--;
		return true;
	}

	if ( p->rightChild == NULL)
	{
		Node* pParent = getParent(p);
		if( pParent->leftChild == p)
			pParent->leftChild = p->leftChild;
		else
			pParent->rightChild = p->leftChild;
		delete p;
		p = NULL;

		m_Length--;
		return true;	
	}
	if( p->leftChild != NULL && p->rightChild != NULL)
	{
		Node* pParent = getParent(p);
		Node* ptr = p->leftChild;
		while( ptr->rightChild != NULL )
			ptr = ptr->rightChild;
		ptr->rightChild = p->rightChild;

		if( pParent == NULL )
			m_root = p->leftChild;
		else
			if(pParent->leftChild == p)
				pParent->leftChild = p->leftChild;
			else
				pParent->rightChild = p->leftChild;
		delete p;
		p = NULL;
		m_Length--;
		return true;
	}
}

template<typename Type> void	BSTrees<Type>::clear()
{
	if( m_root == NULL )
		return;
	clears(m_root);
	m_root = NULL;
}

template<typename Type> void	 BSTrees<Type>::clears(Node* &p)
{
	if(p->leftChild != NULL)
	{
		clears(p->leftChild);
		p->leftChild = NULL;
	}
	if(p->rightChild != NULL)
	{
		clears(p->rightChild);
		p->rightChild = NULL;
	}
	delete p;
	p = NULL;
	m_Length--;
	
}
template<typename Type> typename BSTrees<Type>::Node* BSTrees<Type>::getRoot()
{
	return m_root;
}
template<typename Type> int		BSTrees<Type>::getLength()
{
	return m_Length;
}
template<typename Type> typename BSTrees<Type>::Node* BSTrees<Type>::getParent(Node* p)
{
	if( p == m_root)
		return NULL;
	Node* ptr = m_root;
	Node* ptf = ptr;
	while( ptr != NULL )
	{
		if ( ptr->e == p->e )
			return ptf;
		if ( ptr->e > p->e )
		{
			ptf = ptr;
			ptr = ptr->leftChild;
		}
		else
		{
			ptf = ptr;
			ptr = ptr->rightChild;
		}
	}

}

template<typename Type> typename BSTrees<Type>::Node* BSTrees<Type>::find(Type e)
{
	Node* ptr = m_root;

	while(ptr != NULL)
	{
		if ( ptr->e == e )
			return ptr;
		if ( ptr->e > e )
			ptr = ptr->leftChild;
		else
			ptr = ptr->rightChild;
	}
	if ( ptr == NULL )
		return NULL;
}

template<typename Type> void BSTrees<Type>::traverse(Node* ptr)
{
	if( ptr == NULL )
		return;
	if( ptr->leftChild != NULL )
		traverse(ptr->leftChild);
	cout<<"Element value:"<<ptr->e<<endl;
	if( ptr->rightChild != NULL )
		traverse(ptr->rightChild);
}

template<typename Type> BSTrees<Type>::~BSTrees()
{
	clear();
}
#endif


//main.cpp
#include <iostream>
#include "BSTrees.h"
using namespace std;
void main()
{
         cout<<"************************testBSTree insert***********************"<<endl;
         BSTrees<int>Bst;
         intArr[9] = {6,2,8,4,10,0,12,16,14};
         for (int i=0;i<9;i++)
                   Bst.insert(Arr[i]);
         Bst.traverse(Bst.getRoot());
         cout<<"Tree‘slength is:"<<Bst.getLength()<<endl;
 
         cout<<"************************testBSTree erase1***********************"<<endl;
         //Bst.erase1(6);
         //Bst.erase1(16);
         //Bst.erase1(10);
         //Bst.erase1(8);
         Bst.erase2(6);
         Bst.erase2(16);
         Bst.erase2(10);
         Bst.erase2(8);
         Bst.traverse(Bst.getRoot());
         cout<<"Tree‘slength is:"<<Bst.getLength()<<endl;
 
         Bst.clear();
         Bst.traverse(Bst.getRoot());
         cout<<"Tree‘slength is:"<<Bst.getLength()<<endl;
}

测试结果：





C++模板实现的二叉排序（查找）树,古老的榕树,5-wow.com

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢