#include <bits/stdc++.h> using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; }; void create(TreeNode* &root) { int x; cin>>x; if(x == 0) { root = NULL; return; } root = (TreeNode*)malloc(sizeof(TreeNode)); root->val = x; create(root->left); create(root->right); } // 之字形打印 vector<int> PrintZhiTree(TreeNode* root) { stack<TreeNode*>S1; stack<TreeNode*>S2; vector<int>V; if(!root) return V; S1.push(root); while(!S1.empty()||!S2.empty()) { while(!S1.empty()) { TreeNode* p = S1.top(); S1.pop(); if(!p) continue; S2.push(p->left); S2.push(p->right); V.push_back(p->val); } V.push_back(0); while(!S2.empty()) { TreeNode* p = S2.top(); S2.pop(); if(!p) continue; S1.push(p->right); S1.push(p->left); V.push_back(p->val); } V.push_back(0); } return V; } vector<int> PrintFromTopToBottom(TreeNode* root) { queue<TreeNode*>Q; vector<int>V; if(!root) return V; Q.push(root); while(!Q.empty()) { TreeNode* p = Q.front(); Q.pop(); if(!p) continue; Q.push(p->left); Q.push(p->right); V.push_back(p->val); } return V; } int main() { TreeNode* root; create(root); vector<int>V; //V = PrintFromTopToBottom(root); V = PrintZhiTree(root); for(int i=0; i<V.size(); i++) { if(V[i] == 0) puts(""); else printf("%d ", V[i]); } return 0; }
测试:
1 2 4 8 16 0 0 17 0 0 9 18 0 0 19 0 0 5 10 20 0 0 21 0 0 11 22 0 0 23 0 0 3 4 12 24 0 0 25 0 0 13 26 0 0 27 0 0 7 14 28 0 0 29 0 0 15 30 0 0 31 0 0