树的深度、顺序输出树

#include <stdio.h> #include <stdlib.h> #include <queue> using namespace std; typedef struct BiTNode{ int value; struct BiTNode *lchild; struct BiTNode *rchild; }BiTNode,*BiTree; BiTree rebuild(int perorder[],int perstart,int perend,int inorder[],int instart,int inend){//后序与中序构建一棵树(顺序可变，只需做少许改动) if(perend-perstart!=inend-instart){ return NULL; } if(perstart>perend){ return NULL; } BiTree tree=(BiTree)malloc(sizeof(BiTNode)); tree->value=perorder[perend]; tree->lchild=NULL; tree->rchild=NULL; if(perstart==perend){ return tree; } int index,length; for(index=instart;index<=inend;index++){ if(perorder[perend]==inorder[index]) break; } if(index>inend){ return NULL; } if(index>instart){ length=index-instart; tree->lchild=rebuild(perorder,perstart,perstart+length-1,inorder,instart,instart+length-1); } if(index<inend){ length=inend-index; tree->rchild=rebuild(perorder,perend-length,perend-1,inorder,inend-length+1,inend); } return tree; } int dtree(BiTree t){//求树的深度 int deep=0; if(t){ int ldeep=dtree(t->lchild); int rdeep=dtree(t->rchild); deep=ldeep>=rdeep?ldeep+1:rdeep+1; } return deep; } void bfs(BiTree t){//广度优先顺序输出二叉树 if(t==NULL){ return; } queue<BiTree >q; q.push(t); while(!q.empty()){ BiTree s=q.front(); q.pop(); printf("%d ",s->value); if(s->lchild!=NULL){ q.push(s->lchild); } if(s->rchild!=NULL){ q.push(s->rchild); } } } int main(){ int n; int perorder[31],inorder[31]; scanf("%d",&n); getchar(); for(int i=0;i<n;i++){ scanf("%d",&perorder[i]); } for(int i=0;i<n;i++){ scanf("%d",&inorder[i]); } BiTree tree=rebuild(perorder,0,n-1,inorder,0,n-1); bfs(tree); return 0; }