二叉树的一些遍历模板

这是一棵二叉树

struct tree{
	int data;
	tree * lchild;
	tree * rchild;
};

遍历二叉树：

void printtree_f(tree *BT){ //前序遍历
	if(!BT) return;
	else{
		cout << BT->data << " ";
		printtree_f(BT->lchild);
		printtree_f(BT->rchild);
	}
}

void printtree_m(tree *BT){ //中序遍历
	if(!BT) return;
	else{
		printtree_m(BT->lchild);
		cout << BT->data << " ";
		printtree_m(BT->rchild);
		
	}
}

void printtree_b(tree *BT){ //后序遍历
	if(!BT) return;
	else{
		printtree_b(BT->lchild);
		printtree_b(BT->rchild);
		cout << BT->data << " ";
	}
}

void printtree_s(tree *BT){ //按层遍历
	queue<tree*> vec;
	vec.push(BT);
	while(!vec.empty()){
		tree * top = vec.front();
		if(top->lchild!=NULL) vec.push(top->lchild);
		if(top->rchild!=NULL) vec.push(top->rchild);
		cout << top->data << " ";
		vec.pop();
	}
	return;
}

先序遍历和中序遍历构建二叉树：

tree * createtree(int prestart,int preend,int instart,int inend,int pre[],int in[]){
	tree * BT = new tree;
	if(prestart>preend||instart>inend) return NULL;
	if(prestart==preend&&instart==inend){
		BT->lchild=NULL;
		BT->rchild=NULL;
		BT->data=pre[prestart];
		return BT;
	}
	int front=pre[prestart];int i;
	for(i=0;i<n;i++) if(in[i]==front) break;
	int partleft=i-instart;
	int partright=inend-i;
	BT->data=front;
	BT->lchild=createtree(prestart+1,prestart+partleft,instart,i-1,pre,in);
	BT->rchild=createtree(prestart+1+partleft,prestart+partleft+partright,i+1,i+partright,pre,in);
	return BT;
}

后序和中序构建二叉树：

tree * createfront(int postfront,int postend,int infront,int inend,int post[],int in[]){
	if(postfront>postend||infront>inend) return NULL;
	if(postfront==postend&&infront==inend){
		tree * leave=new tree;
		leave->data=post[postend];
		leave->lchild=NULL;
		leave->rchild=NULL;
		return leave;
	}
	int chroot=post[postend];
	int i;
	for(i=postfront;i<=postend;i++) if(in[i]==chroot) break;
	tree * BT=new tree;
	BT->data=chroot;
	BT->lchild=createfront(postfront,postfront+i-infront-1,infront,i-1,post,in);
	BT->rchild=createfront(postend+i-inend,postend-1,i+1,inend,post,in);
	return BT;
}