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