敦案 第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 6.5先后中序遍历的应用扩展 利用二叉树的遍历算法，适当修改访问结点操作的内容，可以得到求解许多问题的算法。 ◇二叉树的创建（基于先序遍历） 令二叉树的线索化 查找指定结点：在访问结点时，判断当前访问的结点是否是指定的结点，若是则返回 该结点位置，否则继续遍历： 查找位于某种遍历次序中的第k位的结点：遍历前，引入一计数器，用来统计已访问 过的结点数，初值为0在访问结点时，将该计数器增1，并看是否达到k,: 令求叶子结点的数目：遍历前，引入叶子结点计数器，初值为0：访问结点时，将该计 数器增1：遍历结束，则计数器中的值即为所求解： 令判断二叉树中是否仅包含有度为2和0的结点：访问结点时，判断该结点孩子的有无 情况，… 求指定结点的层次：孩子结点的层次比其双亲结点层次多一： ◇求二叉树的高度：二叉树的高度=max(左子树的高度，右子树的高度)+1 6.5.1基于先序遍历的二叉树（二叉链）的创建 【本例特征】 如何基于二叉树的先序、中序、后序遍历的递归算法进行问题求解？ 【思路】 先序遍历PreOrderTraverse 创建CreateBiTree 输入 二叉链表示的二叉树的头指针T 带虚结点的先序序列ch 输入的表现方式 参数 由输入设备输入scanf(&ch) 输出 对结点的访问结果 二叉链表示的二叉树的头指针T 输出的表现方式 由输出设备输出 变参 空树（递归结束）的 T==NULL ch一END DATA(表示虚结点的值) 条件及处理 (直接求解) 空 T=NULL 根结点的访问 T=(BiTree)malloc(sizeof(BiTNode ) (子问题直接求解) Visit(T->data T->data=ch 左子树 (使用递归调用的解) PreOrderTraverse(T->lchild CreateBiTree(T->Ichild 右子树 PreOrderTraverse(T->rchild) CreateBiTree(T->rchild (使用递归调用的解) 【算法】见《数据结构(C语言版)》P131算法6.4。 6.5.2统计二叉树中叶子结点的数目 【本例特征】 如何通过全局变量、变参、返回值三种渠道返回处理结果？ 【思路】 在遍历二叉树时，对一些特殊的结点（无左右孩子）进行计数。可以修改遍历算法的结点访 问操作为对特殊结点的判定和计数过程，需要注意的是计数器的处理方式。可以有以下几种计 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第8页程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 8 页 第六章 树和二叉树 基本概念、遍历算法及其应用 6.5 先|后|中序遍历的应用扩展 利用二叉树的遍历算法，适当修改访问结点操作的内容，可以得到求解许多问题的算法。  二叉树的创建（基于先序遍历）  二叉树的线索化  查找指定结点：在访问结点时，判断当前访问的结点是否是指定的结点，若是则返回 该结点位置，否则继续遍历；  查找位于某种遍历次序中的第 k 位的结点：遍历前，引入一计数器，用来统计已访问 过的结点数，初值为 0；在访问结点时，将该计数器增 1，并看是否达到 k，……；  求叶子结点的数目：遍历前，引入叶子结点计数器，初值为 0；访问结点时，将该计 数器增 1；遍历结束，则计数器中的值即为所求解；  判断二叉树中是否仅包含有度为 2 和 0 的结点：访问结点时，判断该结点孩子的有无 情况，……  求指定结点的层次：孩子结点的层次比其双亲结点层次多一；  求二叉树的高度：二叉树的高度 = max(左子树的高度, 右子树的高度) +1 6.5.1 基于先序遍历的二叉树(二叉链)的创建 【本例特征】 如何基于二叉树的先序、中序、后序遍历的递归算法进行问题求解？ 【思路】 先 序 遍 历 PreOrderTraverse 创 建 CreateBiTree 输入 二叉链表示的二叉树的头指针 T 带虚结点的先序序列 ch 输入的表现方式 参数 由输入设备输入 scanf( &ch ) 输出 对结点的访问结果 二叉链表示的二叉树的头指针 T 输出的表现方式 由输出设备输出 变参 空树（递归结束）的 条件及处理 (直接求解) T == NULL ch == END_DATA（表示虚结点的值） 空 T = NULL 根结点的访问 (子问题直接求解) Visit( T->data ) T = ( BiTree)malloc( sizeof( BiTNode )) T->data = ch 左子树 (使用递归调用的解) PreOrderTraverse( T->lchild ) CreateBiTree( T->lchild ) 右子树 (使用递归调用的解) PreOrderTraverse( T->rchild ) CreateBiTree( T->rchild ) 【算法】见《数据结构(C 语言版)》P131 算法 6.4。 6.5.2 统计二叉树中叶子结点的数目 【本例特征】 如何通过全局变量、变参、返回值三种渠道返回处理结果？ 【思路】 在遍历二叉树时，对一些特殊的结点(无左右孩子)进行计数。可以修改遍历算法的结点访 问操作为对特殊结点的判定和计数过程，需要注意的是计数器的处理方式。可以有以下几种计