数据结构.第6章.树与二叉树.2.遍历二叉树与线索二叉树.pptx

数据结构 Data Structures;;提出问题 ;遍历是任何类型均有的操作 ;遍历二叉树 ;遍历二叉树 ;先左后右的遍历算法 ;先（根）序遍历算法 ;中（根）序遍历算法 ;后（根）序遍历算法 ;例1 ;例2：用二叉树表示算术表达式 ;例3 ;遍历算法的递归实现 ;先序遍历二叉树的递归算法 ;A;中序遍历二叉树的递归算法 ;后序遍历二叉树的递归算法 ;遍历的分析 ;中序遍历二叉树的非递归算法一 ;中序遍历二叉树的非递归算法二 ;遍历算法的应用举例 ;例1：统计二叉树中叶子结点的个数 ;例2：求二叉树的深度 ;例3：按先序序列建立二叉树的二叉链表;例3：按先序序列建立二叉树的二叉链表;线索二叉树;线索二叉树;线索二叉树;线索二叉树;线索二叉树;线索二叉树;线索二叉树;线索二叉树;规定：;二叉树二叉线索存储表示;有关线索二叉树的几个术语;;例2：【 2000年计算机系考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 ;A;线索二叉树的生成;A;;如何在线索树中找结点的后继;如何在线索树中找结点的前驱;线索链表的中序遍历算法 Status IOTraver_T( BiThrTree T,Status (*Visit)(TElemType e) ) { //T指向头结点，头结点的左链lchild指向根结点，中序遍历 //二叉线索树T的非递归算法，对每个数据元素调用函数Visit。 p = T-lchild; //p指向根结点 while (p != T) { //空树或遍历结束时，p = = T while (p-LTag==Link) p = p-lchild; if (!Visit(p-data)) return ERROR; //访问其左子树为空的结点 while (p-RTag==Thread p-rchild!=T) { p = p-rchild; Visit(p-data); } //访问后继结点 p = p-rchild; } return OK; } // IOTraver_T;线索二叉树的生成算法（算法6.6, 见教材P134）;;线索二叉树;;线索二叉树;Thank You !