基于二叉排序树的各种操作

第一步：定义栈

因为要中序遍历，所以要定义栈。

typedef struct Snode{
    BSTree data;
    struct Snode *next;
}Snode , *LinkStack;
//初始化
bool InitStack(LinkStack &s){
    s = NULL;
    return true;
}
//判断是否为空
bool Empty(LinkStack s){
    if(s == NULL) return true;
    return false;
}
//入栈
bool Push(LinkStack &s , BSTree e){
    LinkStack p = new Snode;
    p -> data = e;
    p -> next = s;
    s = p;
    return true;
}
//出栈
bool Pop(LinkStack &s , BSTree &e){
    if(Empty(s)) return false;
    e = s->data;
    LinkStack p = s;
    s = s->next;
    delete p;
    return true;
}
//取栈顶元素
BSTree GetTop(LinkStack s){
    return s->data;
}

第二步，定义二叉排序树的结构：

typedef struct
{
    int key;                  //关键字项
}ElemType;                     // 每个节点的数据类型
typedef struct BSTNode
{
    ElemType data;                      //每个节点的数据域包括关键字项和其他数据项
    struct BSTNode *lchild, *rchild;    // 左右孩子指针
}BSTNode , *BSTree;

第三步，查询树：

BSTree SearchBST (BSTree T , int 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){
    //当二叉排序树T中不存在关键字等于e.key的数据元素时 ，则插入该元素
    if(!T){
        BSTree S = new BSTNode;        //生成新节点*S
        S->data = e;                   // 新节点*s的数据域置为e
        S->lchild = S->rchild = NULL;   // 新节点作为叶子节点
        T = S;                  // 把新节点*S连接到以找到的插入位置
    }
    else if(e.key < T->data.key) {
        InsertBST(T->lchild, e);
    }
    else if(e.key > T->data.key) {
        InsertBST(T->rchild, e);
    }
}

第五步，删除元素：

课本上是用中序遍历结果的前驱来替换被删除元素，我们用后继来替换

//删除
void DeleteBST(BSTree &T, int key){
    //从二叉排序树T中删除关键字等于key的节点
    BSTree p = T, f =NULL;//P为指向节点的指针f为指向双亲节点的指针
    BSTree s = new BSTNode;
    while(p){
        if(p->data.key == key ) break;
        f = p;
        if(p->data.key > key) p = p->lchild;
        else p = p->rchild;
    }
    
    if(!p) return ; // 找不到被删结点则返回
    BSTree q = new BSTNode;
    q = p;
    if((p->lchild) && (p->rchild))    // 被删节点*p左右字数均不为空
    {
        s = p->rchild;
        while(s->lchild){          //在*p的右子树中继续查找其后继节点，即最左下节点
            q = s;
            s = s->lchild;          //向左走到尽头；
        }
        p->data = s->data;              //s指向被删结点的“后继”
        if(q!=p) q->lchild = s->rchild;    // 重接q的左子树
        else q->rchild = s->rchild;         //重接q的右子树
        delete s;
        return;
    }
    else if (!p->rchild){
        p = p->lchild;
    }
    else if(!p->lchild){
        p = p->rchild;
    }
    
    if(!f)  T = p;
    else if(q == f->lchild) f->lchild = p;
    else f -> rchild = p;
    delete q;
    
}

第六步，创建树；

//创建
void CreatBST(BSTree &T){
    ElemType e;
    T = NULL;
    cin>> e.key;
    while(e.key !=ENDFLAG){
        InsertBST(T, e);
        cin>>e.key;
    }
}

第七步，中序遍历二叉树；

//中序遍历树
LinkStack s,s1,s2;
void InOrderTraverse (BSTree T) {
    InitStack(s);
    BSTree p = new BSTNode;
    p = T;
    BSTree q = new BSTNode;
//    BiTree q1 = new BiTNode;
    while(p || !Empty(s)){
        if(p) {
            Push(s,p);
            p = p ->lchild;
        }
        else {
            Pop(s,q);
            cout << q->data.key<<" ";
            p = q->rchild;
        }
    }
    cout << "\n";
}

完工！！完整代码

//
//  main.cpp
//  第七次实验
//
//  Created by 宋玉良 on 2020/12/10.
//
#include<bits/stdc++.h>
#define ENDFLAG 0
using namespace std;

typedef struct
{
    int key;                  //关键字项
}ElemType;                     // 每个节点的数据类型
typedef struct BSTNode
{
    ElemType data;                      //每个节点的数据域包括关键字项和其他数据项
    struct BSTNode *lchild, *rchild;    // 左右孩子指针
}BSTNode , *BSTree;


typedef struct Snode{
    BSTree data;
    struct Snode *next;
}Snode , *LinkStack;
//初始化
bool InitStack(LinkStack &s){
    s = NULL;
    return true;
}
//判断是否为空
bool Empty(LinkStack s){
    if(s == NULL) return true;
    return false;
}
//入栈
bool Push(LinkStack &s , BSTree e){
    LinkStack p = new Snode;
    p -> data = e;
    p -> next = s;
    s = p;
    return true;
}
//出栈
bool Pop(LinkStack &s , BSTree &e){
    if(Empty(s)) return false;
    e = s->data;
    LinkStack p = s;
    s = s->next;
    delete p;
    return true;
}
//取栈顶元素
BSTree GetTop(LinkStack s){
    return s->data;
}
//中序遍历树
LinkStack s,s1,s2;
void InOrderTraverse (BSTree T) {
    InitStack(s);
    BSTree p = new BSTNode;
    p = T;
    BSTree q = new BSTNode;
//    BiTree q1 = new BiTNode;
    while(p || !Empty(s)){
        if(p) {
            Push(s,p);
            p = p ->lchild;
        }
        else {
            Pop(s,q);
            cout << q->data.key<<" ";
            p = q->rchild;
        }
    }
    cout << "\n";
}
//查找
BSTree SearchBST (BSTree T , int 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){
    //当二叉排序树T中不存在关键字等于e.key的数据元素时 ，则插入该元素
    if(!T){
        BSTree S = new BSTNode;        //生成新节点*S
        S->data = e;                   // 新节点*s的数据域置为e
        S->lchild = S->rchild = NULL;   // 新节点作为叶子节点
        T = S;                  // 把新节点*S连接到以找到的插入位置
    }
    else if(e.key < T->data.key) {
        InsertBST(T->lchild, e);
    }
    else if(e.key > T->data.key) {
        InsertBST(T->rchild, e);
    }
}

//创建
void CreatBST(BSTree &T){
    ElemType e;
    T = NULL;
    cin>> e.key;
    while(e.key !=ENDFLAG){
        InsertBST(T, e);
        cin>>e.key;
    }
}
//删除
void DeleteBST(BSTree &T, int key){
    //从二叉排序树T中删除关键字等于key的节点
    BSTree p = T, f =NULL;//P为指向节点的指针f为指向双亲节点的指针
    BSTree s = new BSTNode;
    while(p){
        if(p->data.key == key ) break;
        f = p;
        if(p->data.key > key) p = p->lchild;
        else p = p->rchild;
    }
    
    if(!p) return ; // 找不到被删结点则返回
    BSTree q = new BSTNode;
    q = p;
    if((p->lchild) && (p->rchild))    // 被删节点*p左右字数均不为空
    {
        s = p->rchild;
        while(s->lchild){          //在*p的左子树中继续查找其前驱节点，即最左下节点
            q = s;
            s = s->lchild;          //向左走到尽头；
        }
        p->data = s->data;              //s指向被删结点的“后继”
        if(q!=p) q->lchild = s->rchild;    // 重接q的左子树
        else q->rchild = s->rchild;         //重接q的右子树
        delete s;
        return;
    }
    else if (!p->rchild){
        p = p->lchild;
    }
    else if(!p->lchild){
        p = p->rchild;
    }
    
    if(!f)  T = p;
    else if(q == f->lchild) f->lchild = p;
    else f -> rchild = p;
    delete q;
    
}
int main()
{
    BSTree T = new BSTNode;
    cout << "请输入创建节点的值(输入0)结束"<<endl;
    CreatBST(T);
    cout << "创建的二叉排序树为："<< endl;
    InOrderTraverse(T);
    int n =3;
    while(n--){
        int Case;
        cout << "请输入操作序号，1查询，2插入，3删除" << endl;
        cin>>Case;
        if(Case == 3){
            cout << "请输入要删除的值"<<endl;
            int key;
            cin>>key;
            DeleteBST(T, key);
            cout << "二叉排序树为" << endl;
            InOrderTraverse(T);
        }
        else if(Case == 1){
            cout << "请输入要查询的值"  << endl;
            int key;
            cin >>key;
            if(SearchBST(T, key)){
                cout << "存在" << endl;
            }
            else cout << "不存在"<<endl;
        }
        else if(Case == 2){
            cout << "请输入要插入的值" << endl;
            BSTree key = new BSTNode;
            cin >> key->data.key;
            InsertBST(T, key->data);
            cout << "二叉排序树为" << endl;
            InOrderTraverse(T);
        }
    }
    cout << endl;
}