7-4 Cartesian Tree (30分)

A Cartesian tree is a binary tree constructed from a sequence of distinct numbers. The tree is heap-ordered, and an inorder traversal returns the original sequence. For example, given the sequence { 8, 15, 3, 4, 1, 5, 12, 10, 18, 6 }, the min-heap Cartesian tree is shown by the figure.

Your job is to output the level-order traversal sequence of the min-heap Cartesian tree.

Input Specification:

Each input file contains one test case. Each case starts from giving a positive integer N (≤30), and then N distinct numbers in the next line, separated by a space. All the numbers are in the range of int.

Output Specification:

For each test case, print in a line the level-order traversal sequence of the min-heap Cartesian tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line.

Sample Input:

108 15 3 4 1 5 12 10 18 6`

Sample Output:

1 3 5 8 4 6 15 10 12 18

题目限度：

题目粗心：

现给定一颗笛卡尔树的中序序列，它满足小根堆的性质，当初须要输入其层序遍历。

算法思路：

大抵思路就是建树和层序遍历，其惟一的难点在于建树，其实只有晓得了根节点的地位就不是问题，首先咱们当初有这颗树的中序序列，保留在origin数组中，同时应用unordered_map<int,int> pos 保留每一个节点在中序序列中的地位，建树的要害是得只有每一个子树的根节点和在中序遍历中的地位，这里的子树都满足小根堆的性质，阐明在[inL,inR]之间最小的数字就是以后子树的根节点，那么咱们应用getMin取得original中的[left,right]最小的那个数字，代码如下：

// 在original的[left,right]中找到最小的那个数字int getMin(int left,int right){    int Min = 0x3fffffff;    for(int i=left;i<=right;++i){        Min = Min>original[i]?original[i]:Min;    }    return Min;}

接下来就能够应用createTree函数来进行建树了，代码如下：

Node* createTree(int inL,int inR){    if(inL>inR) return nullptr;    Node* root = new Node;    root->data = getMin(inL,inR);    int k = pos[root->data];// 根节点的地位     //[inL,k-1]为左子树    root->left = createTree(inL,k-1);    //[k+1,inR]为右子树    root->right = createTree(k+1,inR);    return root;}

最初就是层序遍历并输入。

留神点：

  • 1、结点数值有点偏大，应用数组保留结点的地位会导致段谬误，应用map比拟好

提交后果：

AC代码：

#include<cstdio>#include<queue>#include<unordered_map>using namespace std;struct Node{    int data;    Node *left;    Node *right;};int original[40];unordered_map<int,int> pos;// 每一个节点在中序序列中的地位// 在original的[left,right]中找到最小的那个数字int getMin(int left,int right){    int Min = 0x3fffffff;    for(int i=left;i<=right;++i){        Min = Min>original[i]?original[i]:Min;    }    return Min;}Node* createTree(int inL,int inR){    if(inL>inR) return nullptr;    Node* root = new Node;    root->data = getMin(inL,inR);    int k = pos[root->data];// 根节点的地位     //[inL,k-1]为左子树    root->left = createTree(inL,k-1);    //[k+1,inR]为右子树    root->right = createTree(k+1,inR);    return root;}int num = 0;void BFS(Node* root){    queue<Node*> q;    q.push(root);    while (!q.empty()){        Node* t = q.front();        q.pop();        if(num==0){            printf("%d",t->data);            ++num;        } else {            printf(" %d",t->data);        }        if(t->left){            q.push(t->left);        }        if(t->right){            q.push(t->right);        }    }}int main(){    int N;    scanf("%d",&N);    for (int i = 0; i < N; ++i) {        scanf("%d",&original[i]);        pos[original[i]] = i;    }    Node* root = createTree(0,N-1);    BFS(root);    return 0;}