题目：从上往下打印二叉树的每一个节点，同一层的节点按照从左到右的顺序打印
思路：这是一个层序遍历的问题，因此要借用到队列。我们可以在打印第一个节点的同时将这个节点的左右子节点都放入队列，同样打印左右子树。
抽象的问题具体化：
C++代码：
#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>0) root->m_pLeft=constructCore(preOrderStart+1,preOrderStart+leftLength,inOrderStart,inOrderStart+leftLength-1); if(rightLength>0) root->m_pRight=constructCore(preOrderStart+leftLength+1,preOrderEnd,inOrderStart+leftLength+1,inOrderEnd); return root; } BinaryTreeNode* construct(int * preOrder,int* inOrder,int length) { if(preOrder==NULL||inOrder==NULL||length<0) return NULL; return constructCore(preOrder,preOrder+length-1,inOrder,inOrder+length-1); } 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[]={3,5,6}; int b[]={5,3,6}; BinaryTreeNode* pHead=construct(a,b,3); printBiTree(pHead); }
Java代码：
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); } }