二叉搜索树模板

二叉树:每个节点最多只有两个节点

二叉搜索树:

性质:左子树不为空，左节点上的值都必须小于根节点上的值，若右子树不为空，右节点上的值必须大于根节点上的值

体现在insert这个步骤上

template <typename T>
void BSTree<T>::insert(T key)
{
	BSNode<T>* pparent = nullptr;
	BSNode<T>* pnode = root;
	while (pnode != nullptr)
	{
		pparent = pnode;
		if (key > pnode->value)
		{
			pnode = pnode->rchild;
		}
		else if (key < pnode->value)
		{
			pnode = pnode->lchild;
		}
		else
		{
			break;
		}
	}
	pnode = new BSNode<T>(key);
	if (pparent == nullptr)
	{
		root = pnode;
	}
	else
	{
		if (key > pparent->value)
		{
			pparent->rchild = pnode;
		}
		else
		{
			pparent->lchild = pnode;
		}
	}
	pnode->parent = pparent;
}

平衡二叉树：

树中每棵子树都满足其左子树和右子树的深度差不超过1

1.前驱和后驱

中序遍历:4 2 5 1 6 3 7

1的前驱节点是5  1的后继节点是6

因此

某点前驱节点的判断:

1.若该节点有左子树，则其前驱节点为左子树最右边

2.若该节点无左子树，且其为右子树中，则前驱节点为其父节点

后继节点判断

1.若该节点有右子树，则其后继节点为右子树最左边

2.若该节点无右子树，且其为左子树中，则后继节点为其父节点

 模板代码:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
#include<string>
using namespace std;
#define MAX_SIZE 128
template <typename T>
class BSNode
{
public:
	BSNode(T t):value(t),lchild(nullptr),rchild(nullptr),parent(nullptr){}
	BSNode() :lchild(NULL), rchild(NULL), parent(NULL) {};
	T value;
	BSNode<T>* lchild;
	BSNode<T>* rchild;
	BSNode<T>* parent;
};
template<typename T>
class Queue
{
public:
	Queue<T>() : front(-1), rear(-1) { data[MAX_SIZE] = {}; }
	int front;
	int rear;
	BSNode<T>*data[MAX_SIZE];
};
template<typename T>
void initQueue(Queue<T>* q)
{
	q->front = q->rear = -1;
}
template<typename T>
bool emptyQueue(Queue<T>* q)
{
	if (q->front == q->rear)
	{
		return true;
	}
	return false;
}
template<typename T>
bool enQueue(Queue<T>* q, BSNode<T>* &node)
{
	if (q->rear == MAX_SIZE - 1)//队列已满
	{
		return false;
	}
	q->rear++;//负责加元素
	q->data[q->rear] = node;
	return true;
}
template<typename T>
bool deQueue(Queue<T>* q, BSNode<T>* &node)
{
	if (q->front == q->rear)//队列为空
	{
		return false;
	}
	q->front++;//负责取元素
	node = q->data[q->front];//取值
	return true;
}
template <typename T>
class BSTree
{
public:
	BSTree() { BSNode<T>(); };
	~BSTree() { destory(); };
	void preOrder();
	void inOrder();
	void postOrder();
	void layerOrder();
	BSNode<T>* search_Iterator(T key);//迭代进行查找
	T search_minnum();//查找最小元素
	T search_maxnum();//查找最大元素
	BSNode<T>*successor(BSNode<T>* x);//查找指定节点的后继节点
	BSNode<T>*predecessor(BSNode<T>*x);//查找指定节点的前驱节点
	void insert(T key);
	void remove(T key);//删除指定节点
	void destory();
private:
	BSNode<T>* root;
	//BSNode<T>* search(BSNode<T>*& p, T key);
	void remove(BSNode<T>* p, T key);
	void preOrder(BSNode<T>* p);
	void inOrder(BSNode<T>* p);
	void postOrder(BSNode<T>* p);
	void layerOrder(BSNode<T>* &p);
	T search_minnum(BSNode<T>* p);
	T search_maxnum(BSNode<T>* p);
	void destory(BSNode<T>*& p);

};
template <typename T>
void BSTree<T>::insert(T key)
{
	BSNode<T>* pparent = nullptr;
	BSNode<T>* pnode = root;
	while (pnode != nullptr)
	{
		pparent = pnode;
		if (key > pnode->value)
		{
			pnode = pnode->rchild;
		}
		else if (key < pnode->value)
		{
			pnode = pnode->lchild;
		}
		else
		{
			break;
		}
	}
	pnode = new BSNode<T>(key);
	if (pparent == nullptr)
	{
		root = pnode;
	}
	else
	{
		if (key > pparent->value)
		{
			pparent->rchild = pnode;
		}
		else
		{
			pparent->lchild = pnode;
		}
	}
	pnode->parent = pparent;
}
template <typename T>
void BSTree<T>::preOrder()
{
	preOrder(root);
}
template <typename T>
//根左右
void BSTree<T>::preOrder(BSNode<T>* p)
{
	if (p != nullptr)
	{
		cout << p->value << endl;
		preOrder(p->lchild);
		preOrder(p->rchild);
	}
}
template <typename T>
void BSTree<T>::inOrder()
{
	inOrder(root);
}
template <typename T>
//左根右
void BSTree<T>::inOrder(BSNode<T>* p)
{
	if (p != nullptr)
	{
		inOrder(p->lchild);
		cout << p->value << endl;
		inOrder(p->rchild);
	}
}
template <typename T>
void BSTree<T>::postOrder()
{
	postOrder(root);
}
template <typename T>
//左右根
void BSTree<T>::postOrder(BSNode<T>* p)
{
	if (p != nullptr)
	{
		postOrder(p->lchild);
		postOrder(p->rchild);
		cout << p->value << endl;
	}
}
template <typename T>
void BSTree<T>::layerOrder()
{
	layerOrder(root);
}
template <typename T>
void BSTree<T>::layerOrder(BSNode<T>*& p)//一定要用取址符 才能改变值 指针是用来移动的
{
	Queue<T>* q=new Queue<T>();//定义队列
	initQueue(q);
	if (p != NULL)
	{
		enQueue(q, p);
	}
	while (!emptyQueue(q))
	{
		deQueue(q, p);
		printf("%d ", p->value);
		if (p->lchild != NULL)
		{
			enQueue(q, p->lchild);
		}
		if (p->rchild != NULL)
		{
			enQueue(q, p->rchild);
		}

	}
}
//前驱节点 中序遍历时某个节点的前一个节点
template<typename T>
BSNode<T>* BSTree<T>::predecessor(BSNode<T>* pnode)
{
	if (pnode->lchild != nullptr)//有左子树 则其前驱为左子树树最右边的节点
	{
		pnode = pnode->lchild;
		while (pnode->rchild != nullptr)
		{
			pnode = pnode->rchild;
		}
		return pnode;
	}
	BSNode<T>* pparent = pnode->parent;
	while (pparent != nullptr && pparent->lchild == pnode)//直到该节点为父节点的右节点
	{
		pnode = pparent;
		pparent = pparent->parent;
	}
	return pparent;
}
template<typename T>
BSNode<T>* BSTree<T>::successor(BSNode<T>* pnode)
{
	if (pnode->rchild != nullptr)//有右子树 则其后继为右子树最左边的节点
	{
		pnode = pnode->rchild;
		while (pnode->lchild != nullptr)
		{
			pnode = pnode->lchild;
		}
		return pnode;
	}
	BSNode<T>* pparent = pnode->parent;
	while (pparent != nullptr && pparent->rchild == pnode)//若无右子树且是左孩子，则为其父节点
	{
		pnode = pparent;
		pparent = pparent->parent;
	}
	return pparent;
}
template <typename T>
void BSTree<T>::remove(T key)
{
	remove(root,key);
}
template <typename T>
void BSTree<T>::remove(BSNode<T>* pnode,T key)
{
	if (pnode != nullptr)
	{
		if (pnode->value == key)
		{
			BSNode<T>* pdel = nullptr;
			if (pnode->lchild == nullptr || pnode->rchild == nullptr)
			{
				pdel = pnode;
			}
			else
			{
				pdel = predecessor(pnode);
			}
			BSNode<T>* pchild = nullptr;
			//删除结点只有一个孩子或者没有孩子 保存该孩子的指针
			if (pdel->lchild != nullptr)
			{
				pchild = pdel->lchild;
			}
			else
			{
				pchild = pdel->rchild;
			}
			//让孩子指向被删除节点的父节点
			if (pchild != nullptr)
			{
				pchild->parent = pdel->parent;
			}
			//如果要删除的结点是头结点
			if (pdel->parent == nullptr)
			{
				root = pchild;
			}
			//如果双亲节点不是头节点，要注意更改它的双亲节点指向新的孩子节点
			else if (pdel->parent->lchild == pdel)
			{
				pdel->parent->lchild = pchild;
			}
			else
			{
				pdel->parent->rchild = pchild;
			}
			if (pnode->value != pdel->value)
			{
				pnode->value = pdel->value;
			}
			delete pdel;
		}
		//递归进行删除
		else if (key > pnode->value)
		{
			remove(pnode->rchild, key);
		}
		else
		{
			remove(pnode->lchild, key);
		}
	}
}
template<typename T>
BSNode<T>* BSTree<T>::search_Iterator(T key)
{
	BSNode<T>* pnode = root;
	while (pnode != nullptr)
	{
		if (key == pnode->value) { return pnode; }
		if (key > pnode->value) { pnode = pnode->rchild; }
		else { pnode = pnode->lchild; }
	}
	return nullptr;
}
template <typename T>
T BSTree<T>::search_minnum()
{
	return search_minnum(root);
}
template <typename T>
T BSTree<T>::search_minnum(BSNode<T>* p)
{
	if (p->lchild != nullptr)
	{
		return search_minnum(p->lchild);
	}
	return p->value;
}
template <typename T>
T BSTree<T>::search_maxnum()
{
	return search_maxnum(root);
}
template <typename T>
T BSTree<T>::search_maxnum(BSNode<T>* p)
{
	if (p->rchild != nullptr)
	{
		return search_maxnum(p->rchild);
	}
	return p->value;
}
template <typename T>
void BSTree<T>::destory()
{
	destory(root);
}
template <typename T>
void BSTree<T>::destory(BSNode<T>* &p)
{
	if (p != nullptr)
	{
		if (p->lchild != nullptr)
		{
			destory(p->lchild);
		}
		if (p->rchild != nullptr)
		{
			destory(p->rchild);
		}
		delete p;
		p = nullptr;
	}
}
int main()
{
	BSTree<int> t;
	t.insert(62);
	t.insert(58);
	t.insert(47);
	t.insert(51);
	t.insert(35);
	t.insert(37);
	t.insert(88);
	t.insert(73);
	t.insert(99);
	t.insert(93);
	t.insert(95);
	cout << endl << "中序遍历：" << endl;
	t.inOrder();
	cout << endl << "层次遍历: " << endl;
	t.layerOrder();
	cout << endl;
	cout << "最大元素:" << t.search_maxnum() << endl;
	cout << "最小元素:" << t.search_minnum() << endl;
	cout << "删除元素99" << endl;
	t.remove(99);
	cout << "最大元素:" << t.search_maxnum() << endl;
	t.destory();
	getchar();
	return 0;
}