二叉树的遍历.ppt

《二叉树的遍历.ppt》由会员分享，可在线阅读，更多相关《二叉树的遍历.ppt（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息技术基础u满二叉树和完全二叉树满二叉树和完全二叉树u二叉树的存储结构二叉树的存储结构1、请同学们仔细看下面三棵树，辨别出满二叉树和完全二叉树：、请同学们仔细看下面三棵树，辨别出满二叉树和完全二叉树：2、二叉树通常采用、二叉树通常采用 存储结构。存储结构。满二叉树满二叉树完全二叉树完全二叉树链式链式 满二叉树和完全二叉树满二叉树和完全二叉树满二叉树：满二叉树：每一层上的结点数都达到每一层上的结点数都达到最大值。最大值。完全二叉树：完全二叉树：除最后一层外，每一层上的结点数均达到除最后一层外，每一层上的结点数均达到最最大值大值；在最后一层上只；在最后一层上只缺少右边缺少右边的若干结点。的若干结

2、点。二叉树的存储结构：采用二叉树的存储结构：采用链式链式存储结构。存储结构。存储结点由两部分组成：存储结点由两部分组成：数据域数据域与与指针域指针域。存储结点的指针域有两个：存储结点的指针域有两个：左指针左指针和和右指针右指针左指针左指针数据域数据域右指针右指针二叉树存储结点的结构二叉树存储结点的结构怎么访问怎么访问数据呢？数据呢？存存储储数据数据u二叉树的遍历二叉树的遍历u重点难点：掌握和分清重点难点：掌握和分清二叉树遍历二叉树遍历的三种方法的三种方法二叉树的遍历：二叉树的遍历：是指是指不重复不重复地访问二叉树中的地访问二叉树中的所有所有结点。结点。前序遍历（前序遍历（DLRDLR）中序遍历

3、中序遍历(LDR)(LDR)后序遍历后序遍历(LRD)(LRD)三种遍历方法：三种遍历方法：概念概念概念概念前序遍历（前序遍历（DLRDLR）规则：规则：（1 1）访问访问根根结点；结点；（2 2）前序遍历前序遍历左左子树；子树；（3 3）前序遍历前序遍历右右子树；子树；遍历顺序遍历顺序：FCADBEGHP中序遍历（中序遍历（LDRLDR）规则：规则：（1 1）中序遍历）中序遍历左左子树；子树；（2 2）访问）访问根根结点；结点；（3 3）中序遍历）中序遍历右右子树。子树。遍历顺序遍历顺序：ACBDFEHGP后序遍历后序遍历(LRD)(LRD)规则：规则：（1 1）后序遍历）后序遍历左左子树；

4、子树；（2 2）后序遍历）后序遍历右右子树；子树；（3 3）访问）访问根根结点。结点。遍历顺序遍历顺序：ABDCHPGEF设有下列二叉树设有下列二叉树求此二叉树的前序遍历、中序遍历和后序遍历的顺序分别是？求此二叉树的前序遍历、中序遍历和后序遍历的顺序分别是？前序遍历：ABDECF中序遍历：DBEAFC后序遍历：DEBFCA后序后序遍历遍历中序遍历中序遍历前序遍历前序遍历ABDECFDBEAFCDEBFCA二叉树三种遍历记忆方法：二叉树三种遍历记忆方法：前前序遍历：序遍历：先找先找根根，再，再左右左右中中序遍历：序遍历：先先左左边，边，根根中间，中间，右右在后在后后后序遍历：序遍历：先先左右左右，再找，再找根根1.1.完成课后练习完成课后练习1 1、2 2、3 3题。题。2.2.复习下节课的内容。复习下节课的内容。