首页 > 代码库 > 北邮2012复试机考 3T
北邮2012复试机考 3T
97. 二叉排序树
时间限制 1000 ms 内存限制 65536 KB
题目描述
二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树：
- 若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值；
- 若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值；
- 左、右子树本身也是一颗二叉排序树。
现在给你N个关键字值各不相同的节点，要求你按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。
输入格式
第一行，一个数字N（N<=100），表示待插入的节点数。
第二行，N个互不相同的正整数，表示要顺序插入节点的关键字值，这些值不超过108。
输出格式
输出共N行，每次插入节点后，该节点对应的父亲节点的关键字值
输入样例
52 5 1 3 4输出样例
-12253
分析 ： STL中的 set 和 map 都是用二叉排序树实现的，这道题要输出父节点，用这两个不好实现，
解决方法是自己写一个返回父节点的二叉排序树
代码：
#include<iostream>#include<cstdio>#include<string>using namespace std;struct node{ int val; node *lch,*rch;};node *insert(node *p,int x){ if(p==NULL) { node *q=new node; q->val=x; q->lch=q->rch=NULL; return q; } else { if(x< p->val) p->lch=insert(p->lch,x); else p->rch=insert(p->rch,x); return p; }}node *find(node *p,int x,node *my){ if(p==NULL) return my; else if(x==p->val) return my; else if(x< p->val) return find(p->lch,x,p); else return find(p->rch,x,p);}int main(){ int num,temp[105],n; node *donser=NULL,*don=NULL,*dons=NULL; scanf("%d",&num); for(int i=1;i<=num;i++) { scanf("%d",&n); donser=insert(donser,n); temp[i]=n; } cout<<"-1"<<endl; for(int i=2;i<=num;i++) { dons=find(donser,temp[i],don); cout<< dons->val <<endl; } return 0;}
北邮2012复试机考 3T
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。