思路:要输出层次遍历的结果,必须先重建二叉树。我在以前的博客中有讲过怎么重建二叉树,层次遍历借助队列来完成。
struct BinaryTreeNode { int value; BinaryTreeNode* left; BinaryTreeNode* right; }; //重建二叉树 BinaryTreeNode* Construct(int* preorder,int* preorderend,int* inorder,int* inorderend) { if(preorder==NULL||preorderend==NULL||inorder==NULL||inorderend==NULL) return NULL; int rootval=preorder[0]; //根节点的值 BinaryTreeNode* root=new BinaryTreeNode(); root->value =rootval; if(preorder==preorderend) //只有一个节点 { if(inorder==inorderend) return root; else //中序数组中不只有一个节点,异常 return NULL; } //在中序数组中,找root节点 int* rootinorder=inorder; while(rootinorder!=inorderend&&rootval!=(*rootinorder)) ++rootinorder; if(rootinorder==inorderend&&rootval!=(*rootinorder)) //没有找到 return NULL; int len=rootinorder-inorder; //左子树的长度 if(len>0) { //构建左子树 root->left =Construct(preorder+1,preorder+len,inorder,rootinorder-1); } if(len<preorderend-preorder) //左子树长度<总长度 { //构建右子树 root->right =Construct(preorder+len+1,preorderend,rootinorder+1,inorderend); } return root; } //层次遍历 void Levelorder(BinaryTreeNode* root) { if(root==NULL) return; queue<BinaryTreeNode*> q; q.push(root); while(!q.empty()) { BinaryTreeNode* cur=q.front (); cout<<cur->value <<" "; q.pop(); if(cur->left !=NULL) { q.push (cur->left ); } if(cur->right !=NULL) { q.push (cur->right ); } } } void test() { int n=0; cin>>n; //树的节点个数 int* preorder=new int[n]; int* inorder=new int[n]; for(int i=0;i<n;++i) { cin>>preorder[i]; } for(int j=0;j<n;j++) { cin>>inorder[j]; } BinaryTreeNode* root=Construct(preorder,preorder+n-1,inorder,inorder+n-1); Levelorder(root); }