PAT甲级1099.

目录

A1099

题目

样例

输入:

9
1 6
2 3
-1 -1
-1 4
5 -1
-1 -1
7 -1
-1 8
-1 -1
73 45 11 58 82 25 67 38 42

输出:

58 25 82 11 38 67 45 73 42

思路和坑点

　　二叉搜索树的中序遍历结果是有序的，因此先读入树的结构，然后得到中序遍历的结果，将结点的数值排序后安排入座，最后使用层序遍历输出。要学会使用静态数组表示的二叉树的写法和操作。

AC代码

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm> 
#include<map>
#include<unordered_map>
#include<vector>
#include<queue> 
#include<stack>
#include<string>
using namespace std;
typedef struct node{    //结点结构体 
    int data;           //数据 
    int left,right;     //左右指针，初始化为-1 
    node(){
        left=-1;
        right=-1;
        data=0;
    }
}Node;
vector<Node> v;                 //保存所有结点 
vector<int> num;                //保存各结点的数据 
vector<int> inorder;            //中序遍历序列，用于对比安放结点数据 
void Inorder(int root);         //中序遍历 
void laorder(int root);         //层序遍历 

int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n;
    scanf("%d",&n);             //读入树的结构 
    for(int i=0;i<n;i++){
        Node temp;
        scanf("%d%d",&temp.left,&temp.right);
        v.push_back(temp);
    }
    for(int i=0;i<n;i++){       //读入结点数值 
        int temp;
        scanf("%d",&temp);
        num.push_back(temp);
    }
    sort(num.begin(),num.end());//搜索树的中序遍历有序 
    Inorder(0);                 //获取中序遍历序列 
    for(int i=0;i<n;i++){       //匹配各结点数值 
        int k=inorder[i];
        v[k].data=num[i];
    }
    laorder(0);                 //层序遍历 
    return 0;    
}
void Inorder(int root)          //递归实现中序遍历 
{
    if(root==-1)    return;
    Inorder(v[root].left);
    inorder.push_back(root);
    Inorder(v[root].right);
}
void laorder(int root)          //使用队列实现层序遍历 
{
    int cnt=0;
    queue<int> q;
    q.push(root);
    while(!q.empty()){
        int now=q.front();
        if(cnt) putchar(' ');
        printf("%d",v[now].data);
        cnt++;
        q.pop();
        if(v[now].left!=-1) q.push(v[now].left);
        if(v[now].right!=-1) q.push(v[now].right);   
    }
}