关于算法-数据结构:PAT甲级1064-Complete-Binary-Search-Tree

题目粗心：

给定 N 个结点的 CBT 的每一个结点的值, 要求输入对应的层序遍历序列

算法思路：

首先明确 CBT 的概念, 这里要求每一次尽可能的满, 除了最初一层, 这里的定义合乎齐全二叉树, 那么咱们能够对这颗齐全二叉树依照档次遍历序列进行编号, 这样便于输入层序遍历序列 (可能当初还不明确, 看到前面就好了), 为了不便轻松取得左孩子和右孩子咱们应用 1 来代表根节点的编号. 而后对于给定结点数量 N 的齐全二叉树, 其档次序列的编号是固定的就是 1,2,3…n, 那么咱们从 1 到 n 进行遍历, 对于每一个结点 i 如果有左孩子 $2*i<=n$, 那么就更新左孩子编号 $node[i].left = 2*i$, 如果有右孩子 $2*i+1<=n$, 那么
就更新右孩子编号 $node[i].right = 2*i+1$, 并且初始化所有结点的左右孩子都为 -1。接下来就是建树的过程，也是此题惟一的难点，咱们晓得二叉搜寻树的中序遍历序列 (数值) 是有序的，那么咱们将输出序列进行排序就能够失去中序遍历序列 (数值)，同样的，咱们把存储该树的动态数组的下标也进行排序，这样就失去了中序遍历序列数组的下标和数值，将它们一一对应就能够取得这颗树了，可能当初还是不太明确，看下图就好了。


其次要操作就是应用了一个 num 数组存储输出的数据，对其进行排序后就是中序遍历序列，而后咱们将一颗空树进行中序遍历，而后将值一一填入到结点中，就实现了树的创立。仔细观察就晓得，CBT 的层序遍历实际上就是动态数组依照程序顺次输入的后果。

提交后果：

AC 代码：

#include<cstdio>
#include<queue>
#include<algorithm>

using namespace std;

int N;
int num[1005];

struct Node{
    int data;
    int left;
    int right;
    Node(){left = right = -1;}
}node[1005];

int index = 1;// 中序序列指针 
void inTraverse(int root){if(root==-1) return;
    inTraverse(node[root].left);
    node[root].data = num[index++];
    inTraverse(node[root].right);
}

int main(){scanf("%d",&N);
    for(int i=1;i<=N;++i){scanf("%d",&num[i]);
        if(2*i<=N){
            // 有左孩子
            node[i].left = 2*i; 
        }
        if(2*i+1<=N){
            // 有右孩子
            node[i].right = 2*i+1; 
        }
    }
    // 将 num 数组进行排序取得树的中序遍历序列
    sort(num+1,num+N+1);
    // 中序遍历 node，将 num 数组插入其中, 根节点默认为 1
    inTraverse(1); 
    // 输入层序遍历序列 
    for(int i=1;i<=N;++i){printf("%d",node[i].data);
        if(i<N) printf(" ");
    }
    return 0;
}