| 二叉树的遍历是操作的重点，通常采用的递归算法不难实现和理解。但要实现二叉树遍历的非递归则有一定的难度，因而是理解二叉树遍历的难点。
|
|
|
| 由于很多程序员考题中都隐含地利用二叉树遍历的非递归算法，如求二叉树中某个节点的祖先等，因而必须牢固地掌握二叉树的三种遍历的非递归算法。本质上，程序员考题中不是要考生遍历二叉树中的所有节点，而是遍历满足某种条件的节点并输出，在成功找到答案之前需要保留访问过的部分节点信息，因而须借助栈和队列等重要的数据结构。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 例如，在以二叉链表为存储结构的二叉树中，打印数据域值为x的节点（假定节点值不相同），并打印x的所有祖先的数据域值。
|
|
|
| 解决此问题的算法思想是：若在查找某节点的过程中，记下其祖先节点，则可实现本问题要求。能实现这种要求的数据结构是栈，故设置一个栈用于装入x节点的所有祖先，而这种查找只有用非递归的后序遍历。
|
|
|
|
|
|
|
