二叉树
前言
二叉树的遍历主要有深度优先遍历和广度优先遍历，深度优先遍历是优先访问一个子树上的所有节点，访问的属性是竖向的，而广度优先遍历则是优先访问同一层的所有节点，访问属性是横向的。
深度优先遍历
深度优先遍历主要有三种顺序：
- 前序遍历 —— 根左右
- 中序遍历 —— 左根右
- 后序遍历 —— 左右根
这三种遍历顺序用递归可以很容易实现，主要讲的是非递归的实现方法。而要使用迭代的方法来遍历二叉树，需要用到栈的特性。
前序遍历（非递归C++）
算法：
- 根节点入栈
- 访问栈顶元素并将其出栈
- 将左右子树入栈，由于访问顺序是"根左右"，且使用的是栈，因此右子树先于左子树入栈
- 重复步骤2、3，直到栈为空
[code]void preOrder(BTNode* root) { stack S; BTNode* cur = NULL; if(root == NULL) return; S.push(root); //根节点入栈 while(!S.empty()) { //访问顺序"根左右" cur = S.top(); coutleft; } //访问最左孩子 cur = S.top(); cout |
