【c++】二叉搜索树的插入、查找、非递归删除

灰太狼 2022-06-09 04:44 172阅读 0赞

尤其注意删除单个根结点、删除有一个分支的根结点时要防止内存泄露（\_root为私有成员时）

#include <iostream>
    #include <stack>
    #include <queue>
    
    using namespace std;
    
    //结点类
    template <class T>
    class BinaryNode
    {
    public:
    	T data;
    	BinaryNode<T> *lchild;
    	BinaryNode<T> *rchild;
    
    	BinaryNode();
    	BinaryNode(T val);
    private:
    
    };
    
    template <class T>
    BinaryNode<T>::BinaryNode()
    {
    	data = 0;
    	lchild = NULL;
    	rchild = NULL;
    }
    
    template <class T>
    BinaryNode<T>::BinaryNode(T val)
    {
    	data = val;
    	lchild = NULL;
    	rchild = NULL;
    }
    
    //二叉树类
    template <class  T>
    class BinaryTree
    {
    private:
    	BinaryNode<T> *_root;  //根结点
    
    public:
    	BinaryTree();	//构造空结点
    	BinaryTree(const T preList[], const int size, int index, const T end);	//先序构造
    	~BinaryTree();
    
    	BinaryNode<T>* CreateBiTree(const T preList[], const int size, int &index, const T end);	//先序创建二叉树
    	void ClearBiTree(BinaryNode<T> *root);  //销毁二叉树
    	void PreVisitBiTree();	//先序遍历，非递归
    	void MidVisitBiTree();	//中序遍历，非递归
    	void PostVisitBiTree();	//后序遍历，非递归
    	void LevelVisitBiTree();//层序遍历，非递归
    	void InsertTree(int val);
    	void DeleteTree(int val);
    	BinaryNode<T>* SearchTree(int val);
    };
    
    //构造空树
    template <class T>
    BinaryTree<T>::BinaryTree()
    {
    	_root = NULL;
    }
    
    //先序构造二叉树
    template <class T>
    BinaryTree<T>::BinaryTree(const T preList[], const int size, int index, const T end)
    {
    	_root = CreateBiTree(preList, size, index, end);
    }
    
    //析构
    template <class T>
    BinaryTree<T>::~BinaryTree()
    {
    	ClearBiTree(_root);
    	_root = NULL;
    }
    
    //先序创建二叉树
    template <class T>
    BinaryNode<T>* BinaryTree<T>::CreateBiTree(const T preList[],const int size, int &index,const T end)  //特别注意：index必须用引用，否则函数的两个++index将不会正常改变
    {
    	BinaryNode<T>* root = NULL;
    
    	if((index < size) && (preList[index] != end))
    	{
    
    		root = new BinaryNode<T>();
    
    		root->data = preList[index];
    		root->lchild = CreateBiTree(preList, size, ++index, end);
    		root->rchild = CreateBiTree(preList, size, ++index, end);
    	}
    	return root;
    }
    
    //销毁二叉树
    template <class T>
    void BinaryTree<T>::ClearBiTree(BinaryNode<T>* root)
    {
    	BinaryNode<T> *tmp = root;
    
    	if(tmp == NULL)
    	{
    		return;
    	}
    	ClearBiTree(tmp->lchild);
    	ClearBiTree(tmp->rchild);
    
    	delete tmp;
    	tmp = NULL;
    }
    
    //非递归遍历
    
    //1 前序遍历
    template <class T>
    void BinaryTree<T>::PreVisitBiTree()
    {
    	BinaryNode<T>* cur = _root;
    	stack<BinaryNode<T> *> biTreeStack;
    
    	if(cur == NULL)
    	{
    		cout << "NULL" << endl;
    		return;
    	}
    
    	while ((cur != NULL) || (!biTreeStack.empty()))
    	{
    		while (cur != NULL)
    		{
    			cout << cur->data << " "; 
    			biTreeStack.push(cur);
    			cur = cur->lchild;
    		}
    		BinaryNode<T> *top = biTreeStack.top();
    		biTreeStack.pop();
    		cur = top->rchild;
    		cur->data;
    	}
    	cout << endl;
    }
    
    //2 中序遍历
    template<class T>
    void BinaryTree<T>::MidVisitBiTree()
    {
    	BinaryNode<T> *cur = _root;
    	stack<BinaryNode<T> *> biTreeStack;
    
    	while ((cur != NULL) || (!biTreeStack.empty()))
    	{
    		while (cur != NULL)
    		{
    			biTreeStack.push(cur);
    			cur = cur->lchild;
    		}
    		BinaryNode<T> *top = biTreeStack.top();
    		cout << top->data << " ";
    		biTreeStack.pop();
    		cur = top->rchild;
    	}
    	cout << endl;
    }
    
    //3 后序遍历
    template<class T>
    void BinaryTree<T>::PostVisitBiTree()
    {
    	BinaryNode<T> *cur = _root;
    	BinaryNode<T> *priview = NULL;
    
    	stack<BinaryNode<T> *> biTreeStack;
    
    	while ((cur != NULL) || (!biTreeStack.empty()))
    	{
    		while (cur != NULL)
    		{
    			biTreeStack.push(cur);
    			cur = cur->lchild;
    		}
    
    		BinaryNode<T> *top = biTreeStack.top();
    
    		if((top->rchild == NULL) || (priview == top->rchild))
    		{
    			cout << top->data << " ";
    			priview = top;
    			biTreeStack.pop();
    		}
    		else
    		{
    			cur = top->rchild;
    		}
    		
    	}
    	cout << endl;
    }
    
    //4 层序遍历
    template<class T>
    void BinaryTree<T>::LevelVisitBiTree()
    {
    	BinaryNode<T> *cur = _root;
    	queue<BinaryNode<T> *> biTreeQueue;
    
    	biTreeQueue.push(cur);
    
    	while (!biTreeQueue.empty())
    	{
    		BinaryNode<T> *top = biTreeQueue.front();
    		cout << top->data << " ";
    		biTreeQueue.pop();
    		
    		if(top->lchild != NULL)
    		{
    			biTreeQueue.push(top->lchild);
    		}
    		if(top->rchild != NULL)
    		{
    			biTreeQueue.push(top->rchild);
    		}
    	}
    	cout << endl;
    }
    
    //搜索二叉树的插入
    template<class T>
    void BinaryTree<T>::InsertTree(int val)
    {
    	if(NULL == _root)
    	{
    		_root =new BinaryNode<T>();
    		_root->data = val;
    		
    		return;
    	}
    
    	BinaryNode<T> *cur = _root;
    	BinaryNode<T> *parant = NULL;
    	BinaryNode<T> *tmp = new BinaryNode<T>();
    
    	while (cur != NULL)
    	{
    		parant = cur;
    		if(val < cur->data)
    		{
    			cur = cur->lchild;
    		}
    		else
    		{
    			cur = cur->rchild;
    		}
    	}
    	
    	tmp->data = val;
    	if(val < parant->data)
    	{
    		parant->lchild = tmp;
    	}
    	else
    	{
    		parant->rchild = tmp;
    	}
    }
    
    //删除二叉树
    template<class T>
    void BinaryTree<T>::DeleteTree(int val)
    {
    	if(NULL == _root)
    	{
    		cout << "删除失败：树为空" << endl;
    		return;
    	}
    
    	BinaryNode<T> *cur = _root;
    	BinaryNode<T> *parent = _root;
    
    	int flag = 0;
    
    	while (cur != NULL)
    	{
    		if(cur->data == val)
    		{
    			if((NULL == cur->lchild) && (NULL == cur->rchild)) //要删除的点为叶节点
    			{
    				if(parent == cur) //树只有一个结点
    				{
    					delete _root;	//必须删除原始根结点 _root
    					_root = NULL;	
    					return;
    				}
    				else if(parent->lchild == cur) //左孩子为要删除的点
    				{
    					parent->lchild = NULL;
    				}
    				else if(parent->rchild == cur) //右孩子为要删除的点
    				{
    					parent->rchild = NULL;
    				}
    
    				delete cur;
    				cur = NULL;
    				return;
    			}
    			else if((NULL == cur->lchild) || (NULL == cur->rchild)) //要删除的点有一个孩子
    			{
    				if(parent->lchild == cur)  //要删除的点是左孩子
    				{
    					if(cur->lchild != NULL) //要删除的点有一个左孩子
    					{
    						parent->lchild = cur->lchild;
    					}
    					else if(cur->rchild != NULL)
    					{
    						parent->lchild = cur->rchild;
    					}
    				}
    				else if(parent->rchild == cur)
    				{
    					if(cur->lchild != NULL)
    					{
    						parent->rchild = cur->lchild;
    					}
    					else if(cur->rchild != NULL)
    					{
    						parent->rchild = cur->rchild;
    					}
    				}
    
    				else if(parent == cur)  //要删除的点为根节点，且有一个分支
    				{
    					if(cur->lchild != NULL)
    					{
    						_root = cur->lchild;	//必须删除原始根结点 _root，如果delete一个局部变量，只是将_root中的值改变，但是
    												//_root还是存在的，它变成了野指针，当再次访问根结点的时候，就会导致内存泄露
    					}
    					else if(cur->rchild != NULL)
    					{
    						_root = cur->rchild;	//必须删除原始根结点 _root
    					}
    				}
    				delete cur;
    				cur = NULL;
    				return;
    			}
    			else
    			{
    				BinaryNode<T> *tmp = cur;
    				BinaryNode<T> *tmpParent = cur;
    				
    				tmp = tmp->lchild;
    				while (tmp->rchild != NULL)
    				{
    					tmpParent = tmp;
    					tmp = tmp->rchild;
    				}
    
    				cur->data = tmp->data;
    				if(tmpParent == cur)
    				{
    					cur->lchild = tmp->lchild;
    				}
    				else
    				{
    					tmpParent->rchild = tmp->lchild;
    				}
    				delete tmp;
    				tmp = NULL;
    				return;
    			}
    		}
    
    		parent = cur;
    		if(val < cur->data)
    		{
    			cur = cur->lchild;
    		}
    		else
    		{
    			cur = cur->rchild;
    		}
    	}
    
    	cout << "未找到要删除的点" << endl;
    }
    
    //搜索二叉树
    template<class T>
    BinaryNode<T>* BinaryTree<T>::SearchTree(int val)
    {
    	if(NULL == _root)
    	{
    		cout << "none tree" << endl;
    		return _root;
    	}
    
    	BinaryNode<T> *cur = _root;
    	while (cur != NULL)
    	{
    		if(val < cur->data)
    		{
    			cur = cur->lchild;
    		}
    		else if(val > cur->data)
    		{
    			cur = cur->rchild;
    		}
    		else
    		{
    			return cur;
    		}
    	}
    
    	cout << "none tree" << endl;
    	return NULL;
    }
    
    int main()
    {
    	//int preList[] = {8, 2 , 0, 3, 0, 0, 14, 0, 33, 0, 0};
    	int preList[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    	BinaryTree<int> *tree = new BinaryTree<int>(preList, 12, 0, 0);
    	//tree->PreVisitBiTree();
    	//tree->MidVisitBiTree();
    	//tree->PostVisitBiTree();
    	//tree->LevelVisitBiTree();
    	tree->InsertTree(34);
    	tree->InsertTree(32);
    	//tree->InsertTree(33);
    	//tree->DeleteTree(8);
    	tree->DeleteTree(34);
    	//tree->DeleteTree(32);
    	//tree->DeleteTree(33);
    	//tree->DeleteTree(14);
    	//tree->DeleteTree(2);
    	//tree->DeleteTree(3);
    	//tree->DeleteTree(35);
    	cout << "insert a number" << endl;
    	tree->MidVisitBiTree();
    	cout << "search tree" << endl;
    	
    	BinaryNode<int> *tmp = tree->SearchTree(98);
    	if(tmp != NULL)
    	{
    		cout << tmp->data << endl;
    	}
    
    	delete tree;
    
    	return 0;
    }