12二叉树的存储结构和遍历.ppt

课堂练习 写出三种遍历的结果 A B E C D A B C D E F G H K 先序序列： 中序序列： 后序序列： A B C D E F G H K B D C A E H G K F D C B H K G F E A 三种遍历的比较 1、如果不考虑visit，三种遍历的算法在结构上是一样的，因此，压栈和出栈的过程相同。 三种遍历的比较 2、三种遍历的执行过程是不一样的（visit的位置不一样）。 3、由前序序列和中序序列，或者后序和中序序列可以唯一确定一颗二叉树 A B C D E F G H K 先序序列： 中序序列： 后序序列： A B C D E F G H K B D C A E H G K F D C B H K G F E A 三种遍历的比较 3、复制二叉树 4、建立二叉树 2、查询二叉树中某个结点 应用举例 1、统计二叉树中结点的个数 遍历访问了每个结点一次且仅一次 设置一个全局变量count=0 统计二叉树中结点的个数 将visit改为:count++ 统计二叉树中结点的个数 void PreOrder (BiTree T){ } if (! T ) return; count++; Preorder( T-lchild); Preorder( T-rchild); void Preorder (BiTree T,void( *visit)(TElemType e)) { // 先序遍历二叉树 1 if (!T) return; 2 visit(T-data); // 访问结点 3 Preorder(T-lchild, visit); // 遍历左子树 4 Preorder(T-rchild, visit);// 遍历右子树 } 统计二叉树中结点的个数 int count=0; main() PreOrder(T); printf(”%d”,count); } { 递归思想: 如果是空树，返回0 统计二叉树中结点的个数 求出左子树的结点的个数m 求出右子树的结点的个数n 返回m+n+1 统计二叉树中结点的个数 int CountNode (BiTree T){ //返回指针T所指二叉树中所有叶子结点个数 } if (!T ) return 0;//空树 m = CountNode( T-lchild); n = CountNode( T-rchild); return (m+n+1); 求二叉树的深度 课堂练习： 空树的深度为0， 求二叉树的深度 int Depth (BiTree T ){// 返回二叉树的深度 } if ( !T ) return (0); depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft :depthRight); return depthval; 查询二叉树中的某个结点 给定指向二叉树的根结点的指针T和x，在T中查找数据元素的值等于x的结点，如果找到，则返回一个指针，指向这个结点，否则，返回空指针。 A B E C D T X= C 查询二叉树中的某个结点 1. 在二叉树不空的前提下,和根结点的元素进行比较,若相等,则找到返回指向根结点的指针 2. 否则在左子树中进行查找,若找到,则返回指针 3. 否则继续在右子树中进行查找,若找到,则返回指针,否则返回空指针 * 二叉树的存储结构和遍历 二叉树的遍历 二叉树的存储结构 小结和作业 顺序存储 二叉链表 三叉链表 链式存储 问题的提出 递归遍历算法 遍历的应用实例 二叉树的顺序存储 顺序存储是用一组连续的存储单元存放数据 顺序存储要求数据是线性结构 二叉树是非线性结构 如何把二叉树转换为线性结构，而且保持结点之间的父/子关系? 二叉树的顺序存储 A C G B D E F K L H J I M N O 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 满二叉树：从上到下，从左往右依次编号 二叉树的顺序存储 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 数组的下标，也是结点的编号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C E F D G H I