4.2二叉树的基本操作　ppt课件（25张PPT）-2023新浙教版《高中信息技术》选择性必修第一册.pptx

1、知识回顾知识回顾二叉树的性质：在任意一棵二叉树中，若度为2的节点数量为n2，叶子结点数为n0，则n0=n2+1 深 度 为 k 的 二 叉 树 最 多 有 2k-1（k =1）个 节 点。二 叉 树 的 第 k 层 上 最 多 有 2k-1（k =1）个 节 点。知识回顾知识回顾1.满 二 叉 树u 特点：每个节点的度为2或者度为0 所有叶子节点都在同一层2.完 全 二 叉 树u 特点：至多只有最下两层中的节点的度小于2最下一层的叶子节点都依次排列在该层最左边位置作业讲解作业讲解CDB作业讲解作业讲解CCA作业讲解作业讲解AB C DAB C H I J32367344.2二叉树基本操作浙江省

2、高中信息技术 选择性必修一 数据与数据结构4.2.1 4.2.1 二叉树的建二叉树的建立立 数组实现 链表实现1.数 组 实 现(1)完全二叉树从根节点开始，按从上而下，自左往右的顺序对n个节点进行编号，根节点编号为0，最后一个节点的编号为n-1。然后将节点用一组连续的数组元素来表示，节点编号与数组下标一一对应。二叉树的建立ee r c h a s h u d e j i a n l ir c h a s h u d e j i a n l i012341.数 组 实 现(2)非完全二叉树先将它补全为一颗完全二叉树，然后将补全的二叉树按照完全二叉树的数组表示。二叉树的建立ee r c h a

3、s h u d e j i a n l ir c h a s h u d e j i a n l i练一练1、某二叉树如下图所示，用数组来表示为（）D2.链 表 实 现用链表表示二叉树，至少需要3个域：一个数据域和两个指针域，两个指针域分别指向节点的左孩子和右孩子。二叉树的建立ee r c h a s h u d e j i a n l ir c h a s h u d e j i a n l i3.l i s t 实 现二叉树的建立ee r c h a s h u d e j i a n l ir c h a s h u d e j i a n l i3.l i s t 实 现二叉树的建立e

4、e r c h a s h u d e j i a n l ir c h a s h u d e j i a n l i练一练A二叉树的遍历二叉树的遍历 前序遍历 中序遍历 后序遍历u概 念：是按照一定的规则和次序访问二叉树中的所有节点，使得每个节点都被访问一次且仅被访问一次。u遍历方式：前序遍历（根-左-右）中序遍历（左-根-右）后序遍历（左-右-根）层序遍历二叉树的遍历e r c h a s h u d ee r c h a s h u d e b i a n l i b i a n l i1.前 序 遍 历u规则：若二叉树为空，则空操作返回；否则，先访问根节点，再访问左子树，最后访问右子

5、树。二叉树的遍历e r c h a s h u d ee r c h a s h u d e b i a n l i b i a n l i（根左右）2.中 序 遍 历u规则：若二叉树为空，则空操作返回；否则，先访问左子树，再访问根节点，最后访问右子树。二叉树的遍历e r c h a s h u d ee r c h a s h u d e b i a n l i b i a n l i（左根右）3.后 序 遍 历u规则：若二叉树为空，则空操作返回；否则，先访问左子树，再访问右子树，最后访问根节点。二叉树的遍历e r c h a s h u d ee r c h a s h u d e b i

6、 a n l i b i a n l i（左右根）4.层 序 遍 历u规则：若二叉树为空，则空操作返回；否则，从根节点开始，自上而下，从左往右遍历。二叉树的遍历e r c h a s h u d ee r c h a s h u d e b i a n l i b i a n l i练一练则该二叉树的前序遍历序列是()则该二叉树的中序遍历序列是()则该二叉树的后序遍历序列是()则该二叉树的层序遍历序列是()a bdg cfdgb a cfgdb fc a1.某二叉树如图所示:a bc df g练一练则该二叉树的前序遍历序列是()则该二叉树的中序遍历序列是()则该二叉树的后序遍历序列是()则该二

7、叉树的层序遍历序列是()A BDE CFGDBE A GFCDEB GFC A2.某二叉树如图所示:A BC DEF G练一练3.一棵二叉树的前序遍历序列为“abdgecf”，中序遍历序列为“gdbeacf”，则该二叉树的后序遍历序列是()A.g d e b f c a B.g d e b c f a C.g d e b a f c D.g e d b f c aA练一练4、一棵二叉树的中序遍历序列为“dbgehafic”，后序遍历序列为“dghebifca”，请画出这棵二叉树，并确认是否唯一。提示：先找到根，这样可由中序遍历得到左子树和右子树，然后再在子树中继续重复这一过程。a ab bd de eg gh hc cf fi i练一练5.(多选题)已知6个节点的二叉树的前序遍历序列为ABCDEF，后序遍历序列为CBEFDA，则该二叉树的可能的中序遍历序列是()A.CBAEDF B.BCAFDE C.BCAEDF D.CBAFDEAC