数据结构课件树概论.ppt

  1. 1、本文档共68页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
5.在中序线索二叉树上查找任意结点的中序后继结点 有以下两种情况: ⑴如果该结点的右标志为1,那么其右指针域所指向的结点便是它的后继结点; ⑵如果该结点的右标志为0,它的后继结点是以该结点的右孩子为根结点的子树的最左结点。 6.3.5 线索二叉树 6.线索二叉树应用 二叉树经常遍历或查找结点在遍历所得线性序列中的前驱和后继,应用线索二叉链表作存储结构较合适。 二叉树的线索二叉链表表示(P133) 为了计算方便可添加头结点(P133 图6.11) 6.3.5 线索二叉树 小 结 掌握二叉树的四种遍历方式 指定二叉树的遍历结点序列 恢复二叉树 掌握二叉树遍历的实现算法 递归、非递归实现算法 层次遍历实现算法 理解如何对二叉树线索化 练习题 编写二叉树创建递归算法 编写二叉树中序遍历的非递归算法 编写二叉树后序遍历的非递归算法 利用二叉树的遍历算法实现求二叉树中结点总数和在二叉树中查找某一个结点x的算法。 6.3.1 二叉树的遍历方式 二叉树的遍历方式有四种: 先序、中序、后序和层次遍历 先序遍历(DLR)定义: 若二叉树为空,遍历结束。否则, ⑴访问根结点; ⑵先序遍历根结点的左子树; ⑶先序遍历根结点的右子树。 6.3.1 二叉树的遍历方式 二叉树的遍历方式有四种: 先序、中序、后序和层次遍历 中序遍历(LDR)定义: 若二叉树为空,遍历结束。否则, ⑴中序遍历根结点的左子树; ⑵访问根结点; ⑶中序遍历根结点的右子树。 6.3.1 二叉树的遍历方式 二叉树的遍历方式有四种: 先序、中序、后序和层次遍历 后序遍历(LRD)定义: 若二叉树为空,遍历结束。否则, ⑴后序遍历根结点的左子树; ⑵后序遍历根结点的右子树。 ⑶访问根结点; 6.3.1 二叉树的遍历方式 二叉树的遍历方式有四种: 先序、中序、后序和层次遍历 层次遍历定义: 若二叉树为空,遍历结束。否则,从二叉树的第一层(根结点)开始,从上至下逐层遍历,同一层,则按从左到右的顺序逐个访问结点。 6.3.1 二叉树的遍历方式 练习1: 给出下面指定二叉树的四种遍历方式下的结点序列。 6.3.1 二叉树的遍历方式 练习2: 根据给定的遍历结点序列恢复二叉树。 LDR:DCBGEAHFIJK DLR:ABCDEGFHJIK 哪些遍历组合可以唯一确定一棵二叉树? 6.3.1 二叉树的遍历方式 结论 DLR,LDR可以确定一棵二叉树; LDR,LRD可以确定一棵二叉树; LDR,层次遍历可以确定一棵二叉树 6.3.1 二叉树的遍历方式 练习3: 根据给定的遍历结点序列恢复二叉树。 LDR: B C A E D G H F I LRD: C B E H G I F D A 6.3 二叉树的遍历 6.3.1 二叉树的遍历方式 6.3.2 二叉树遍历的递归算法 6.3.3 二叉树遍历的非递归算法 6.3.4 二叉树的层次遍历算法 6.3.5 线索二叉树 6.3.2 二叉树遍历的递归算法 先序遍历递归算法: void PreOrder(BiTree bt) { if (bt==NULL) return; Visite(bt-data); PreOrder(bt-lchild); PreOrder(bt-rchild); } 6.3.2 二叉树遍历的递归算法 中序遍历递归算法: void InOrder(BiTree bt) { if (bt==NULL) return; InOrder(bt-lchild); Visite(bt-data); InOrder(bt-rchild); } 6.3.2 二叉树遍历的递归算法 后序遍历递归算法: void PostOrder(BiTree bt) { if (bt==NULL) return; PostOrder(bt-lchild); PostOrder(bt-rchild); Visite(bt-data); } 6.3.2 二叉树遍历的递归算法 根据二叉树的递归定义,很容易写出二叉树先序、中序和后序遍历的递归算法。但并非所有程序设计语言都允许递归;另一方面,递归程序虽然简洁,但可读性不好,执行效率也不

文档评论(0)

kehan123 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档