什么是二叉排序树：
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是中的一类。在一般情况下，查询效率比链表结构要高。
PS:
这里就不多说了，相信大家都有资料，这边直接上代码，代码里有详细的介绍，希望能帮助到大家
代码测试：
10 66 12 5 80 1 66 30 100 71 3 30 50
代码部分：
//二叉排序树性质 //1.若它的左子树不为空，则左子树上的所有结点的值均小于它的根结点的值 //2.若它的右子树不为空，则右子树上的所有结点的值均大于它的根节点的值 //3.它的左右子树也是二叉排序树 #include<iostream> #include<queue> #include<stack> using namespace std; //定义二叉排序树结点 struct BSTNode { int data; BSTNode* lchild; BSTNode* rchild; }; //插入函数 void Insert(BSTNode*& T, int data) {//因为要不断地改变指针，所以要用二级指针 BSTNode* s; //如果是空树的话，直接插入到根节点 if (!T) { s = new BSTNode; s->data = data; s->lchild = s->rchild = NULL; T = s; } else if (data < T->data) {//如果小于根节点则往左继续递归 Insert(T->lchild, data); } else if (data > T->data) {//如果大于根节点则往右继续递归 Insert(T->rchild, data); } } //创建二叉树函数 void CreatBSTree(BSTNode*& T) { T = new BSTNode; T = NULL;//要先赋NULL值 int n; cout << "请输入n个整数，代表二叉排序树的结点个数："; cin >> n; int data; for (int i = 0; i < n; i++) { cout << "现在请输入第" << i + 1 << "个结点的data值："; cin >> data; Insert(T, data); } cout << "二叉树创建成功！" << endl; } //先序遍历 void PreOrder(BSTNode* T) { if (T != NULL) { cout << T->data << " "; PreOrder(T->lchild); PreOrder(T->rchild); } } //中序遍历 void InOrder(BSTNode* T) { if (T != NULL) { InOrder(T->lchild); cout << T->data << " "; InOrder(T->rchild); } } //中序非递归遍历 void InOrder_(BSTNode* T) { BSTNode* p, * q; stack<BSTNode*>s;//创建栈 p = T; //循环条件是p不为空或者栈不为空 while (p || !s.empty()) { if (p) { s.push(p); p = p->lchild; } else { q = s.top(); s.pop(); cout << q->data << " "; p = q->rchild; } } } //后序遍历 void LastOrder(BSTNode* T) { if (T != NULL) { LastOrder(T->lchild); LastOrder(T->rchild); cout << T->data << " "; } } //层次遍历 void LevelOrder(BSTNode* T) { queue<BSTNode*>q; BSTNode* p; q.push(T); while (!q.empty()) { p = q.front(); q.pop(); cout << p->data << " "; //左孩子不为空 if (p->lchild != NULL) { q.push(p->lchild); } //右孩子不为空 if (p->rchild != NULL) { q.push(p->rchild); } } } //求树的深度 int GetDepth(BSTNode* T) { if (T == NULL) return 0; int left = GetDepth(T->lchild); int right = GetDepth(T->rchild); return left > right ? left + 1 : right + 1; } //搜索函数 BSTNode* SearchBST(BSTNode* T, int key) { if (!T || key == T->data) return T; else if (key < T->data) SearchBST(T->lchild, key); else SearchBST(T->rchild, key); } //删除函数 void DeleteBST(BSTNode* T, int key) { //初始化 BSTNode* p = T; BSTNode* f = NULL; BSTNode* q = NULL; //循环找p->data==key的值，以及它的双亲结点 while (p) { if (key == p->data) break; f = p;//f为p的双亲结点 //在左子树找 if (key < p->data) p = p->lchild; //在右子树找 else p = p->rchild; } //如果没找到 if (!p) return; //考虑三种情况：左右都不为空、左子树不为空、右子树不为空 q = p; //1.左右都不为空 if ((p->lchild) && (p->rchild)) { BSTNode* s = p->lchild; q = p; //找到左子树的最右结点，即其直接前驱 while (s->rchild) { q = s; s = s->rchild; } p->data = s->data;//令*p的直接前驱代替*p，即s代替p if (q != p) q->rchild = s->lchild;//重接*q的右子树 else q->lchild = s->lchild;//重接*q的左子树 delete s; return; } //2.没有右子树 else if (p->lchild) { //置换 q = p;//q指向要删除的结点 p = p->lchild;//p指向它的左孩子 } //3.没有左子树 else if (p->rchild) { //置换 q = p;//q指向要删除的结点 p = p->rchild;//p指向它的右孩子 } //4.是叶子结点 else if (!p->lchild && !p->rchild) { //置换 q = p; p = NULL; } //开始重接删除结点的左孩子或右孩子 if (!f) T = p;//删除的是根节点 else if (q == f->lchild) f->lchild = p; else if (q == f->rchild) f->rchild = p; delete q; } int main() { BSTNode* BT; CreatBSTree(BT); //遍历 cout << "先序遍历如下：" << endl; PreOrder(BT); cout << endl; cout << "中序遍历如下：" << endl; InOrder(BT); cout << endl; cout << "中序非递归遍历如下：" << endl; InOrder_(BT); cout << endl; cout << "后序遍历如下：" << endl; LastOrder(BT); cout << endl; cout << "层次遍历如下：" << endl; LevelOrder(BT); cout << endl; //查找 int x; cout << "请输入您要查找的值："; cin >> x; BSTNode* temp = SearchBST(BT, x); if (temp) { cout << "找到了!" << endl; } else { cout << "没有找到！" << endl; } //删除 int y; cout << "请输入您要删除的值："; cin >> y; DeleteBST(BT, y); //删除完再遍历 InOrder_(BT); cout << endl; cout << endl; system("pause"); return 0; }
输出结果：
