PAT_甲级_1099 Build A Binary Search Tree

题目大意:

给定一颗二叉查找树的结构和一些待插入数字,要求输出该二叉树的层序遍历序列

算法思路:

道题和1064的思路是一样的,都是紧紧把握一条,就是利用给定的二叉树的信息获得中序遍历的结点的下标序列,对给定的待插入数字进行排序得到中序遍历的结点的数字序列,然后两者一一对应就可以将该二叉查找树构造出来。这里由于输入的是结点的编号,那么用二叉树的静态存储方法比较方便,使用in数组保存结点中序遍历的编号序列。在输入完毕后,对二叉树进行中序遍历,根节点为0,将in数组中的数字按照遍历顺序依次填入到二叉树中,就可以完成二叉树的构建,然后再进行层序遍历并进行输出即可。
PAT_甲级_1099 Build A Binary Search Tree_第1张图片

提交结果:

PAT_甲级_1099 Build A Binary Search Tree_第2张图片

AC代码:

#include
#include
#include

using namespace std;

struct Node{
    int data;
    int left;
    int right;
}node[105];

int N;
int in[105];//中序遍历序列 
int inIndex = 0;//中序序列工作指针 

void preTraverse(int root){
    if(root==-1) return;
    preTraverse(node[root].left);
    node[root].data = in[inIndex++];
    preTraverse(node[root].right);
}

int num=0;//控制空格的输出 
void levelTraverse(int root){
    queue q;
    q.push(root);
    while(!q.empty()){
        int t = q.front();
        q.pop();
        printf("%d",node[t].data);
        if(num

你可能感兴趣的