二叉排序树的创建 、删除操作

二叉排序树的创建 、删除操作

【问题描述】

请根据输入的数据创建一棵二叉排序树。然后执行相应操作。

1 删除某一值为x的结点

2 求指定结点y在二叉排序树中的层数

【输入形式】

结点数据，以0代表结束输入。

待删除的x，待求层数的y

【输出形式】

删除后的二叉排序树的中序遍历结果

y所在的层数

【样例输入】

29 39 15 25 28 10 11 2 0

10

11

【样例输出】

2 11 15 25 28 29 39

4

【样例说明】

若待删除的结点包含左右子树，则以其左子树的最右结点代替它。

#include <iostream>
#include<bits/stdc++.h>
#define MAX 100
using namespace std;

/*这样定义在编译时会报错
struct BSTnode
{
    int data;
    BSTnode *Rchild,*Lchild;
}*BSTree;
错误如下:
error: variable or field 'InsertBST' declared void|
error: 'bst' was not declared in this scope|
error: expected primary-expression before 'int'|
*/

//定义二叉树（以后推荐使用这种定义方法，减少编译器识别时发生出乎意外的error）
typedef struct node
{
    int data;
    node *Rchild,*Lchild;
}*BSTree,BSTnode;//这里我目前理解为 *BTSree是一个指针，因为指针可以移动，所以可以代表这棵二叉树  、BSTnode表示的只是一个结构体单元，只能代表这棵树的一部分

/*使用指针传递,由于BSTree本身就是一个指针所以，这里就会变成使用指针的指针，在调用函数是还需要使用&，代码看起来就不是很明了
1.在参数框里的 *bst 表示的是定义一个指针的指针
2.在函数体里的*bst表示指针的指针取值，即是表示的是二叉树的指针（指针的指针--->指针）
void InsertBST(BSTree *bst,int data)
{
    BSTree t;
    if(*bst==NULL)
    {
        t=(BSTree)malloc(sizeof(BSTnode));
        t->data=data;
        t->Rchild=NULL;
        t->Lchild=NULL;
        *bst=t;
    }
    else if(data>(*bst)->data)
    {
        InsertBST(&((*bst)->Rchild),data);
    }
    else if(data<(*bst)->data)
    {
        InsertBST(&((*bst)->Lchild),data);
    }
}*/
//使用引用传递
void InsertBST(BSTree &bst,int data)
{
    BSTree t;
    if(bst==NULL)
    {
        t=(BSTree)malloc(sizeof(BSTnode));
        t->data=data;
        t->Rchild=NULL;
        t->Lchild=NULL;
        bst=t;
    }
    else if(data<bst->data)
    {
        InsertBST(bst->Lchild,data);
    }
    else if(data>bst->data)
    {
        InsertBST(bst->Rchild,data);
    }
}

void CreatBST(BSTree *bst)
{
    int data;
    *bst=NULL;
    cin>>data;
    while(data!=0)
    {
        InsertBST(*bst,data);//关于这个地方为什么bst需要带指针我还是迷惑的
        cin>>data;
    }
}
BSTnode *DelBST(BSTree bst,int data)
{
    BSTnode *p,*f,*s,*q;
    p=bst;f=NULL;
    while(p)
    {
        if(p->data==data) break;
        f=p;
        if(data>p->data)
        {
            p=p->Rchild;
        }
        else
        {
            p=p->Lchild;
        }

    }
    if(p==NULL) return bst;
    if(p->Lchild==NULL)
    {
        if(f==NULL) bst=p->Rchild;
        else if(f->Lchild=p)
        {
            f->Lchild=p->Rchild;
        }
        else
        {
            f->Rchild=p->Rchild;
        }
        free(p);//在树中短出来的结构单元需要free释放掉
    }
    else
    {
        q=p;s=p->Lchild;
        while(s->Rchild)
        {
            q=s;
            s=s->Rchild;
        }
        if(q==p) q->Lchild=s->Lchild;
        else q->Rchild=s->Lchild;
        p->data=s->data;
        free(s);
    }
    return bst;
}
void Inder(BSTree root)
{
    if(root)
    {
        Inder(root->Lchild);
        cout<<root->data<<" ";
        Inder(root->Rchild);
    }
}
void DeepNum(BSTree bst,int y)
{
    int num=1;
    while(bst)
    {
        if(bst->data==y)
        {
            cout<<num<<endl;
            break;
        }
        if(bst->data>y)
        {
            num+=1;
            bst=bst->Lchild;
        }
        else
        {
            num+=1;
            bst=bst->Rchild;
        }
    }
}
int main()
{
    BSTree bst;
    int deldata;//需要删掉的数据
    int y;//需要求节点层数的data
    CreatBST(&bst);
    cin>>deldata;
    bst=DelBST(bst,deldata);
    Inder(bst);
    cout<<endl;
    cin>>y;
    DeepNum(bst,y);
    return 0;
}

收获提炼：
1.结构体定义的方法不同，有时候编译的时候就会带来不一样的效果
2.函数参数传递的问题：
①值传递
void swap(int x,int y)
{
int tmp;
tmp=x;
x=y;
y=tmp;
}
调用时：swap(a,b);

②地址传递
void swap(int *x,int *y)
{
int tmp;
tmp=*x;
*x=*y;
*y=tmp;
}

swap(&a,&b);

③引用传递

void swap(int &x,int &y)
{
int tmp;
tmp=x;
x=y;
y=tmp;

}

swap(a,b);