二叉搜索树（Binary Search Tree）：左子树上的值都小于根结点，右子树上的值都大于根结点，其层序遍历即为有序序列。

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

typedef struct BST {
	int data;
	BST* lchild, * rchild;
}BSTNode,*BSTree;

bool BST_Insert(BSTree& T, int data)
{
	if (T == NULL)
	{
		T = new BSTNode;
		T->data = data;
		T->lchild = T->rchild = NULL;
		return true;
	}
	else if (data < T->data) {
		return BST_Insert(T->lchild, data);
	}
	else if (data > T->data) {
		return BST_Insert(T->rchild, data);
	}
	else  // 已存在值不插入
		return false;
}

bool BST_Dele(BSTree& T, int data)
{
	if (T == NULL) return false;
	if (T->data == data)
	{
		BSTree p, q;  // 前驱 后继

		//如果左右儿子都有比较难删除
		if (T->lchild && T->rchild)
		{
			p = T;
			q = p->lchild;
			while (q->rchild)  // 寻找左子树最大
			{
				p = q;
				q = q->rchild;
			}
			if (p != T) {
				p->rchild = q->lchild;
			}
			else {
				p->lchild = q->lchild;
			}
			free(q);
		}
		else if (T->lchild) {  //只有左儿子
			p = T;
			T = T->lchild;
			free(p);
		}
		else  //只有右儿子或左右儿子都没有（叶子）
		{
			p = T;
			T = T->rchild;
			free(p);
		}
		return true;
	}
	else if (data < T->data) {
		return BST_Dele(T->lchild, data);
	}
	else if (data > T->data) {
		return BST_Dele(T->rchild, data);
	}
}

//BST 前序遍历
void Prior_Order(BSTree& T)
{
	if (T != NULL) {
		cout << T->data;
		Prior_Order(T->lchild);
		Prior_Order(T->rchild);
	}
}

//BST 中序遍历
void Mid_Order(BSTree& T)
{
	if (T != NULL) {
		Mid_Order(T->lchild);
		cout << T->data;
		Mid_Order(T->rchild);
	}
}

//BST 后序遍历
void Post_Order(BSTree& T)
{
	if (T != NULL) {
		Post_Order(T->lchild);
		Post_Order(T->rchild);
		cout << T->data;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	BSTree T = NULL;
	for (int i = 0; i < 10; i++)
	{
		BST_Insert(T, i);
	}
	Prior_Order(T);
	return 0;
}