unickcheng / competition Goto Github PK

int build(int l1,int r1,int l2,int r2)
{
	if(l1>r1) return 0;
	int node=post_order[r2];
	int p=l1;
	while(in_order[p]!=node) p++;
	ltree[node]=build(l1,p-1,l2,l2+p-l1-1);
	rtree[node]=build(p+1,r1,l2+p-l1,r2-1);
	return node;
}

void bfs(int root)
{//广度搜索进行层次遍历
	queue<int> q;
	q.push(root);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		printf("%d ",u);
		if(ltree[u]) q.push(ltree[u]);
		if(rtree[u]) q.push(rtree[u]);
	}
}

void proOrder(int node)
{//先序遍历
	printf("%d ",node);
	if(ltree[node]) pro(ltree[node]);
	if(rtree[node]) pro(rtree[node]);
}

void inOrder(int node)
{//中序遍历
	if(ltree[node]) pro(ltree[node]);
	printf("%d ",node);
	if(rtree[node]) pro(rtree[node]);
}

void postOrder(int node)
{//后序遍历
	if(ltree[node]) pro(ltree[node]);
	if(rtree[node]) pro(rtree[node]);
	printf("%d ",node);
}