二叉搜索树/二叉排序树（Binary Search Tree）：
1：它或者是一棵空树。
2：具有下列性质的二叉树：
(1) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
(2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
(3)它的左、右子树也分别为二叉排序树；
(4)没有键值相等的结点。
以下代码实现了BST的插入，删除，查找，前序、中序、后序遍历的递归和非递归，层序遍历。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
struct Node{int data; //数据域 Node* lchild; //左子树 Node* rchild; //右子树
}; Node* Create_BST(int key) //创建结点
{Node* p=(Node*)malloc(sizeof(Node));p->data=key;p->rchild=NULL;p->lchild=NULL; return p;
} Node* Insert_BST(Node* T , int key) //插入结点
{ if(T==NULL) //如果T为空，那么创建新结点。 {T=Create_BST(key);}else if(T->data>key) //如果要插入的值小于T结点的值，那么往T的左子树上查找位置插入 {T->lchild=Insert_BST(T->lchild,key);}else if(T->data<key) //如果要插入的值大于T结点的值，那么往T的右子树上查找位置插入 {T->rchild=Insert_BST(T->rchild,key);}return T;
}Node* Find(Node* T,int key) //查找值为key的结点
{if(T==NULL){return NULL;}else if(T->data>key){return Find(T->lchild,key);}else if(T->data<key){return Find(T->rchild,key);}else{return T;}
}Node* FindMax(Node* T) //查找值最大的结点
{if(T==NULL){return NULL;}else if(T->rchild!=NULL){T = FindMax(T->rchild);}return T;
}Node* FindMin(Node* T) //查找值最小的结点
{if(T==NULL){return T;}else if(T->lchild!=NULL){T = FindMin(T->lchild);}return T;
}Node* Delete_BST(Node* T , int key) //删除值为key的结点
{if(T==NULL){return NULL;}else if(T->data>key){T->lchild = Delete_BST(T->lchild,key);}else if(T->data<key){T->rchild = Delete_BST(T->rchild,key);}else //当T就是要删除的那个结点时 {if(T->lchild && T->rchild)//如果T的左右子树都不为空 { //要找左子树的最大值，或者是右子树的最小值来替代这个位置 Node* tmp = FindMin(T->rchild);T->data=tmp->data;T->rchild=Delete_BST(T->rchild,tmp->data); }else if(T->rchild==NULL&&T->lchild==NULL){delete T;T=NULL;}else //左子树和右子树中有一个为空 {if(T->lchild){Node* tmp=T;T=T->lchild;delete tmp; } else{Node* tmp=T;T=T->rchild;delete tmp;}}}return T;
} void PreOrder(Node* T) //前序遍历 递归
{if(T==NULL)return;else{printf("%d ",T->data);PreOrder(T->lchild);PreOrder(T->rchild);}
}void MidOrder(Node* T) //中序遍历 递归
{if(T==NULL)return;else{MidOrder(T->lchild);printf("%d ",T->data);MidOrder(T->rchild);}
} void PostOrder(Node* T) //后序遍历 递归
{if(T==NULL)return;else{PostOrder(T->lchild);PostOrder(T->rchild);printf("%d ",T->data);}
} void LevelOrder(Node* T) //层序遍历 队列
{if(T==NULL)return;queue<Node*> q; Node* p;q.push(T);while(!q.empty()){p=q.front();q.pop();if(p->lchild!=NULL){q.push(p->lchild);}if(p->rchild!=NULL){q.push(p->rchild);}printf("%d ",p->data); }
}void PrintPre(Node* T) //前序遍历 栈（非递归）
{if(T==NULL)return ;stack<Node*> s;Node* p=T;Node* q;while(p!=NULL||!s.empty()) //结点不为空||栈中有元素 {if(p){printf("%d ",p->data); //先访问根节点 s.push(p); //根节点入栈 p=p->lchild; //访问左子树 } else //当p结点为空时 代表没有左右节点了 即p现在是叶子结点 { q=s.top(); //使p的根节点出栈 s.pop(); p=q->rchild; //访问右子树 } }
} void PrintMid(Node* T) //中序遍历 栈（非递归）
{if(T==NULL)return ;stack<Node*> s;Node* p=T;Node* q;while(p!=NULL||!s.empty()){if(p){s.push(p); //先访问左子树，使左子树根节点进栈 p=p->lchild; //找到左子树的最底层 }else{q=s.top();s.pop();printf("%d ",q->data); //输出根节点 p=q->rchild; //右子树入栈 } }} void PrintPost(Node* T) //后序遍历 栈（非递归） 左右根
{if(T==NULL)return;stack<Node*> s;Node* p=T; //p存放当前访问结点Node* q=NULL; //q存放上次访问的结点 while(p!=NULL) //首先要访问左子树，所以不断的将根入栈，找到左子树的最底层 {s.push(p);p=p->lchild;} while(!s.empty()){p=s.top(); //将栈顶元素出栈 s.pop();//结点能够被访问的前提是：没有右子树，或者是右子树刚被访问过 if(p->rchild==NULL||p->rchild==q) {printf("%d ",p->data);q=p; //更新访问过的结点 }else //有右子树且右子树未被访问 {s.push(p); //此结点再次入栈p=p->rchild;//进入右子树进行访问，而且右子树一定不为空 while(p) //到达右子树中左子树的最低层 {s.push(p);p=p->lchild;} } }
} int Height_BST(Node* T) //BST的高度
{if(T==NULL)return 0;else{return max(Height_BST(T->rchild),Height_BST(T->lchild))+1;}
}int main()
{int n; //n个结点int num;Node* Tree = NULL;scanf("%d",&n); for(int i=0;i<n;i++){scanf("%d",&num);Tree=Insert_BST(Tree,num); //插入结点 } printf("\n\n----------------------------\n");printf("MinKey: %d\n",FindMin(Tree)->data); //最小值 printf("MaxKey: %d\n",FindMax(Tree)->data); //最大值 printf("\n\n----------------------------\n");printf("前序遍历（递归）：\n");PreOrder(Tree);printf("\n\n"); printf("前序遍历（非递归）：\n");PrintPre(Tree);printf("\n\n");printf("中序遍历（递归）：\n");MidOrder(Tree);printf("\n\n");printf("中序遍历（非递归）：\n");PrintMid(Tree);printf("\n\n");printf("后序遍历（递归）：\n");PostOrder(Tree);printf("\n\n");printf("后序遍历（非递归）：\n");PrintPost(Tree);printf("\n\n");printf("层序遍历 ：\n");LevelOrder(Tree);printf("\n\n");printf("\n\n----------------------------\n"); printf("BST的高度： %d\n",Height_BST(Tree)); printf("\n\n----------------------------\n");printf("请输入要查找的数字：\n");int x;scanf("%d",&x);if(Find(Tree,x)!=NULL) printf("存在！\n"); elseprintf("不存在！\n");printf("\n\n----------------------------\n"); printf("请输入要删除的数字：\n"); scanf("%d",&x);Tree=Delete_BST(Tree,x);printf("删除后的序列（中序）：\n");MidOrder(Tree); return 0;
}