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