树的遍历有层次遍历，前序遍历，中序遍历，后序遍历。 我们知道了可以根据前序和中序遍历， 后序和中序遍历唯一确定一棵二叉树。 前序遍历：根左右 中序遍历：左根右 后序遍历：左右根 根据前序遍历和中序遍历确定一棵二叉树
struct node { int data; node *left,*right; }; int pre_order[1000],in_order[1000]; node* build(int p1,int p2,int l1,int l2)//前序的下标，中序的下标 { if(p2<p1) return NULL; node *root=new node; root->data=pre_order[p1]; int p=l1; while(in_order[p]!=root->data) p++; int cnt=p-l1; root->left=build(p1+1,p1+cnt,l1,l1+cnt-1); root->right=build(p1+cnt+1,p2,l1+cnt+1,l2); }先将后序遍历倒序输入到数组post_order,然后这个数组就是根右左
node* build(int p1,int p2,int l1,int l2)//后序的下标，中序的下标 { if(p1>p2||l2<l1||p2>n||l2>n) return NULL; node *root=new node; root->data=pre_order[p1]; int p=l2; while(in_order[p]!=root->data) p--; int cnt=l2-p;//cnt 是右子树的点数 root->right=build(p1+1,p1+cnt,l2-cnt+1,l2); root->left=build(p1+cnt+1,p2,l1,l1+cnt-1); }层次遍历
void level(BTNode *t) { if(t==NULL) return ; queue<BTNode *> Q; Q.push(t); while(!Q.empty()) { t=Q.front(); Q.pop(); cout<<t->data; if(t->left) Q.push(t->left); if(t->right) Q.push(t->right); } }