编写程序在二叉树中查找给定结点及父结点。二叉树结点的数据域值不等于0的整数。
输入格式:
输入第1行为一组用空格间隔的整数,表示带空指针信息的二叉树先根序列,其中空指针用0表示。例如1 5 8 0 0 0 6 0 0表示如下图的二叉树。第2行为整数m,表示查询个数。接下来m行,每行为一个不等于0的整数K,表示要查找的结点的数据值。m不超过100,二叉树结点个数不超过150000,高度不超过6000。输入数据保证二叉树各结点数据值互不相等。
输出格式:
输出为m行,每行1个整数,表示被查找结点K的父结点数据值,若二叉树中无结点K或结点K无父结点,则输出0。
输入样例:
1 5 8 0 0 0 6 0 0
3
8
1
6
输出样例:
5
0
1
#include<iostream>
#include<map>
using namespace std;
const int N=15e3+100;
struct node{
int v;//结点值
int l,r;//左右孩子的下标
st()
{//初始化
l=r=-1;
}
}tree[4*N];//4倍空间,用来储存二叉树
map<int,int>mp;//储存数值在数组a中的下标
int a[N];//基础数组,数组tree在其基础上建树
int n=1;//1 5 8 0 0 0 6 0 0
void build_tree(int rt,int &num)
{//构建二叉树
if(a[num]==0)
{//a[num]==0,表示空结点
tree[rt].v=-1;
}
else
{
if(mp.count(a[num])==0)
mp[a[num]]=rt;//储存a[num]在树中的位置
tree[rt].v=a[num];//结点赋值
num++;
build_tree(2*rt,num);//左孩子
num++;
build_tree(2*rt+1,num);//右孩子
}
}
/*
1 5 8 0 0 0 6 0 0
3
8 1 6
*/
int main()
{
int x=1,m=0;
do
{
cin>>a[n++];//储存结点值
}
while(getchar()!='\n');//回车结束输入
build_tree(1,x);//构建二叉树(结构体数组模拟)
cin>>m;//查询次数
for(int i=0;i<m;i++)
{
int num,y;
cin>>num;//查询值
y=mp[num];//mp[num]是num在tree数组中的位置,查询效率O(log2n)
y/=2;//左右孩子的下标除以2,就是父节点的下标
if(y==0)
{//父节点下标为0,既是根节点
cout<<0<<endl;
}
else
{//输出父节点值
cout<<tree[y].v<<endl;
}
}
return 0;
}