树和二叉树数据结构ppt课件.pptx

《树和二叉树数据结构ppt课件.pptx》由会员分享，可在线阅读，更多相关《树和二叉树数据结构ppt课件.pptx（86页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树集合数据元素间除“同属于一个集合”外，无其它关系图形结构多个对多个，如图逻辑结构逻辑结构为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能第第6 6章树章树

2、和二叉树和二叉树6.1 树的定义和基本术语树的定义和基本术语6.2 二叉树二叉树6.3 遍历二叉树与线索二叉树遍历二叉树与线索二叉树6.4 树和森林树和森林6.5 霍夫曼树及其应用霍夫曼树及其应用为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.1.掌握二叉树的基本概念、掌握二叉树的基本概念、性质性质和存储结构和存储结构2.2.熟练掌握二叉树的熟练掌握二叉树的前、中、后序遍历方法前、中、后序遍历方法3.3.了解了解线索化线索化

3、二叉树的思想二叉树的思想4.4.熟练掌握：熟练掌握：霍夫曼树霍夫曼树的实现方法、构造的实现方法、构造霍夫曼编霍夫曼编码码的方法的方法5.5.了解：森林与二叉树的转换，树的遍历方法了解：森林与二叉树的转换，树的遍历方法教学目标教学目标为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能6.1 6.1 树的定义和基本术语树的定义和基本术语树是树是n n个结点的有限集个结点的有限集T1T2T3为深入学习习近平新时代中国特色社会主义思想和党

4、的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能ADT Tree数据对象数据对象D:数据关系数据关系R:基本操作基本操作 P：ADT Tree若若D为空集，则称为空树；为空集，则称为空树；/允许允许n=0若若D中仅含一个数据元素，则中仅含一个数据元素，则R为空集；为空集；其他情况下的其他情况下的R存在二元关系：存在二元关系：root 唯一唯一 /关于根的说明关于根的说明 DjDk=/关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说明关于数据元素的说明D是具有相同

5、特性的数据元素的集合。是具有相同特性的数据元素的集合。/至少有至少有15个个树的抽象数据类型定义树的抽象数据类型定义为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能凹入表示凹入表示嵌套集合嵌套集合广义表广义表树的其它表示方式树的其它表示方式为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分

6、发挥中小学图书室育人功能 根根 叶子叶子 森林森林有序树有序树无序树无序树即根结点即根结点(没有前驱没有前驱)即终端结点即终端结点(没有后继没有后继)指指m棵不相交的树的集合棵不相交的树的集合(例如删除例如删除A后的子树个数后的子树个数)结点各子树从左至右有序，不能互换（左为第一）结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。结点各子树可互换位置。基本术语基本术语为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功

7、能即上层的那个结点即上层的那个结点(直接前驱直接前驱)即下层结点的子树的根即下层结点的子树的根(直接后继直接后继)同一双亲下的同层结点（孩子之间互称兄弟）同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点即该结点下层子树中的任一结点双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙基本术语基本术语为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神

8、贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点树的度树的度树的深度树的深度(或高度或高度)从根到该结点的层数（根结点算第一层）从根到该结点的层数（根结点算第一层）即度为即度为0的结点，即叶子的结点，即叶子即度不为即度不为0的结点（也称为内部结点）的结点（也称为内部结点）所有结点度中的最大值所有结点度中的最大值指所有结点中最大的层数指所有结点中最大的层数层次1234基本术语基本术语为深入学习习近平新时代中国特色社会主义思想和党的十

9、九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能MINEBDAGJKCFLH为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充

10、分发挥中小学图书室育人功能 1)哪是根节点 2）哪是叶子节点 3）哪个节点是G的双亲 4）哪些是G的祖先 5）哪些节点是G的孩子 6）哪些节点是E的子孙 7）哪些节点是E的兄弟 8）节点B和N的层次号是 分别是多少 9）树的深度是多少 10）以节点C为根的子树 的深度是多少 11）树的度数是多少MINEBDAGJKCFLH为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能6.2 6.2 二叉树二叉树普通树（多叉树）若不转化为二叉树

11、，则运算很难实现普通树（多叉树）若不转化为二叉树，则运算很难实现为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个 “叉叉”的树？的树？二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不可以证明，所有树都能转为唯一对应的二叉树，不失一般性。失一般性。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能二叉树二叉树基本基本特点：特点：结点的度小于等于结点的度小于等

12、于结点的度小于等于结点的度小于等于2 2 2 2有序树（子树有序，不能颠倒）有序树（子树有序，不能颠倒）有序树（子树有序，不能颠倒）有序树（子树有序，不能颠倒）二叉树的五种不同形态二叉树的五种不同形态为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能具有具有具有具有3 3 3 3个结点的二叉树可能有几种不同形态？普通树呢？个结点的二叉树可能有几种不同形态？普通树呢？个结点的二叉树可能有几种不同形态？普通树呢？个结点的二叉树可能有几

13、种不同形态？普通树呢？练习练习5 5种种/2/2种种为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能一棵度一棵度为2的的树与一棵二叉与一棵二叉树有何区有何区别？解：解：二叉树是颗有序树，但度为2的树则未必有序。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能ADT

14、 BinaryTree数据对象数据对象D:数据关系数据关系R:基本操作基本操作 P：ADT BinaryTree若若D=，则，则R=；若若D，则，则R=H；存在二元关系：；存在二元关系：root 唯一唯一 /关于根的说明关于根的说明 DjDk=/关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说明关于数据元素的说明 /关于左子树和右子树的说明关于左子树和右子树的说明D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。/至少有至少有20个个二叉树的抽象数据类型定义二叉树的抽象数据类型定义为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特

15、色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能性质性质1:1:在二叉树的第在二叉树的第i i层上至多有层上至多有2 2 2 2i-1i-1i-1i-1个结点个结点二叉树的性质二叉树的性质提问：第提问：第i i层上至少有层上至少有 个结点？个结点？性质性质2:2:深度为深度为k k的二叉树至多有的二叉树至多有2 2 2 2k k k k-1-1-1-1个结点个结点提问：深度为提问：深度为k k时至少有时至少有 个结点？个结点？1k为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国

16、特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能性质性质3:3:对于任何一棵二叉树，若对于任何一棵二叉树，若2 2度的结点数有度的结点数有n n2 2个，则叶子数个，则叶子数n n0 0必定为必定为n n2 21 1（即（即n n0 0=n=n2 2+1+1）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能满二叉树：满二叉树：一棵深度为一棵深度为

17、一棵深度为一棵深度为k k k k 且有且有且有且有2 2 2 2k k-1-1-1-1个结点的个结点的个结点的个结点的二叉树。二叉树。二叉树。二叉树。（特点：每层（特点：每层都都“充满充满”了结点）了结点）特殊形态的二叉树特殊形态的二叉树完全二叉树：完全二叉树：深度为深度为k k 的的，有有n n个结点的二叉树，当且个结点的二叉树，当且仅当其每一个结点都与深度仅当其每一个结点都与深度为为k k 的满二叉树中编号从的满二叉树中编号从1 1至至n n的结点的结点一一对应一一对应只有最后一层叶子不满，只有最后一层叶子不满，且全部集中在左边且全部集中在左边为深入学习习近平新时代中国特色社会主义思想和

18、党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能满满二二叉叉树树是是叶叶子子一一个个也也不不少少的的树树，而而完完全全二二叉叉树树虽虽然然前前n-1n-1层层是是满满的的，但但最最底底层层却却允允许许在在右右边边缺缺少少连连续续若若干个结点。干个结点。满二叉树是完全二叉树的一个特例。满二叉树是完全二叉树的一个特例。满二叉树和完全二叉树的区别满二叉树和完全二叉树的区别为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十

19、九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能一棵完全二叉树有一棵完全二叉树有50005000个结点，可以计算出其个结点，可以计算出其叶结点的个数是（叶结点的个数是（）。）。练习练习2500为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能性质性质4:4:具有具有n n个结点的完全二叉树的深度必为个结点的完全二叉树的深度必为loglog2 2n n1 1k层层nk-1层

20、层为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能性质性质5:5:对完全二叉树，若从上至下、从左至右编号，则对完全二叉树，若从上至下、从左至右编号，则编号为编号为i i 的结点，其左孩子编号必为的结点，其左孩子编号必为2i2i，其右孩子编号，其右孩子编号必为必为2i2i1 1；其双亲的编号必为；其双亲的编号必为i/2i/2。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的

21、十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能二叉树的顺序存储二叉树的顺序存储实现：按实现：按实现：按实现：按满二叉树满二叉树满二叉树满二叉树的结点层次编号，依次存放二叉的结点层次编号，依次存放二叉的结点层次编号，依次存放二叉的结点层次编号，依次存放二叉树中的数据元素。树中的数据元素。树中的数据元素。树中的数据元素。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能a

22、 b c d e 0 0 0 0 f g 0 1 2 3 4 5 6 7 8 9 10abcdefg特点：特点：特点：特点：结点间关系蕴含在其存储位置中结点间关系蕴含在其存储位置中结点间关系蕴含在其存储位置中结点间关系蕴含在其存储位置中浪费空间，适于存浪费空间，适于存浪费空间，适于存浪费空间，适于存满二叉树和完全二叉树满二叉树和完全二叉树满二叉树和完全二叉树满二叉树和完全二叉树 单支树单支树二叉树的顺序存储二叉树的顺序存储为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学

23、图书室育人功能充分发挥中小学图书室育人功能DATADATAPARENTPARENTLCHILDLCHILDRCHILDRCHILD二叉树的链式存储二叉树的链式存储为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能ABCDEFG AB C D E F G二叉链表二叉链表typedef struct BiNode TElemType data;struct BiNode *lchild,*rchild;/左右孩子指针左右孩子指针BiN

24、ode,*BiTree;为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能分分析析：必必有有2n2n个个链链域域。除除根根结结点点外外，每每个个结结点点有有且且仅仅有有一一个个双双亲亲，所所以以只只会会有有n n1 1个个结结点点的的链链域域存存放放指指针针，指指向向非非空空子子女结点。女结点。空指针数目空指针数目2n2n(n-1)=n+1(n-1)=n+1在在n n个结点的二叉链表中，个结点的二叉链表中，有有 个个空指针域空指针

25、域练习练习 AB C D E F Gn+1为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能三叉链表三叉链表ABCDEFG A B C D E F Glchild data parent rchildtypedef struct TriTNodetypedef struct TriTNode TelemType data;TelemType data;struct TriTNode struct TriTNode*lchild,*

26、parent,*rchild*lchild,*parent,*rchild;TriTNode,*TriTree;TriTNode,*TriTree;为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树遍历定义遍历定义指按某条搜索路线遍访每个结点且指按某条搜索路线遍访每个结点且不重复（又称周游）。不重复（又称周游）。遍历用途遍历用途它是树结构插入、删除、修改、查它是树结构插入

27、、删除、修改、查找和排序运算的前提，是二叉树一找和排序运算的前提，是二叉树一切运算的基础和核心。切运算的基础和核心。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能DLRDLRLDRLRDDRLRDLRLD遍历规则遍历规则先左后右先左后右为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发

28、挥中小学图书室育人功能先序遍历：先序遍历：中序遍历：中序遍历：后序遍历：后序遍历：A B CD EA B D E CA B D E CD B E A CD B E A CD E B C AD E B C A口诀：口诀：DLRDLR先序遍历，即先根再左再右先序遍历，即先根再左再右LDRLDR中序遍历，即先左再根再右中序遍历，即先左再根再右LRDLRD后序遍历，即先左再右再根后序遍历，即先左再右再根为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学

29、图书室育人功能+*A*/EDCB先序遍历先序遍历+*/A B C D E前缀表示前缀表示中序遍历中序遍历A/B*C*D+E中缀表示中缀表示后序遍历后序遍历A B/C*D*E+后缀表示后缀表示层序遍历层序遍历+*E*D/C A B用二叉树表示算术表达式用二叉树表示算术表达式为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能D L RAD L RD L RBDCD L RADBC先序遍历序列：先序遍历序列：先序遍历序列：先序遍历序列：

30、A B D CA B D C若二叉树为空，则空操作若二叉树为空，则空操作否则否则访问根结点访问根结点 (D)(D)前序遍历左子树前序遍历左子树 (L)(L)前序遍历右子树前序遍历右子树 (R)(R)遍历的算法实现先序遍历遍历的算法实现先序遍历为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能则三种遍历算法可写出则三种遍历算法可写出:遍历的算法实现遍历的算法实现用递归形式格外简单！用递归形式格外简单！用递归形式格外简单！用递归形式格

31、外简单！long Factorial(long n)if(n=0)return 1;/基本项基本项 else return n*Factorial(n-1);/归纳项归纳项回忆回忆:为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能Status PreOrderTraverse(BiTree T)if(T=NULL)return OK;/空二叉树空二叉树 else coutdata;/访问根结点访问根结点 PreOrderTrav

32、erse(T-lchild);/递归遍历左子树递归遍历左子树 PreOrderTraverse(T-rchild);/递归遍历右子树递归遍历右子树 先序遍历算法先序遍历算法为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能Status PreOrderTraverse(BiTree T)if(T=NULL)return OK;else coutdata;PreOrderTraverse(T-lchild);PreOrderTrav

33、erse(T-rchild);主程序主程序Pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：先序序列：ABDC为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育

34、人功能充分发挥中小学图书室育人功能遍历的算法实现中序遍历遍历的算法实现中序遍历若二叉树为空，则空操作若二叉树为空，则空操作若二叉树为空，则空操作若二叉树为空，则空操作否则否则否则否则:中序遍历左子树中序遍历左子树中序遍历左子树中序遍历左子树 (L)(L)(L)(L)访问根结点访问根结点访问根结点访问根结点 (D)(D)(D)(D)中序遍历右子树中序遍历右子树中序遍历右子树中序遍历右子树 (R)(R)(R)(R)ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：中序遍历序列：中序遍历序列：B D A CB D A CB D A CB D A C为深入学习习近平新

35、时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能Status InOrderTraverse(BiTree T)if(T=NULL)return OK;/空二叉树空二叉树 else InOrderTraverse(T-lchild);/递归遍历左子树递归遍历左子树 coutdata;/访问根结点访问根结点 InOrderTraverse(T-rchild);/递归遍历右子树递归遍历右子树 中序遍历算法中序遍历算法为深入学习习近平新时代中国特色社会

36、主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能遍历的算法实现后序遍历遍历的算法实现后序遍历若二叉树为空，则空操作若二叉树为空，则空操作否则否则后序遍历左子树后序遍历左子树 (L)(L)后序遍历右子树后序遍历右子树 (R)(R)访问根结点访问根结点 (D)(D)ADBC L R DL R DL R DADCL R DB后序遍历序列：后序遍历序列：后序遍历序列：后序遍历序列：D B C AD B C A为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深

37、入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能Status PostOrderTraverse(BiTree T)if(T=NULL)return OK;/空二叉树空二叉树 else PostOrderTraverse(T-lchild);/递归遍历左子树递归遍历左子树 PostOrderTraverse(T-rchild);/递归遍历右子树递归遍历右子树 coutdata;/访问根结点访问根结点 后序遍历算法后序遍历算法为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学

38、习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能Status PreOrderTraverse(BiTree T)if(T=NULL)return OK;else coutdata;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);Status PostOrderTraverse(BiTree T)if(T=NULL)return OK;else PostOrderTraverse(T-lchild);PostOrderTraverse

39、(T-rchild);coutdata;Status InOrderTraverse(BiTree T)if(T=NULL)return OK;else InOrderTraverse(T-lchild);coutdata;InOrderTraverse(T-rchild);遍历算法的分析遍历算法的分析为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能如果去掉输出语句，从递归的角度看，三种算法是完如果去掉输出语句，从递归的角度看，

40、三种算法是完全相同的，或说这三种算法的全相同的，或说这三种算法的访问路径是相同的，只访问路径是相同的，只是访问结点的时机不同是访问结点的时机不同。从虚线的出发点到终点的路径从虚线的出发点到终点的路径上，每个结点经过上，每个结点经过3次次。AFEDCBG第第1次次经过时访问经过时访问先序先序遍历遍历第第2次次经过时访问经过时访问中序中序遍历遍历第第3次次经过时访问经过时访问后序后序遍历遍历遍历算法的分析遍历算法的分析为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育

41、人功能充分发挥中小学图书室育人功能AFEDCBG时间效率时间效率:O(n)O(n)/每个结点只访问一次每个结点只访问一次空间效率空间效率:O(n):O(n)/栈占用的最大辅助空间栈占用的最大辅助空间遍历算法的分析遍历算法的分析为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能ABCDEFG A B C D E F G 按先序遍历序列建立二叉树的二叉链表按先序遍历序列建立二叉树的二叉链表例：已知先序序列为：例：已知先序序列为：A B

42、 C A B C D E D E G G F F （动态演示）（动态演示）二叉树的建立（算法二叉树的建立（算法6.36.3）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能计算二叉树结点总数计算二叉树结点总数计算计算二叉树二叉树叶子总数叶子总数计算二叉树高度计算二叉树高度二叉树遍历算法的应用二叉树遍历算法的应用为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯

43、彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能若二叉树中各结点的值均不相同，则：若二叉树中各结点的值均不相同，则：由二叉树的前序序列和中序序列，或由其后序序列和由二叉树的前序序列和中序序列，或由其后序序列和中序序列均中序序列均能唯一能唯一地确定一棵二叉树，地确定一棵二叉树，但由前序序列和后序序列却但由前序序列和后序序列却不一定能唯一不一定能唯一地确定一棵地确定一棵二叉树。二叉树。重要结论重要结论为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大

44、会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能练习练习已知一棵二叉树的已知一棵二叉树的中序序列中序序列和和后序序列后序序列分别是分别是BDCEAFHGBDCEAFHG 和和 DECBHGFADECBHGFA，请画出这棵二叉树。，请画出这棵二叉树。由后序遍历特征，根结点必在后序序列尾部由后序遍历特征，根结点必在后序序列尾部（A A）；由由中中序序遍遍历历特特征征，根根结结点点必必在在其其中中间间，而而且且其其左左部部必必全全部部是是左左子子树树子子孙孙（BDCEBDCE），其其右右部部必必全全部部是是右右子子树子孙树子孙（FHGFHG）；继继而而，根根据据后后序序中中的的DEC

45、BDECB子子树树可可确确定定B B为为A A的的左左孩孩子子，根据根据HGFHGF子串可确定子串可确定F F为为A A的右孩子；以此类推。的右孩子；以此类推。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能中序遍历：中序遍历：B D C E A F H GB D C E A F H G后序遍历：后序遍历：D E C B H G F D E C B H G F A A（B D C E）（F H G）ABF （D C E）（H G

46、）CD EGHABBFF为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能二叉链表空间效率这么低，能否二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息利用这些空闲区存放有用的信息或线索？或线索？可以用它来存放当前结点的可以用它来存放当前结点的直接前驱和后继直接前驱和后继等线索，以加快等线索，以加快查找速度。查找速度。思考思考线索化二叉树线索化二叉树在在n n个结点的二叉链表中，个结点的二叉链表中，有有n+1n+1个个空指针

47、域空指针域 AB C D E F G为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能普通二叉树只能找到结点的左右孩子信息，而该普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得结点的直接前驱和直接后继只能在遍历过程中获得若将遍历后对应的有关前驱和后继预存起来，则若将遍历后对应的有关前驱和后继预存起来，则从从第一个结点第一个结点开始就能很快开始就能很快“顺藤摸瓜顺藤摸瓜”而遍历整个而遍历整个树树

48、例如中序遍历结果：例如中序遍历结果：B D C E A F H GB D C E A F H G，实际上，实际上已已将二叉树转为线性排列，显然具有唯一前驱和唯将二叉树转为线性排列，显然具有唯一前驱和唯一后继！一后继！可能是根、或最左（右）叶子可能是根、或最左（右）叶子线索化二叉树线索化二叉树为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能两种解决方法两种解决方法增加两个域：增加两个域：fwdfwd和和bwdbwd；利用空链域（利

49、用空链域（n+1n+1个空链域）个空链域）如何保存这类信息？如何保存这类信息？线索化二叉树线索化二叉树为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1）若结点有左子树，则）若结点有左子树，则lchild指向其左孩子；指向其左孩子；否则，否则，lchild指向其直接前驱指向其直接前驱(即线索即线索)；2）若结点有右子树，则）若结点有右子树，则rchild指向其右孩子；指向其右孩子；否则，否则，rchild指向其直接后继指向其直接

50、后继(即线索即线索)。为了避免混淆，增加两个标志域为了避免混淆，增加两个标志域lchildLTagdataRTag rchild线索化二叉树线索化二叉树为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能LTag :LTag :若若 LTag=0,lchildLTag=0,lchild域指向左孩子；域指向左孩子；若若 LTag=1,lchildLTag=1,lchild域指向其前驱。域指向其前驱。RTag :RTag :若若 RTa