#include<iostream>
using namespace std;
/*-----------二叉排序树的二叉链表的存储表示-----------*/
#define ENDFLAG 999
typedef int KeyType;
typedef int InfoType;
typedef struct {
KeyType key;//关键子项
InfoType otherinfo;//其他数据域
} ElemType;
typedef struct BSTNode {
ElemType data;//每个结点的数据域包括关键字项和其他数据项
struct BSTNode *lchild, *rchild;//左右孩子指针
} BSTNode, *BSTree;
/*-----------二叉排序树的查找--------------*/
BSTNode *Search_BST(BSTree &T, KeyType key) {
while (T != NULL && key != T->data.key) {
if (key < T->data.key) T = T->lchild;
else T = T->rchild;
}
return T;
}
/*--------- 二叉排序树的递归查找-----------*/
BSTNode *SearchBST(BSTree T, KeyType key) {
//在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
//若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
if ((!T) || key == T->data.key) return T;//查找结束
else if (key < T->data.key) return SearchBST(T->lchild, key);//在左子树中继续查找
else return SearchBST(T->rchild, key);//在右子树中继续查找
}
/*----------二叉排序树的插入------------*/
void InsertBST(BSTree &T, ElemType e) {
if (!T) {
BSTNode *S = new BSTNode;//生成新结点*S
S->data = e;//新结点*S的数据域置为e
S->lchild = S->rchild = NULL;//新结点*S作为叶子结点
T = S;//把新结点*S链接到已找到的插入位置
} else if (e.key < T->data.key)
InsertBST(T->lchild, e);//将*S插入左子树
else if (e.key > T->data.key)
InsertBST(T->rchild, e);//将*S插入右子树
}
/*------------非递归建立二叉排序树------------*/
BSTNode *nonRecusInsertNode(BSTree &T, ElemType e) {
BSTNode *p = T; //用来查找
BSTNode *q = NULL; //用来指明当前插入位置的父节点
//此处用来寻找插入的位置和当前插入位置的父节点
//q记录插入位置的父节点用来连接插入的孩子
while (p != NULL) {
if (p->data.key == e.key) {
return NULL; //已经存在，插入失败
} else if (p->data.key > e.key) {
q = p;
p = p->lchild; //找到对应插入为NULL的位置
} else {
q = p;
p = p->rchild;
}
}
//初始化一个插入结点
p = (BSTNode *) malloc(sizeof(BSTNode));
p->data.key = e.key;
p->lchild = NULL;
p->rchild = NULL;
//将插入结点与之父节点相连
if (!q) { //要插入根节点，直接用T指针相连
T = p;
} else if (q->data.key > e.key) { //插入父节点的左边，将父节点的左孩子指向插入的结点
q->lchild = p;
} else q->rchild = p; //插入父节点的右边，将父节点的右孩子指向插入的结点
return p;
}
/*----------二叉排序树的创建-----------*/
void CreatBST(BSTree &T) {
//依次读入一个关键字为key的结点，将此结点插入二叉排序树T中
T = NULL;//将二叉排序树T初始化为空树
ElemType e;
int test_num[] = {6, 10, 45, 32, 55, 68, 100};
for (int i = 0; i < sizeof(test_num) / sizeof(test_num[0]); ++i) {
e.key = test_num[i];
InsertBST(T, e);
}
}
/*---------二叉排序树的删除----------*/
void DeleteBST(BSTree &T, KeyType key) {
//从二叉排序树T中删除关键字等于key的结点
BSTNode *p = new BSTNode;
BSTNode *f;
p = T;
f = NULL;
/*--------------下面的while循环从根开始查找关键字等于key的结点*p----------*/
while (p) {
if (p->data.key == key) break;//找到关键字等于key的结点*p，结束循环
f = p;//*f为*p的双亲结点
if (p->data.key > key) p = p->lchild;//在*p的左子树中继续查找
else p = p->rchild;//在*p的右子树中继续查找
}
if (!p) return;//找不到被删结点则返回
/*------考虑3种情况实现p所指子树内部的处理：
* *p左右子树均空(为叶子节点)、
* 左右子树均不空、
* 无右子树(或无左子树)----*/
if (p->lchild == NULL && p->rchild == NULL) {//1.*p左右子树均空(为叶子节点)
p = NULL;
} else if (p->lchild == NULL) {//2.1.*p左子树为空
if (f->lchild == p)
f->lchild = p->rchild;
else {
f->rchild = p->rchild;
}
delete p;
} else if (p->rchild == NULL) {//2.2.*p右子树为空
if (f->lchild == p)
f->lchild = p->lchild;
else {
f->rchild = p->lchild;
}
delete p;
} else {//3.左右子树均不空
BSTNode *q = p->rchild;//*q为直接后继(*p右子树的最左节点)
BSTNode *q_f = p;
while (q->lchild) {
q_f = q;//*q_f为*q的双亲结点, 如果进入while循环, *q必为*q_f的左孩子
q = q->lchild;
}
p->data = q->data;//将直接后继(*p右子树的最左节点)的值赋给*p
if (q_f == p) {
q_f->rchild = q->rchild;//未进入while循环, 代表直接后继*q为*p的右孩子, 此结点*q必无左子树
} else {
q_f->lchild = q->rchild;//进入while循环, 代表直接后继为*p的右子树的最左节点, 此结点*q必无左子树
}
delete q;
}
}
/*------------二叉树的中序遍历------------*/
void InorderTree(BSTree T) {
if (T) {
InorderTree(T->lchild);
cout << T->data.key << " ";
InorderTree(T->rchild);
}
}
int main() {
BSTree T = NULL;
CreatBST(T);//创建一棵二叉排序树
InorderTree(T);//中序遍历二叉树
cout << endl;
cout << "请输入您要查询的元素：" << endl;
int k = 0;
cin >> k;
BSTree T1 = NULL;//定义T1用来接收查找结果
T1 = SearchBST(T, k);
if (T1) cout << "存在此元素！" << endl;
else cout << "不存在此元素！" << endl;
int key = 0;
cout << "请输入您要删除的元素：" << endl;
cin >> key;
DeleteBST(T, key);//删除元素
InorderTree(T);//再次中序遍历二叉树
return 0;
}
