首页 > 其他 > 详细

二叉搜索树的建树与遍历

时间:2018-05-27 14:15:30      阅读:194      评论:0      收藏:0      [点我收藏+]

注意要插入的值,如果等于当前节点,就把它变成当前节点的右儿子

此代码是中南大学暑训入门 B题的AC代码

#include<iostream>
#define ll long long
using namespace std;
struct node
{
    ll data;
    node * lson;
    node * rson;
}*head;
int t;

void build(ll x,node *p)
{
    if(p==NULL){
        node * pp;
        pp=new node ;
        pp->data=x;
        pp->lson=NULL;
        pp->rson=NULL;
        head=pp;
        return;
    }

    if(p->data<=x&&p->rson){build(x,p->rson);}
    else if(p->data>x&&p->lson){build(x,p->lson);}
    else if(p->data<=x&&!p->rson){
        node * pp;
        pp=new node ;
        pp->data=x;
        pp->lson=NULL;
        pp->rson=NULL;
        p->rson=pp;
    }
    else if(p->data>x&&!p->lson){
        node * pp;
        pp=new node ;
        pp->data=x;
        pp->lson=NULL;
        pp->rson=NULL;
        p->lson=pp;
    }
}

void preview(node *p)
{
    if(p==NULL){return;}
    if(t){cout<<" ";}
    cout<<p->data;t++;
    preview(p->lson);
    preview(p->rson);
}

void midview(node *p)
{
    if(p==NULL){return;}
    midview(p->lson);
    if(t)cout<<" ";
    cout<<p->data;t++;
    midview(p->rson);
}

void posview(node *p)
{

    if(p==NULL){return;}
    posview(p->lson);
    posview(p->rson);
    if(t){cout<<" ";}
    cout<<p->data;t++;
}

void delet(node *p)
{

    if(p==NULL){return;}
    delet(p->lson);
    delet(p->rson);
    delete p;

}

int main()
{
    int T;
    while(cin>>T)
    while(T--){
        int n;
        ll x;
        cin>>n;
        head=NULL;
        for(int i=0;i<n;i++){
            cin>>x;
            build(x,head);
        }
        t=0;
        preview(head);
        cout<<endl;
        t=0;
        midview(head);
        cout<<endl;
        t=0;
        posview(head);
        cout<<endl;
        delet(head);
        cout<<endl;
    }
}

  

二叉搜索树的建树与遍历

原文:https://www.cnblogs.com/ZGQblogs/p/9095867.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!