Cartesian Tree

PAT-1167

一开始我使用数组进行存储，但是这样可能会导致无法开足够大的数组，因为树如果是链表状的则无法开这么大的数组（虽然结点很少）。
正确的解法还是需要建树，使用指针。

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<cstdio>

#include<sstream>

#include<set>

#include<map>

#include<cmath>

#include<vector>

#include<unordered_map>

#include<queue>

using namespace std;

const int INF=0X3F3F3F3F;

int n;

const int maxn=1003;

int a[maxn];//中序遍历

int tree[8*maxn];

int buildHeap(int root,int inl,int inr){

	if(inl>inr)

		return -1;

	int mid=INF;

	int midi=0;

	for(int i=inl;i<=inr;i++){

		if(a[i]<mid){

			mid=a[i];

			midi=i;

		}

	}

	tree[root<<1]=buildHeap(root<<1,inl,midi-1);

	tree[root<<1|1]=buildHeap(root<<1|1,midi+1,inr);

	return mid;

}

int main(){

	cin>>n;

	for(int i=0;i<n;i++){

		cin>>a[i];

	}

	tree[1]=buildHeap(1,0,n-1);

	queue<int>que;

	que.push(1);

	vector<int>ve;

	while(!que.empty()){

		int root=que.front();

		que.pop();

		ve.push_back(tree[root]);

		int lroot=root<<1;

		int rroot=root<<1|1;

		if(tree[lroot]!=-1){

			que.push(lroot);

		}

		if(tree[rroot]!=-1){

			que.push(rroot);

		}

	}

	for(int i=0;i<ve.size();i++){

		if(i==(int)ve.size()-1){

			cout<<ve[i]<<endl;

		}else{

			cout<<ve[i]<<" ";

		}

	}

	return 0;

}

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<cstdio>

#include<sstream>

#include<set>

#include<map>

#include<cmath>

#include<vector>

#include<unordered_map>

#include<queue>

using namespace std;

const int INF=0X3F3F3F3F;

int n;

const int maxn=1003;

int a[maxn];//中序遍历

int tree[8*maxn];

struct Node{

	int data;

	Node* left;

	Node* right;

};

Node* buildHeap(int inl,int inr){

	if(inl>inr)

		return NULL;

	int mid=INF;

	int midi=0;

	for(int i=inl;i<=inr;i++){

		if(a[i]<mid){

			mid=a[i];

			midi=i;

		}

	}

	Node* now=new Node();

	now->data=mid;

	now->left=buildHeap(inl,midi-1);

	now->right=buildHeap(midi+1,inr);

	return now;

}

int main(){

	cin>>n;

	for(int i=0;i<n;i++){

		cin>>a[i];

	}

//	cout<<"ue"<<endl;

	Node* root=buildHeap(0,n-1);

	queue<Node*>que;

	que.push(root);

	vector<int>ve;

	while(!que.empty()){

		Node* now=que.front();

		que.pop();

		ve.push_back(now->data);

		if(now->left!=NULL){

			que.push(now->left);

		}

		if(now->right!=NULL){

			que.push(now->right);

		}

	}

	for(int i=0;i<ve.size();i++){

		if(i==(int)ve.size()-1){

			cout<<ve[i]<<endl;

		}else{

			cout<<ve[i]<<" ";

		}

	}

	return 0;

}

巴特西

PAT-1167（Cartesian Tree）根据中序遍历序列重建最小堆

Cartesian Tree

PAT-1167

最新文章

热门文章