题目:对于一个给定的二叉树,分层遍历二叉树,分为上下左右,不同方向进行遍历。
解析:原来实现时考虑使用队列来做,但这个算法不方便使用递归来做,如果使用递归会造成诸多问题。因此可以使用循环来处理,编程之美中不使用队列而是用数组模拟队列,对于从下上输出很有帮助,具体描述如下:
1)对于从右向左输出,开始考虑使用栈来颠倒,实际发现其实只要处理左右子树的顺序改变一下就可以了;
2)对于从下向上遍历,开始考虑使用栈来存储再输出,但这样付出额外的空间,因为采用了数组保存了特定输出顺序的所有节点,只要从后向前输出数组,就可以实现从下向上的遍历了。
心得:使用数组来保存待输出的节点顺序,可以方便按照需求进行合理的输出,其实就是改变遍历数组的顺序就可以了。
具体的程序代码如下:
#include <stdio.h> #include <vector> class TreeNode { public: TreeNode() : left_(NULL), right_(NULL) {} int value_; TreeNode* left_; TreeNode* right_; }; void TopDownLeftRightVisit(TreeNode* root) { std::vector<TreeNode*> visit_order; int offset = 0; TreeNode* current = root; if (current) { visit_order.push_back(current); } while (offset < visit_order.size()) { printf("%d ", visit_order[offset]->value_); current = visit_order[offset]; if (current->left_) { visit_order.push_back(current->left_); } if (current->right_) { visit_order.push_back(current->right_); } offset++; } } void TopDownRightLeftVisit(TreeNode* root) { std::vector<TreeNode*> visit_order; int offset = 0; TreeNode* current = root; if (current) { visit_order.push_back(current); } while (offset < visit_order.size()) { printf("%d ", visit_order[offset]->value_); current = visit_order[offset]; if (current->right_) { visit_order.push_back(current->right_); } if (current->left_) { visit_order.push_back(current->left_); } offset++; } } void BottomUpLeftRightVisit(TreeNode* root) { std::vector<TreeNode*> visit_order; int offset = 0; TreeNode* current = root; if (current) { visit_order.push_back(current); } while (offset < visit_order.size()) { current = visit_order[offset]; if (current->right_) { visit_order.push_back(current->right_); } if (current->left_) { visit_order.push_back(current->left_); } offset++; } for (int i = visit_order.size() - 1; i >=0; --i) { printf("%d ", visit_order[i]->value_); } } void BottomUpRightLeftVisit(TreeNode* root) { std::vector<TreeNode*> visit_order; int offset = 0; TreeNode* current = root; if (current) { visit_order.push_back(current); } while (offset < visit_order.size()) { current = visit_order[offset]; if (current->left_) { visit_order.push_back(current->left_); } if (current->right_) { visit_order.push_back(current->right_); } offset++; } for (int i = visit_order.size() - 1; i >=0; --i) { printf("%d ", visit_order[i]->value_); } } void SetLink(TreeNode* parent, TreeNode* left, TreeNode* right) { parent->left_ = left; parent->right_ = right; } int main(int argc, char** argv) { TreeNode* tree = new TreeNode[8]; for (int i = 0; i < 8; ++i) { tree[i].value_ = i + 1; } SetLink(&tree[0], &tree[1], &tree[2]); SetLink(&tree[1], &tree[3], &tree[4]); SetLink(&tree[2], NULL, &tree[5]); SetLink(&tree[4], &tree[6], &tree[7]); TopDownLeftRightVisit(tree); printf("\n"); TopDownRightLeftVisit(tree); printf("\n"); BottomUpLeftRightVisit(tree); printf("\n"); BottomUpRightLeftVisit(tree); printf("\n"); }
为了程序设计的简单,没有使用模板,而使用int来表示测试数据。
参考文献:
编程之美3.10