BST tree

Binary search tree （BST Trees ） The construction of 、 lookup 、 Insert 、 Delete operation

BST（ Binary search / Sort tree ） Class template implementation

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>

typedef int Key;

typedef struct BstNode {
    
	BstNode* left;
	BstNode* right;
	BstNode* parents;
	Key val;
}BstNode;

typedef struct 
{
    
	BstNode* head;
	int size;
}Bstree;

BstNode* BuyNode(BstNode* pa = NULL)// establish 
{
    
	BstNode* s = (BstNode*)malloc(sizeof(BstNode));
	if (s == NULL)
		exit(1);
	memset(s, 0, sizeof(BstNode));
	s->parents = pa;
	return s;
}

void InitBstree(Bstree &root)// initialization 
{
    
	root.head = BuyNode();
	root.size = 0;
}

void Free(BstNode* p)// Release 
{
    
	free(p);
}


void DestroyBstree(BstNode* node)
{
    
	if (node)
	{
    
		DestroyBstree(node->left);
		DestroyBstree(node->right);
		Free(node);
	}
}
void Destroy(Bstree& root)// The destruction 
{
    
	DestroyBstree(root.head->parents);
	root.size = 0;
}

BstNode* First(BstNode* ptr)//Min
{
    
	while (ptr != NULL&&ptr->left != NULL)
		ptr = ptr->left;
	return ptr;
}

BstNode* Last(BstNode* ptr)//Max
{
    
	while (ptr != NULL&&ptr->right != NULL)
		ptr = ptr->right;
	return ptr;
}

BstNode* Next(Bstree& root, BstNode *ptr)// The last node 
{
    
	if (ptr == NULL || ptr == root.head)
		return NULL;
	if (ptr->right != NULL)
		return First(ptr->right);
	else
	{
    
		BstNode* pa = ptr->parents;
		while (pa != root.head&&pa->left != ptr)
		{
    
			ptr = pa;
			pa = pa->parents;
		}
		if (pa == root.head)
			pa = NULL;
		return pa;
	}
}

BstNode* Prev(Bstree& root, BstNode* ptr)// Previous 
{
    
	if (ptr == NULL || ptr == root.head)
		return NULL;
	if (ptr->left != NULL)
		return Last(ptr->left);
	else
	{
    
		BstNode* pa = ptr->parents;
		while (pa != root.head&&pa->right != ptr)
		{
    
			ptr = pa;
			pa = pa->parents;
		}
		if (pa == root.head)
			pa = NULL;
		return pa;
	}
}

BstNode* FindVal(Bstree & root, Key val)// Loop search 
{
    
	BstNode* p = root.head->parents;
	while (p != NULL&&p->val != val)
		p = val < p->val ? p->left : p->right;
	return p;
}


BstNode* Search(BstNode* p, Key val)
{
    
	if (p == NULL || p->val == val)
		return p;
	else if (val < p->val)
		return Search(p->left, val);
	else return Search(p->right, val);
}
BstNode* SearchVal(Bstree& root, Key val)// Recursive search 
{
    
	return Search(root.head->parents, val);
}


bool InterBST(Bstree &root, Key val)// Insert elements 
{
    
	BstNode* pa = root.head;
	BstNode* p = root.head->parents;
	while (p != NULL&&p->val != val)
	{
    
		pa = p;
		p = (val < p->val ? p->left : p->right);
	}
	if (p != NULL)
		return false;
	p = BuyNode(pa);
	p->val = val;
	if (pa == root.head)
	{
    
		root.head->left = p;
		root.head->right = p;
		root.head->parents = p;
	}
	else {
    
		if (p->val < pa->val)
		{
    
			pa->left = p;
			if (p->val < root.head->left->val)
				root.head->left = p;
			else {
    
				pa->right = p;
				if (p->val > root.head->left->val)
					root.head->right = p;
			}
		}
	}
	root.size++;
	return true;
}

bool RemoveBST(Bstree &root, Key val)// Delete a value 
{
    
	BstNode* pa = root.head;
	BstNode* p = root.head->parents;
	while (p != NULL || p->val != val)
	{
    
		pa = p;
		p = val < p->val ? p->left : p->right;
	}
	if (p == NULL) return false;
	if (p->left != NULL&&p->right != NULL)
	{
    
		BstNode* nt = Next(root, p->right);
		p->val = nt->val;
		p = nt;
	}
	BstNode* child = p->left != NULL ? p->left : p->right;
	if (child != NULL)child->parents = pa;
	if (pa == root.head)
		root.head->parents = child;
	else
	{
    
		if (p == pa->left)
			pa->left = child;
		else
			pa->right = child;
	}
	Free(p);
	root.size -= 1;
	return true;
}

//void NiceInOrder(Bstree& root)
//{
    
// for (BstNode *p = First(root.head)->parents;
// p != NULL; p = Next(root, p))
// printf("%d ", p->val);
// printf("\n");
//}
//void ResNiceInOrder(Bstree& root)
//{
    
// for(BstNode *p = Last(root.head)->parents;
// p != NULL; p = Prev(root, p))
// printf("%d ", p->val);
// printf("\n");
//}

void Inordr(BstNode* node)
{
    
	if (node)
	{
    
		Inordr(node->left);
		printf("%d ", node->val);
		Inordr(node->right);
	}
}
void inordr(Bstree* root)// In the sequence traversal 
{
    
	if (root)
		Inordr(root->head);
	printf("\n");
}

int main()
{
    
	Bstree* root = (Bstree*)malloc(sizeof(Bstree));
	InitBstree(*root);
	int arr[] = {
     9,5,3,4,1,7,2,8,0 };
	int n = sizeof(arr) / sizeof(int);
	for (int i = 0; i < n; i++)
	{
    
		InterBST(*root, arr[i]);
	}
	inordr(root);
	printf("max:%d\n", Last(root->head)->val);
	printf("min:%d\n", First(root->head)->val);
	return 0;
}

#include <iostream>

using namespace std;

template<typename T>
class BST {
    
private:
	struct Node
	{
    
		T val;
		Node* left;
		Node* right;
		Node(T val)// Use numerical construction Node
		{
    
			this->val = val;
			this->left = this->right = NULL;
		}
		Node(Node* node)// Use existing Node Building new Node
		{
    
			this->val = node->val;
			this->left = node->left;
			this->right = node->right;
		}
	};
	Node* root;
	int size;
	Node* insert(Node* node, T val)// Insert 
	{
    
		if (node == NULL) {
    
			size++;
			return new Node(val);
		}
		else
		{
    
			if (val == node->val)
			{
    
				node->val = val;
				return node;
			}
			else if (val < node->val)
			{
    
				node->left = insert(node->left, val);
				return node;
			}
			else {
    
				node->right = insert(node->right, val);
				return node;
			}
		}
	}

	Node* maxNode(Node* node)// Get the maximum ,Last
	{
    
		if (node->right == NULL)
			return node;
		return maxNode(node->right);
	}

	Node* minNode(Node* node)// Get the minimum ,First
	{
    
		if (node->left == NULL)
			return node;
		return minNode(node->left);
	}

	Node* deleteMin(Node* node)// Return to delete the minimum value BST The value of the tree 
	{
    
		if (node->left == NULL)
		{
    
			Node* rightNode = node->right;
			delete node;
			size--;
			return rightNode;
		}
		else {
    
			node->left = deleteMin(node->left);
			return node;
		}
	}

	Node* deleteMax(Node* node)// Return to delete the maximum BST The root of the tree 
	{
    
		if (node->right == NULL)
		{
    
			Node* leftNode = node->left;
			delete node;
			size--;
			return leftNode;
		}
		else {
    
			node->right = deleteMax(node->right);
			return node;
		}
	}
	Node* remove(Node* node, T val)// Delete 
	{
    
		if (node == NULL)
			return node;
		else
		{
    
			if (val < node->val)
			{
    
				node->left = remove(node->left,val);
				return node;
			}
			else if (val>node->val)
			{
    
				node->right = remove(node->right,val);
				return node;
			}
			else {
    
				if (node->right == NULL) {
    
					Node* left = node->left;
					delete node;
					size--;
					return left;
				}
				else if (node->right == NULL) {
    
					Node* right = node->right;
					delete node;
					size--;
					return right;
				}
				else {
    
					Node* deleteNode = node;
					Node* newTree = new Node(minNode(node->right));
					this->size++;
					newTree->right = deleteMin(node->right);
					newTree->left = node->left;
					delete node;
					size--;
					return newTree;
				}
			}
		}
	}
	void inorder(Node* node)// In the sequence traversal 
	{
    
		if (node)
		{
    
			inorder(node->left);
			cout << node->val << " ";
			inorder(node->right);
		}
	}
	void destroy(Node* node)// The destruction 
	{
    
		if (node)
		{
    
			destroy(node->left);
			destroy(node->right);
			delete node;
			size--;
		}
	}
public:
	// stay public Calling private methods in 
	BST()
	{
    
		root = NULL;
		size = 0;
	}
	~BST()
	{
    
		destroy(root);
	}
	int GetSize()
	{
    
		return size;
	}
	bool IsEmpty()
	{
    
		return size == 0;
	}
	void insert(T val)
	{
    
		root = insert(root, val);
	}
	T maxVal()
	{
    
			Node* maxVal = maxNode(root);
			return maxVal->val;	
	}
	T minVal()
	{
    
			Node* minVal = minNode(root);
			return minVal->val;
	}
	void deleteMax()
	{
    
		if (root)
			root = deleteMax(root);
	}
	void deleteMin()
	{
    
		if (root)
			root = deleteMin(root);
	}
	void remove(T val)
	{
    
		if (root)
			root = remove(root, val);
	}
	void inorder()
	{
    
		inorder(root);
		cout << endl;
	}
};

int main()
{
    
	int arr[] = {
     9,5,3,4,1,7,2,8,0 };
	int n = sizeof(arr) / sizeof(int);
	BST<int> bst;
	for (int i = 0; i < n; i++)
	{
    
		bst.insert(arr[i]);
	}
	bst.inorder();
	cout << "max: " << bst.maxVal() << endl;
	cout << "min: " << bst.minVal() << endl;
	cout << " The deleted node is :value=4" << endl;
	bst.remove(4);
	bst.inorder();
	return 0;
}

Compare your feelings C++ It's also very useful