從上到下列印二叉樹

從上到下列印二叉樹

從上到下列印出二叉樹的每個節點，同一層的節點按照順序從左到右的順序列印。

思路：每次列印節點的時候，如果該節點有子節點，則把該節點的子節點放到一個隊列的隊尾。接下來到隊列的頭部取出最早進入隊列的節點，重複前面操作。

參考代碼：

root@gt:/home/git/Code# ./a.out 8 6 10 5 7 9 11 root@gt:/home/git/Code# cat printTopBottom.cpp #include <iostream>#include <vector>#include <queue>#include <stdlib.h>using namespace std;typedef struct BTreeNode{ int value; struct BTreeNode* pleft; struct BTreeNode* pright;}TreeNode;vector<int> printTopBottom(TreeNode* root){ vector<int> res; if(root == NULL) return res; queue<TreeNode*> q; q.push(root); while(!q.empty()) { res.push_back(q.front()->value); if(q.front()->pleft != NULL) q.push(q.front()->pleft); if(q.front()->pright != NULL) q.push(q.front()->pright); q.pop(); } return res;}TreeNode* concore(int* preStart,int* preEnd,int* inStart,int* inEnd){//前序遍歷的地一個元素就是根節點 int rootValue = preStart[0]; TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); root->value = rootValue; root->pleft = root->pright = NULL;//在中序遍歷序號中找到根節點的值 int* rootIn = inStart; while(rootIn <= inEnd && *rootIn != rootValue) ++rootIn; int leftLen = rootIn - inStart; int* leftPreEnd = preStart + leftLen; if(leftLen>0) { root->pleft = concore(preStart+1,leftPreEnd,inStart,inStart+leftLen-1); } if(leftLen < preEnd - preStart) { root->pright = concore(leftPreEnd+1,preEnd,rootIn+1,inEnd); } return root;}TreeNode* construct(int* pre,int* in,int len){ if(pre==NULL || in==NULL || len<=0) return 0; return concore(pre,pre+len-1,in,in+len-1);}void preOrder(TreeNode* root){ if(root ==NULL) return; printf("%d ",root->value); preOrder(root->pleft); preOrder(root->pright);}int main(){ int pre[] = {8,6,5,7,10,9,11}; int in[] = {5,6,7,8,9,10,11}; TreeNode* root = construct(pre,in,sizeof(pre)/sizeof(int)); vector<int> res = printTopBottom(root); for(int i = 0;i < sizeof(pre)/sizeof(int);i++) { cout << res[i] << ; } cout<<endl; return 0;}

推薦閱讀：