#include<iostream>

#include<deque>

using namespace std;

struct BinaryTreeNode

{

    int m_nValue;

    BinaryTreeNode* m_pLeft;

    BinaryTreeNode* m_pRight;

};

BinaryTreeNode* constructCore(int* preOrderStart,int* preOrderEnd,int* inOrderStart,int* inOrderEnd)

{

    int value=*preOrderStart;

    BinaryTreeNode* root=new BinaryTreeNode();

    root->m_nValue=value;

    root->m_pLeft=root->m_pRight=NULL;

    //当只有一个节点时

    if(preOrderStart==preOrderEnd)

    {

        if(inOrderStart==inOrderEnd&&*preOrderStart==*inOrderStart)

            return root;

        else

            throw std::exception("inVaild input");

    }

    //当有多个节点的时候

    int* rootInOrder=inOrderStart;

    while(rootInOrder<inOrderEnd&&*rootInOrder!=value)

    {

        rootInOrder++;

    }

    if(rootInOrder==inOrderEnd&&*rootInOrder!=value)

        throw std::exception("inVaild input");

    int leftLength=rootInOrder-inOrderStart;

    int rightLength=inOrderEnd-rootInOrder;

    if(leftLength>)

        root->m_pLeft=constructCore(preOrderStart+,preOrderStart+leftLength,inOrderStart,inOrderStart+leftLength-);

    if(rightLength>)

        root->m_pRight=constructCore(preOrderStart+leftLength+,preOrderEnd,inOrderStart+leftLength+,inOrderEnd);

    return root;

}

BinaryTreeNode* construct(int * preOrder,int* inOrder,int length)

{

    if(preOrder==NULL||inOrder==NULL||length<)

        return NULL;

    return constructCore(preOrder,preOrder+length-,inOrder,inOrder+length-);

}

void printNode(BinaryTreeNode* pNode)

{

    if(pNode==NULL)

        return;

        cout<<"this node is:  "<<pNode->m_nValue<<endl;

    if(pNode->m_pLeft!=NULL)

        cout<<"the left node is:  "<<pNode->m_pLeft->m_nValue<<endl;

    else

        cout<<"the left node is NULL"<<endl;

    if(pNode->m_pLeft!=NULL)

        cout<<"the right node is:  "<<pNode->m_pRight->m_nValue<<endl;

    else

        cout<<"the right node is NULL"<<endl;

}

void printBiTree(BinaryTreeNode* root)

{

    if(root==NULL)

        return;

    printNode(root);

    if(root->m_pLeft!=NULL)

        printBiTree(root->m_pLeft);

    if(root->m_pRight!=NULL)

        printBiTree(root->m_pRight);

}

void main()

{

    int a[]={,,};

    int b[]={,,};

    BinaryTreeNode* pHead=construct(a,b,);

    printBiTree(pHead);

}

import java.util.LinkedList;

import java.util.Queue;

public class PrintFromTopToBottom {

    public static class BinaryTreeNode{

        int m_nValue;

        BinaryTreeNode m_pLeft;

        BinaryTreeNode m_pRight;

    }

    public static BinaryTreeNode CreateBiTree(int[] preorder,int start,int[] inorder,int end,int length){

        if(preorder==null||inorder==null||preorder.length!=inorder.length||length<0)

            return null;

        BinaryTreeNode pRoot=new BinaryTreeNode();

        int value=preorder[start];

        pRoot.m_nValue=value;

        pRoot.m_pLeft=pRoot.m_pRight=null;

        //只有一个节点的时候

        if(length==1){

            if(preorder[start]==inorder[end])

                return pRoot;

            else

                throw new RuntimeException("inVaild input!");

        }

        //有多个节点的时候

        int i=0;

        while(i<length){

            if(value==inorder[end-i])

                break;

            i++;

        }

        if(i==length)

            throw new RuntimeException("inVaild input!");

        pRoot.m_pLeft=CreateBiTree(preorder,start+1,inorder,end-i-1,length-i-1);

        pRoot.m_pRight=CreateBiTree(preorder,start+length-i,inorder,end,i);

        return pRoot;

  }

    public static void printFromTopToBottom(BinaryTreeNode pHead){

        if(pHead==null)

            return;

        Queue<BinaryTreeNode> queue=new LinkedList<BinaryTreeNode>();

        queue.add(pHead);

        while(!queue.isEmpty()){

            BinaryTreeNode pNode=queue.poll();

            System.out.println(pNode.m_nValue);

        if(pNode.m_pLeft!=null)

            queue.add(pNode.m_pLeft);

        if(pNode.m_pRight!=null)

            queue.add(pNode.m_pRight);

        }

    }

    public static void main(String[] args)

    {

        int[] a={3,5,6};

        int[] b={5,3,6};

        BinaryTreeNode pHead=CreateBiTree(a,0,b,2,a.length);

        printFromTopToBottom(pHead);

    }

}