折纸

题目描述： >一张纸对折，折痕有向上的有向下的，给出折叠的次数n，输出每个折痕的朝向

分析：

折痕的朝向的分布满足二叉树，左子树均为下，右子树均为上，折叠次数n即为二叉树的深度，建立一棵二叉树再通过遍历即可输出折痕的朝向，为了减轻复杂度，在建立的时候即输出朝向

#include<iostream> 
#include"stdlib.h"
#include<time.h>
using namespace std;
template<class T>
struct TreeNode{
	T element;
	TreeNode<T>* lchild;
	TreeNode<T>* rchild;
	TreeNode(){
		lchild=rchild=NULL;}
	TreeNode(T key){
	element=key;
	lchild=rchild=NULL;
	}
};

template<typename T> 
TreeNode<T>* PreCreateTree(TreeNode<T>* root,int n) { //先序创建二叉树
		if (n == 0){
			return NULL;
		}		
		TreeNode<int>myTree1;root->lchild=&myTree1;
        root->lchild->element = 1;
        PreCreateTree(root->lchild,n-1);
        if(root->element==1)
        cout<<"下"; 
        else
		cout<<"上" ; 
        TreeNode<int>myTree2;root->rchild=&myTree2;
        root->rchild->element = 2;
        PreCreateTree(root->rchild,n-1);
    	return root;
     }   	   

int main(){
	TreeNode<int>myTree1;
	myTree1.element=1;
	TreeNode<int>* myTree=&myTree1;
	PreCreateTree(myTree,5);
	
}