一个C++的平衡二叉树例子



MyAVLTree.h

#pragma once
#include <memory.h>

// 	IsEmpty():若树为空，返回true，否则返回false
// 	GetDepth():获得树的深度

// Destroy():销毁一颗树
// 	Clear():清空一棵树

// 	GetRoot(T):返回树的根节点到T中
// 	GetValue(T):返回指定节点T的值

// 	PreOrderTraverse():前序遍历整棵树
// 	InOrderTraverse():中序遍历整棵树
// 	PostOrderTraverse():后序遍历整棵树

// 	Insert(e): 在树中插入新节点，并将值设为e
// 	Delete(e):将值为e的节点在树中删除


class MyBiTree
{
public:
	typedef struct _NODE
	{
		_NODE* pLeft;
		_NODE* pRight;
		int    nData;
	}NODE,*PNODE;
	MyBiTree(void);
	~MyBiTree(void);
public:
	bool IsEmpty(); // 判断树是否为空
	int  GetDepth(PNODE pNode)
	{
		if (pNode==nullptr)
		{
			return 0;
		}
		int nLeftDepth = GetDepth(pNode->pLeft);

		int nRightDepth = GetDepth(pNode->pRight);
		if (nLeftDepth>nRightDepth)
		{
			return nLeftDepth+1;
		}
		else
		{
			return nRightDepth+1;
		}
// 		return nLeftDepth>nRightDepth?
// 		nLeftDepth:nRightDepth;
	}

	void PreOrderTraverse()//前序遍历
	{
		PreOrderTraverse(m_pRoot);
		printf("\n");
	}

	void MidOrderTraverse()//中序遍历
	{
		MidOrderTraverse(m_pRoot);
		printf("\n");
	}

	void SubOrderTraverse()//后序遍历
	{
		SubOrderTraverse(m_pRoot);
		printf("\n");
	}

	bool InsertEle(int nEle)
	{
		return Insert(nEle,m_pRoot);
	}

	bool DeleteEle(int nEle)
	{
		Delete(nEle,m_pRoot);
	}

private:
	void PreOrderTraverse(PNODE pNode);
	void MidOrderTraverse(PNODE pNode);
	void SubOrderTraverse(PNODE pNode);

	bool AddNode(PNODE& pNode,int nEle);
	bool Insert(int nEle,PNODE& pNode);
	bool Delete(int nEle,PNODE& pNode);

	PNODE SingleLeftRevolve(PNODE& pk2)
	{
		PNODE pk1 = pk2->pLeft;
		pk2->pLeft = pk1->pRight;
		pk1->pRight = pk2;
		return pk1;
	}

	PNODE DoubleLeftRevolve(PNODE& pk2)
	{
		SingleRightRevolve(pk2->pLeft);
		return SingleLeftRevolve(pk2);
	}

	PNODE SingleRightRevolve(PNODE& pk2)
	{
		PNODE pk1 = pk2->pLeft;
		pk2->pRight = pk1->pLeft;
		pk1->pLeft = pk2;
		return pk1;
	}

	PNODE DoubleRightRevolve(PNODE& pk2)
	{
		SingleLeftRevolve(pk2->pRight);
		return SingleRightRevolve(pk2);
	}

	PNODE& GetMinNode(PNODE& pNode)
	{
		while (pNode->pLeft!=nullptr)
		{
			pNode = pNode->pLeft;
		}
		return pNode;
	}

	PNODE& GetMaxNode(PNODE& pNode)
	{
		while (pNode->pRight!=nullptr)
		{
			pNode = pNode->pRight;
		}
		return pNode;
	}
private:
	PNODE m_pRoot;
};

MyAVLTree.cpp

#include "stdafx.h"
#include "MyBiTree.h"

MyBiTree::MyBiTree(void)
	:m_pRoot(nullptr)
{
}

MyBiTree::~MyBiTree(void)
{
}

//判断树是否为空
bool MyBiTree::IsEmpty()
{
	if(m_pRoot==nullptr)
		return true;
	return false;
	//return m_pRoot?false:true;
}

//二叉树的前序遍历
void MyBiTree::PreOrderTraverse(PNODE pNode)
{
	//是否已经遍历到叶子节点之后
	if (pNode == nullptr)
	{
		return ;
	}
	//访问遍历到的结点
	printf("%-5d",pNode->nData);
	//访问左子树
	PreOrderTraverse(pNode->pLeft);
	//访问右子树
	PreOrderTraverse(pNode->pRight);

}

//二叉树的中序遍历
void MyBiTree::MidOrderTraverse(PNODE pNode)
{
	//是否已经遍历到叶子节点之后
	if (pNode == nullptr)
	{
		return ;
	}
	//访问左子树
	MidOrderTraverse(pNode->pLeft);
	//访问遍历到的结点
	printf("%-5d",pNode->nData);
	//访问右子树
	MidOrderTraverse(pNode->pRight);

}

//二叉树的后序遍历
void MyBiTree::SubOrderTraverse(PNODE pNode)
{
	//是否已经遍历到叶子节点之后
	if (pNode == nullptr)
	{
		return ;
	}
	//访问左子树
	SubOrderTraverse(pNode->pLeft);
	//访问右子树
	SubOrderTraverse(pNode->pRight);
	//访问遍历到的结点
	printf("%-5d",pNode->nData);

}

bool MyBiTree::AddNode(PNODE& pNode,int nEle)
{
	pNode = new NODE;
	if (pNode == nullptr)
	{
		return false;
	}
	memset(pNode,0,sizeof(NODE));
	pNode->nData = nEle;
	return true;
}

bool MyBiTree::Insert(int nEle,PNODE& pNode)
{
	//1 如果为nullptr，说明已经走到了叶子节点之后，可以添加了
	if (pNode == nullptr)
	{
		return AddNode(pNode,nEle);
	}
	//2 假如数据比此结点数据大，说明应该插入在右子树当中
	if (nEle>pNode->nData)
	{    
		if (false==Insert(nEle,pNode->pRight))
		{
			return false;
		}
	}
	//3 假如数据比此结点数据小，说明应该插入在左子树当中
	else if(nEle<pNode->nData)
	{
		if (false == Insert(nEle,pNode->pLeft))
		{
			return false;
		}
	}
	//4 假如数据一样大，返回错误
	else
	{
		return false;
	}

	int nLeftHeight = GetDepth(pNode->pLeft);
	int nRightHeight = GetDepth(pNode->pRight);
	//进行左旋
	if (nLeftHeight-nRightHeight==2)
	{
		//进行左单旋
		if(GetDepth(pNode->pLeft->pLeft)>=
			GetDepth(pNode->pLeft->pRight))
		{
			pNode = SingleLeftRevolve(pNode);
		}
		//进行左双旋
		else
		{
			pNode = DoubleLeftRevolve(pNode);
		}
	}
	//进行右旋
	else if (nRightHeight-nLeftHeight==2)
	{
		if(GetDepth(pNode->pRight->pRight)>=
			GetDepth(pNode->pRight->pLeft))
		{
			pNode = SingleRightRevolve(pNode);
		}
		else
		{
			pNode = SingleRightRevolve(pNode);
		}
	}
	return true;
}

bool MyBiTree::Delete(int nEle,PNODE& pNode)
{
	//1 已经递归到叶子节点之后，但还没有找到数据，返回失败
	if (pNode==nullptr)
	{
		return false;
	}
	//2 数据比此结点大，去右子树中继续删除
	if (nEle>pNode->nData)
	{
		if (Delete(nEle,pNode->pRight))
		{
			return false;
		}
	}
	//3 数据比此结点小，去左子树中继续删除
	else if (nEle<pNode->nData)
	{
		if (false == Delete(nEle,pNode->pLeft))
		{
			return false;
		}
	}
	//4 找到此数据了
	else
	{
		//4.1找的是叶子节点的情况
		if (pNode->pLeft==nullptr&&
			pNode->pRight==nullptr)
		{
			//释放此结点
			delete pNode;
			pNode = nullptr;
			//成功
			return true;
		}
		//4.2找到的是非叶子节点的情况
		else
		{
			int nLeftHeight = GetDepth(pNode->pLeft);
			int nRightHeight = GetDepth(pNode->pRight);
			//4.2.1如果左边比右边高，应该删除左边
			if (nLeftHeight>nRightHeight)
			{
				//寻找左边的最大值
				PNODE& pTempNode = GetMaxNode(pNode->pLeft);
				//将最大值赋值给要删除的结点
				pNode->nData = pTempNode->nData;
				//去左子树中删除找到的最大值
				if (false==Delete(pTempNode->nData,pNode->pLeft))
				{
					return false;
				}
				//return Delete(pTempNode->nData,pTempNode);
			}
			//4.2.2如果右边比左边高，应该删除右边
			else
			{
				//寻找右边的最小值
				PNODE& pTempNode = GetMinNode(pNode->pRight);
				//将最小赋值给将删除的结点
				pNode->nData = pTempNode->nData;
				//去右子树中删除找到的最小值
				if (false==Delete(pTempNode->nData,pNode->pRight))
				{
					return false;
				}
				
				//return Delete(pTempNode->nData,pTempNode);
			}

		}
	}

	int nLeftHeight = GetDepth(pNode->pLeft);
	int nRightHeight = GetDepth(pNode->pRight);
	//进行左旋
	if (nLeftHeight-nRightHeight==2)
	{
		//进行左单旋
		if(GetDepth(pNode->pLeft->pLeft)>=
			GetDepth(pNode->pLeft->pRight))
		{
			SingleLeftRevolve(pNode);
		}
		//进行左双旋
		else
		{
			DoubleLeftRevolve(pNode);
		}
	}
	//进行右旋
	else if (nRightHeight-nLeftHeight==2)
	{
		if(GetDepth(pNode->pRight->pRight)>=
			GetDepth(pNode->pRight->pLeft))
		{
			SingleRightRevolve(pNode);
		}
		else
		{
			SingleRightRevolve(pNode);
		}
	}
	return true;
}

AVLTree.cpp

// BiTree.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "MyBiTree.h"

int _tmain(int argc, _TCHAR* argv[])
{
	MyBiTree obj;
	obj.InsertEle(88);
	obj.InsertEle(75);
	obj.InsertEle(62);
	obj.InsertEle(50);
	obj.InsertEle(37);
	obj.InsertEle(25);
	obj.InsertEle(12);
	obj.MidOrderTraverse();
	return 0;
}