二叉树的基本操作课件浙教版（2019）高中信息技术选修1（25张PPT）.pptxVIP

知识回顾二叉树的性质：③在任意一棵二叉树中，若度为2的节点数量为n2，叶子结点数为n0，则n0=n2+1②深度为k的二叉树最多有2k-1（k=1）个节点。①二叉树的第k层上最多有2k-1（k=1）个节点。

知识回顾1.满二叉树特点：①每个节点的度为2或者度为0②所有叶子节点都在同一层2.完全二叉树特点：①至多只有最下两层中的节点的度小于2②最下一层的叶子节点都依次排列在该层最左边位置

作业讲解CDB

作业讲解CCA

作业讲解ABCDABCHIJ3236734

CHZX4.2二叉树基本操作浙江省高中信息技术选择性必修一《数据与数据结构》

4.2.1二叉树的建立数组实现链表实现01

1.数组实现(1)完全二叉树从根节点开始，按从上而下，自左往右的顺序对n个节点进行编号，根节点编号为0，最后一个节点的编号为n-1。然后将节点用一组连续的数组元素来表示，节点编号与数组下标一一对应。二叉树的建立erchashudejianli01234

1.数组实现(2)非完全二叉树先将它补全为一颗完全二叉树，然后将补全的二叉树按照完全二叉树的数组表示。二叉树的建立erchashudejianli

练一练1、某二叉树如下图所示，用数组来表示为（）D

2.链表实现用链表表示二叉树，至少需要3个域：一个数据域和两个指针域，两个指针域分别指向节点的左孩子和右孩子。二叉树的建立erchashudejianli

3.list实现二叉树的建立erchashudejianli

3.list实现二叉树的建立erchashudejianli

练一练A

二叉树的遍历前序遍历中序遍历后序遍历02

概念：是按照一定的规则和次序访问二叉树中的所有节点，使得每个节点都被访问一次且仅被访问一次。遍历方式：①前序遍历（根-左-右）②中序遍历（左-根-右）③后序遍历（左-右-根）④层序遍历二叉树的遍历erchashudebianli

1.前序遍历规则：若二叉树为空，则空操作返回；否则，先访问根节点，再访问左子树，最后访问右子树。二叉树的遍历erchashudebianli（根左右）

2.中序遍历规则：若二叉树为空，则空操作返回；否则，先访问左子树，再访问根节点，最后访问右子树。二叉树的遍历erchashudebianli（左根右）

3.后序遍历规则：若二叉树为空，则空操作返回；否则，先访问左子树，再访问右子树，最后访问根节点。二叉树的遍历erchashudebianli（左右根）

4.层序遍历规则：若二叉树为空，则空操作返回；否则，从根节点开始，自上而下，从左往右遍历。二叉树的遍历erchashudebianli

练一练则该二叉树的前序遍历序列是()则该二叉树的中序遍历序列是()则该二叉树的后序遍历序列是()则该二叉树的层序遍历序列是()abdgcfdgbacfgdbfca1.某二叉树如图所示:abcdfg

练一练则该二叉树的前序遍历序列是()则该二叉树的中序遍历序列是()则该二叉树的后序遍历序列是()则该二叉树的层序遍历序列是()ABDECFGDBEAGFCDEBGFCA2.某二叉树如图所示:ABCDEFG

练一练3.一棵二叉树的前序遍历序列为“abdgecf”，中序遍历序列为“gdbeacf”，则该二叉树的后序遍历序列是()A.gdebfca B.gdebcfaC.gdebafc D.gedbfcaA

练一练4、一棵二叉树的中序遍历序列为“dbgehafic”，后序遍历序列为“dghebifca”，请画出这棵二叉树，并确认是否唯一。提示：先找到根，这样可由中序遍历得到左子树和右子树，然后再在子树中继续重复这一过程。abdeghcfi

练一练5.(多选题)已知6个节点的二叉树的前序遍历序列为ABCDEF，后序遍历序列为CBEFDA，则该二叉树的可能的中序遍历序列是() A.CBAEDF B.BCAFDE C.BCAEDF D.CBAFDE AC