非递归、固定量额外存储空间 遍历二叉树
题
写出一个O(n)时间的非递归过程，输出给定的含n个节点的二叉树中每个结点的关键字，要求只能使用除树本身以外固定量的额外存储空间，而且在过程中不能修改该树，哪怕只是暂时的。
树的遍历方式分类
从树的深度分类
树的遍历可以分为广度优先和深度优先两种形式。
- 广度优先，就是先输出父结点，再输出子结点。一般借助于（FIFO）队列。
- 深度优先，就是先输出子结点，再输出父结点。一般需要借助（LIFO）栈结构，如果不使用栈数据结构，一般就需要借用运行时的方法调用栈。
从树的节点的先后顺序分类
树的遍历可以分为先根遍历、中序遍历、后序遍历。前中后是以父节点在遍历中的顺序为根据的。
- 先根遍历：先遍历根，再遍历左子树，最后遍历右子树。
- 中序遍历：先遍历左子树，再遍历根，最后遍历右子树。
- 后序遍历：先遍历左子树，再遍历右子树，最后遍历根。
分析
由于只能使用固定量的额外存储空间，所以，没法构建队列或栈来进行遍历 或 用变量标记哪些结点是已输出的。由于不能修改树，也没法在树上做标记。所以，结点是否已输出只能在遍历过程中判断，也就需要遍历的算法能够区分出已输出和未输出的。
如果采用广度优先的方式，先输出父结点后，由于没有足够的空间来存储对子树的引用，树可以说是变为两棵独立的树，这个方式应该是不可行的。
如果采用深度优先的方式，以中序遍历为例，总是按左子树、父结点、右子树的顺序遍历，那么当右子树遍历完后，说明父结点及其所有子树都遍历完成了，可以这样往上处理父结点的父结点。而判断右子树是否遍历完成可以通过：当前遍历完成的结点是否是父结点的右结点来完成。这种方法是可行的。
当结点p及其子树都遍历完成后，需要向上查找第一个未遍历的右子树（parent = p.parent）：
p == parent.rChild，当前遍历是子树是右子树，需要继续往上查找；- 否则，p是parent的左孩子，先输出parent；如果parent有右孩子，需要进行遍历；如果parent没有右孩子，需要继续往上查找。