chap6-2树与二叉树的遍历教程.ppt

数据结构（C） ;第6章 主要内容;回顾;*;回顾;*; 二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。;6.3 二叉树遍历和线索二叉树;*;*;*;*;*;*;*;;二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。 ;二、二叉树遍历的非递归算法;A;1. 利用栈的中序遍历非递归算法;*;*;*;*;*;*;*;*;*;*;二叉树前序遍历的非递归算法的关键：在前序遍历过某结点的整个左子树后，如何找到该结点的右子树的根指针。 解决办法：利用栈存放该结点的右子女结点。 ;*;*;*;*;*;二叉树遍历算法的应用举例;（1）求二叉树的高度;（1）求二叉树的高度;（2）求二叉树的叶子结点个数;（2）求二叉树的叶子结点个数;若已知一棵二叉树的前序（或中序，或后序，或层序）序列，能??唯一确定这棵二叉树呢？;例：已知前序遍历序列为ABC，后序遍历序列为CBA，则下列二叉树都满足条件。;若已知一棵二叉树的先序序列和中序序列，能否唯一确定这棵二叉树呢？怎样确定？ ;先序：A B C D E F G H I中序：B C A E D G H F I;先序：F G H I 中序：G H F I;1. 根据先序序列的第一个元素建立根结点； 2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列； 3. 在先序序列中确定左右子树的先序序列； 4. 由左子树的先序序列和中序序列建立左子树； 5. 由右子树的先序序列和中序序列建立右子树。 ;课堂练习;小结;随堂练习