二叉查找树(BST) -- C++实现


// BinarySearchTree.h
#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H

#include "Component.h"

namespace jay{

	template<typename T>
	class BinarySearchTree
	{
	private:
		// 内嵌的节点类
        class Node
		{
			public:
			T m_value;
			Node* m_pLeftChild;
			Node* m_pRightChild;

			Node( T Value )
			{
				m_value = Value;
				m_pLeftChild = NULL;
				m_pRightChild = NULL;
			}

		};
		Node *m_pRoot;

	public:
		void Insert( T Value );
		void Insert( Node* pNode, T Value );

		void Delete( T Value );
		Node* Delete( Node* pNode, T Value );

		void ClearMemory(Node *pNode);

		T Max();
		Node* GetMax(Node* pNode);
		T Min();
		Node* GetMin(Node* pNode);

		void DeleteMax();
		Node* DeleteMax(Node* pNode);
		void DeleteMin();
		Node* DeleteMin(Node* pNode);

		// 前序后序中序遍历是针对根节点来说的
		void PreorderTraversal();  // 前序遍历 DLR 前序遍历首先访问根结点然后遍历左子树,最后遍历右子树
		void InorderTraversal();   // 中序遍历 LDR ,中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树
		void PostorderTraversal(); //后序遍历 LRD 先左后右再根  即首先遍历左子树,然后遍历右子树,最后访问根结点

		void PreorderTraversal(Node *pNode);
		void InorderTraversal(Node *pNode);  
		void PostorderTraversal(Node *pNode);
		
		int Find(T value);
		Node* Get(Node* pNode,T value);
		BinarySearchTree();
		~BinarySearchTree();
		
	};

	template<typename T>
	BinarySearchTree<T>::BinarySearchTree()
	{
		m_pRoot = NULL;
	}

	template<typename T>
	BinarySearchTree<T>::~BinarySearchTree()
	{
		ClearMemory(m_pRoot);
	}

	template<typename T>
	void BinarySearchTree<T>::ClearMemory(Node *pNode)
	{
		if ( pNode == NULL )
			return;

		// 遍历删除左子树
		if ( pNode->m_pLeftChild != NULL )
			ClearMemory( pNode->m_pLeftChild );

		// 遍历删除右子树
		if ( pNode->m_pRightChild != NULL )
			ClearMemory( pNode->m_pRightChild );

		delete pNode;
		pNode = NULL;
	}

	template<typename T>
	void BinarySearchTree<T>::PreorderTraversal()
	{
		cout << "前序遍历:";
		PreorderTraversal( m_pRoot );
		cout << endl;
	}

	template<typename T>
	void BinarySearchTree<T>::PreorderTraversal(Node *pNode)
	{
		if (pNode == NULL)
			return;

		cout << " " << pNode->m_value << " ";
		PreorderTraversal( pNode->m_pLeftChild);
		PreorderTraversal( pNode->m_pRightChild);
	}

	template<typename T>
	void BinarySearchTree<T>::InorderTraversal()
	{
		cout << "中序遍历:";
		InorderTraversal( m_pRoot );
		cout << endl;
	}

	template<typename T>
	void BinarySearchTree<T>::InorderTraversal(Node *pNode)
	{
		if (pNode == NULL)
			return;

		InorderTraversal( pNode->m_pLeftChild);
		cout << " " << pNode->m_value << " ";
		InorderTraversal( pNode->m_pRightChild);
	}

	template<typename T>
	void BinarySearchTree<T>::PostorderTraversal()
	{
		cout << "后序遍历:";
		PostorderTraversal( m_pRoot );
		cout << endl;
	}

	template<typename T>
	void BinarySearchTree<T>::PostorderTraversal(Node *pNode)
	{
		if (pNode == NULL)
			return;

		PostorderTraversal( pNode->m_pLeftChild);
		PostorderTraversal( pNode->m_pRightChild);
		cout << " " << pNode->m_value << " ";
	}

	template<typename T>
	void BinarySearchTree<T>::DeleteMax()
	{
		m_pRoot = DeleteMax(m_pRoot);
	}

	template<typename T>
	typename BinarySearchTree<T>::Node* BinarySearchTree<T>::DeleteMax(Node* pNode)
	{
		// 当pNode没有右子树的时候,说明pNode是最小的
		if (pNode->m_pRightChild == NULL) 
		{
			// 如果pNode不存在左子结点,需要将当前结点的内存释放,并返回NULL
			// 如果pNode存在左子结点,则需要将左子节点返回,替换pNode原来的位置,做pNode的父节点的右子节点
			if (pNode->m_pLeftChild == NULL) 
			{
				delete pNode;
				pNode = NULL;
				return NULL;
			}
			else
			{
				return pNode->m_pLeftChild;
			}
		}

		// 递归查找最大值
		pNode->m_pRightChild = DeleteMax(pNode->m_pRightChild); 

		//x.size = size(x.left) + size(x.right) + 1;

		// 返回当前的根节点
		return pNode;
	}

	template<typename T>
	void BinarySearchTree<T>::DeleteMin()
	{
		m_pRoot = DeleteMin(m_pRoot);
	}

	template<typename T>
	typename BinarySearchTree<T>::Node* BinarySearchTree<T>::DeleteMin(Node* pNode)
	{
		// 当pNode没有左子树的时候,说明pNode是最小的
		if (pNode->m_pLeftChild == NULL) 
		{
			// 如果pNode不存在右子结点,需要将当前结点的内存释放,并返回NULL
			// 如果pNode存在右子结点,则需要将右子节点返回,替换pNode原来的位置,做pNode的父节点的左子节点
			if (pNode->m_pRightChild == NULL) 
			{
				delete pNode;
				pNode = NULL;
				return NULL;
			}
			else
			{
				return pNode->m_pRightChild;
			}
		}

		// 递归查找最小值
		pNode->m_pLeftChild = DeleteMin(pNode->m_pLeftChild); 

		//x.size = size(x.left) + size(x.right) + 1;
		// 返回当前的根节点
		return pNode;
	}

	template<typename T>
	T BinarySearchTree<T>::Max()
	{
		return GetMax(m_pRoot)->m_value;
	}

	template<typename T>
	typename BinarySearchTree<T>::Node* BinarySearchTree<T>::GetMax(Node* pNode)
	{
		if (pNode->m_pRightChild == NULL) 
			return pNode; 
		else                 
			return GetMax(pNode->m_pRightChild); 
	}

	template<typename T>
	T BinarySearchTree<T>::Min()
	{
		return GetMin(m_pRoot)->m_value;
	}

	template<typename T>
	typename BinarySearchTree<T>::Node* BinarySearchTree<T>::GetMin(Node* pNode)
	{
		if (pNode->m_pLeftChild == NULL) 
			return pNode; 
		else                 
			return GetMin(pNode->m_pLeftChild); 
	}



	template<typename T>
	void BinarySearchTree<T>::Delete(T Value)
	{
		m_pRoot = Delete(m_pRoot, Value);
	}

	template<typename T>
	typename BinarySearchTree<T>::Node* BinarySearchTree<T>::Delete(Node* pNode,T Value)
	{
		// 该值当前不存在
		if (pNode == NULL) 
			return NULL;

		if (Value < pNode->m_value ) 
			pNode->m_pLeftChild  = Delete(pNode->m_pLeftChild,  Value);
		else if (Value > pNode->m_value ) 
			pNode->m_pRightChild  = Delete(pNode->m_pRightChild,  Value);
		else 
		{   // 找到待删除的Node
			// 如果待删除节点的右子树为空,则返回左子树
			if (pNode->m_pRightChild == NULL) 
				return pNode->m_pLeftChild;
			// 如果待删除节点的左子树为空,则返回右子树
			if (pNode->m_pLeftChild  == NULL) 
				return pNode->m_pRightChild;

			// 如果待删除节点的左右子树均不为空
			// 从待删除结点的右子树找出最小的结点CMin,将其代替当前节点的位置,然后将结点CMin删除,删除后返回的是 待删除结点的右子树删除最小值的根节点
			
			// 备份当前节点
			Node *tmp = pNode;

			// 获取待删除结点的右子树的最小的结点,替换当前节点
			pNode = GetMin(pNode->m_pRightChild);
			// 获取待删除结点的右子树的最小的结点,将该右子树返回的根节点更新给当前节点的右节点
			pNode->m_pRightChild = DeleteMin(tmp->m_pRightChild); 
			// 待删除结点的左子树,更新为当前节点的左节点
			pNode->m_pLeftChild = tmp->m_pLeftChild;

			delete tmp;
			tmp = NULL;
		} 
		// x.size = size(x.left) + size(x.right) + 1;

		// 返回当前的根节点
		return pNode;
		
	}

	template<typename T>
	int BinarySearchTree<T>::Find(T value)
	{
		if (Get(m_pRoot,value) == NULL)
		{
			return 0;
		}

		return 1;
	}

	template<typename T>
	typename BinarySearchTree<T>::Node* BinarySearchTree<T>::Get(Node* pNode,T Value)
	{
		if ( pNode == NULL )
			return NULL;

		// 查找的值小于当前节点值,则查找左子树
		if ( Value < pNode->m_value )
		{
			return Get( pNode->m_pLeftChild, Value );
		}
		// 查找的值大于当前节点值,则查找右子树
		else if(Value > pNode->m_value )
		{
			return Get( pNode->m_pRightChild, Value );
		}
		//
		else
		{
			return pNode;
		}
	}

	template<typename T>
	void BinarySearchTree<T>::Insert(T Value )
	{
		if ( m_pRoot == NULL )
			m_pRoot = new Node( Value );
		else
			Insert( m_pRoot, Value );
	}

	template<typename T>
	void BinarySearchTree<T>::Insert(Node* pNode, T Value )
	{
		// insert的值小于当前节点值,则插入左子树
		if (Value < pNode->m_value)
		{
			if ( pNode->m_pLeftChild == NULL)
				pNode->m_pLeftChild = new Node( Value );
			else
				Insert( pNode->m_pLeftChild, Value );
		}
		// insert的值大于当前节点值,则插入右子树
		else if (Value > pNode->m_value)
		{
			if ( pNode->m_pRightChild == NULL)
				pNode->m_pRightChild = new Node( Value );
			else
				Insert( pNode->m_pRightChild, Value );
		}
		// 如果相等则不处理
		// esle
	}


};

#endif
//main.cpp

#include <time.h>
#include<windows.h>

#include <iostream>
#include <vector>
using namespace std;

#include "Component.h"
#include "BinarySearchTree.h"

using namespace jay;


int main(int argc, char* argv[])
{
	BinarySearchTree<int> myBst;
	myBst.Insert(10);
	myBst.Insert(9);
	myBst.Insert(8);
	myBst.Insert(7);
	myBst.Insert(6);
	myBst.Insert(116);
	myBst.Insert(5);
	myBst.Insert(4);
	myBst.Insert(3);
	myBst.Insert(2);
	myBst.Insert(15);
	myBst.Insert(16);
	myBst.Insert(17);
	myBst.Insert(18);
	myBst.Insert(19);
	myBst.Insert(20);

	myBst.Delete(116);
	myBst.Delete(1);
	myBst.Delete(21);

	myBst.PreorderTraversal();
	myBst.InorderTraversal();
	myBst.PostorderTraversal();

	cout << "当前最大值: "<< myBst.Max()<<endl;
	myBst.DeleteMax();
	cout << "当前最大值: "<< myBst.Max()<<endl;
	myBst.DeleteMax();
	cout << "当前最大值: "<< myBst.Max()<<endl;

	cout << "当前最小值: "<< myBst.Min()<<endl;
	myBst.DeleteMin();
	cout << "当前最小值: "<< myBst.Min()<<endl;
	myBst.DeleteMin();
	cout << "当前最小值: "<< myBst.Min()<<endl;

	cout << myBst.Find(4)<<endl;
	cout << myBst.Find(5)<<endl;
	cout << myBst.Find(6)<<endl;
	cout << myBst.Find(7)<<endl;
	cout << myBst.Find(8)<<endl;

	myBst.Delete(4);
	myBst.Delete(5);
	myBst.Delete(6);

	cout <<"after delete..."<<endl;
	cout << myBst.Find(4)<<endl;
	cout << myBst.Find(5)<<endl;
	cout << myBst.Find(6)<<endl;
	cout << myBst.Find(7)<<endl;
	cout << myBst.Find(8)<<endl;
	
}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。