Binary search tree template

Binary tree : Up to two nodes per node

Binary search tree :

nature : The left subtree is not empty , The value on the left node must be less than the value on the root node , If the right subtree is not empty , The value on the right node must be greater than the value on the root node

Embodied in insert In this step

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;
}

Balanced binary trees ：

Each subtree in the tree satisfies that the depth difference between the left subtree and the right subtree does not exceed 1

1. Front and rear drive

In the sequence traversal :4 2 5 1 6 3 7

1 The precursor node of is 5  1 The subsequent nodes of are 6

therefore

Judgment of a certain point precursor node :

1. If the node has left subtree , The precursor node is the rightmost node of the left subtree

2. If the node has no left subtree , And it is in the right subtree , Then the precursor node is its parent node

Subsequent node judgment

1. If the node has a right subtree , Then its successor node is the leftmost node of the right subtree

2. If the node has no right subtree , And it is in the left subtree , Then the successor node is its parent node

  Template code :

#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)// The queue is full 
	{
		return false;
	}
	q->rear++;// Responsible for adding elements 
	q->data[q->rear] = node;
	return true;
}
template<typename T>
bool deQueue(Queue<T>* q, BSNode<T>* &node)
{
	if (q->front == q->rear)// The queue is empty 
	{
		return false;
	}
	q->front++;// Responsible for getting elements 
	node = q->data[q->front];// Value 
	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);// Iterate to find 
	T search_minnum();// Find the smallest element 
	T search_maxnum();// Find the largest element 
	BSNode<T>*successor(BSNode<T>* x);// Find the successor node of the specified node 
	BSNode<T>*predecessor(BSNode<T>*x);// Find the precursor node of the specified node 
	void insert(T key);
	void remove(T key);// Delete the specified node 
	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>
// Root left and right 
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>
// Left root right 
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>
// Left and right 
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)// Be sure to use an address character   To change the value   The pointer is used to move 
{
	Queue<T>* q=new Queue<T>();// Define the queue 
	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);
		}

	}
}
// Precursor node   The previous node of a node when traversing the middle order 
template<typename T>
BSNode<T>* BSTree<T>::predecessor(BSNode<T>* pnode)
{
	if (pnode->lchild != nullptr)// There's a Zuozi tree   The precursor is the rightmost node of the left subtree 
	{
		pnode = pnode->lchild;
		while (pnode->rchild != nullptr)
		{
			pnode = pnode->rchild;
		}
		return pnode;
	}
	BSNode<T>* pparent = pnode->parent;
	while (pparent != nullptr && pparent->lchild == pnode)// Until the node is the right node of the parent node 
	{
		pnode = pparent;
		pparent = pparent->parent;
	}
	return pparent;
}
template<typename T>
BSNode<T>* BSTree<T>::successor(BSNode<T>* pnode)
{
	if (pnode->rchild != nullptr)// There are right subtrees   Then it is followed by the leftmost node of the right subtree 
	{
		pnode = pnode->rchild;
		while (pnode->lchild != nullptr)
		{
			pnode = pnode->lchild;
		}
		return pnode;
	}
	BSNode<T>* pparent = pnode->parent;
	while (pparent != nullptr && pparent->rchild == pnode)// If there is no right subtree and it is a left child , Is its parent node 
	{
		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;
			// Delete a node with only one child or no child   Save the child's pointer 
			if (pdel->lchild != nullptr)
			{
				pchild = pdel->lchild;
			}
			else
			{
				pchild = pdel->rchild;
			}
			// Let the child point to the parent node of the deleted node 
			if (pchild != nullptr)
			{
				pchild->parent = pdel->parent;
			}
			// If the node to be deleted is a header node 
			if (pdel->parent == nullptr)
			{
				root = pchild;
			}
			// If the parent node is not the head node , Be careful to change its parent node to point to the new child node 
			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;
		}
		// Delete recursively 
		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 << " In the sequence traversal ：" << endl;
	t.inOrder();
	cout << endl << " Level traversal : " << endl;
	t.layerOrder();
	cout << endl;
	cout << " The biggest element :" << t.search_maxnum() << endl;
	cout << " The smallest element :" << t.search_minnum() << endl;
	cout << " Remove elements 99" << endl;
	t.remove(99);
	cout << " The biggest element :" << t.search_maxnum() << endl;
	t.destory();
	getchar();
	return 0;
}