二叉搜索树(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;
}