4.2二叉树的基本操作课件2024-2025学年高二上学期选择性必修1《数据与数据结构》第四章浙教版（2019）

4.2 二叉树的基本操作 《数据与数据结构》 一、二叉树的建立 1.一维数组实现 – 完全二叉树 A B C D E 0 1 2 3 4 5 6 7 A B C D E 0 1 2 3 4 bt = [“A”, “B”, “C”, “D”, “E”] 按自上而下、自左向右的顺序对n个节点进行编号，根节点是0，最后节点是n-1。 一、二叉树的建立 A C B 0 1 2 3 4 5 6 A B C 0 1 2 3 4 5 6 1.一维数组实现 – 非完全二叉树 bt = [“A” , None, “B” , None , None , None, “C”] 练习：绿本P41例1 补全为一棵完全二叉树 None：表示空节点 一、二叉树的建立 1.一维数组实现 A B C D E 0 1 2 3 4 5 6 A B C D E A C B 0 1 2 3 4 5 6 A B C 对于完全二叉树，一维数组的表达方式简单又节省空间。 对于非完全二叉树，一维数组的表达方式虽然简单，却容易造成存储空间的浪费。 一、二叉树的建立 重要结论：建议做个笔记 0 1 2 3 4 5 6 A B C D E 下标为 i 的节点的孩子节点的下标为 左孩子： 右孩子： 2*i+1 2*i+2 下标为 i 的节点的父节点的下标为 非根节点 i>0 (i-1)//2 A B C D E 0 1 2 3 4 i 2*1+1 2*1+2 i (3-1)//2= 一、二叉树的建立 2.链表实现 A B C D E F G 由二叉树定义可知，二叉树的每个节点最多有两个孩子，即左孩子和右孩子。因此，可将节点数据结构定义为一个数据域和两个指针域。 两个指针域分别指向节点的左孩子和右孩子，这两个指针分别称为左指针和右指针。 左孩子指针 数据域 右孩子指针 lchild data rchild 一、二叉树的建立 2.链表实现 A B C D E G F A B ∧ C ∧ E ∧ D ∧ 头指针 ∧ G ∧ ∧ F ∧ 如图所示，是将左图的二叉树采用链表结构存储，这种链表也称为二叉链表。 ∧代表“无后继指针” 拓展链接 二叉树的list（列表）实现 二叉树节点可以看成一个三元组，元素是左、右子树和本节点数据。Python的列表可以用于构造这样的三元组，可以使用嵌套列表来模拟二叉树，非空二叉树可以用包含三个元素的列表[data,left,right]来表示每一个节点，其中data是根节点的元素，left和right是两棵子树，空树或空节点用None表示。 A B C D E G F H I [‘A’,[‘B’,None,None], [‘C’,[‘D’, [‘F’,None,None], [‘G’,None,None]], [‘E’,[‘H’, None,None], [‘I’, None,None]]]] 练习：绿本P41例2 二、二叉树的遍历（重难点内容） 二叉树的遍历是指按照一定的规则和次序依次访问二叉树中的所有节点，使得所有节点都被访问有且仅有一次。 主要看根节点是什么时候遍历 遍历的方式 前序遍历 根左右 中序遍历 左根右 后序遍历 左右根 二、二叉树的遍历 1.前序遍历 规则：根左右 1、若所在二叉树为空，则空操作返回； 2、先访问根节点 3、再访问左子树 4、再访问右子树 A B C D E G F H I K J 二、二叉树的遍历 1.前序遍历:根左右 （1）整个树遍历： A/ B / C / （2）A左子树遍历：B/ D /E / （3）B左子树遍历：D/None/H （4）B右子树遍历：E/None/None （5）A左子树遍历：B-D-H-E （6）整个树遍历：A/ B-D-H-E / C / （7）整个树遍历：A/ B-D-H-E / C-F-I-G-J-K/ A B C D E G F H I K J 根 左 右 B D E H 左 根 右 D H 左 根 前序遍历的顺序为：A-B-D-H-E-C-F-I-G-J-K 建议：补齐二叉树 二、二叉树的遍历 2.中序遍历：左根右 A B C D E G F H I K J 根 左 右 （1）整个树遍历： /A/ / （2）A左子树遍历： / B / / （3）B左子树遍历：None/D/H （4）B右子树遍历：None/E/None （5）A左子树遍历：D-H-B-E （6）整个树遍历：D-H-B-E/A/ / （7）整个树遍历：D-H-B-E/A/I-F-C-J-G-K 中序遍历的顺序为：D-H-B-E-A-I-F-C-J-G-K 二、二叉树的遍历 3.后序遍历:左右根 后序遍历的顺序为：H-D-E-B-I-F-J-K-G-C-A A B C D E G F H I K J 根 左 右 二、二叉树的遍历 – 课堂练习 A B C D E G F I H J 前序遍历： 中序遍历： 后序遍历： A-B-D-H-I-E-C-F-J-G H-D-I-B-E-A-J-F-C-G H-I-D-E-B-J-F-G-C-A 三、遍历二叉树的应用1 – 表达式树 中缀表达式（中序遍历）： 8-(3+2*6)/5+4 8 / - 4 + + 5 3 * 2 6 构造表达式树，运算数作为叶子节点，运算符都是分支(根)节点。 后缀表达式（后序遍历）： 8 3 2 6 * + 5 / - 4 + 逆波兰表达式 已知某二叉树的前序（根左右）遍历为A-B-D-H-I-E-C-F-G，中序（左根右）遍历为H-D-I-B-E-A-F-C-G,请绘制二叉树形态示意图，写出后序（左右根）遍历为序列，思考二叉树是否唯一。 后序遍历为：H-I-D-E-B-F-G-C-A 三、遍历二叉树的应用2：推导出第三种遍历序列 A B C D G E F I H 绿本P42第3题 已知某二叉树的后序（左右根）遍历为G-D-H-E-B-I-F-C-A，中序（左根右）遍历为D-G-B-E-H-A-C-I-F,请绘制二叉树形态示意图，写出前序（根左右）遍历序列，思考二叉树是否唯一。 前序遍历为：A-B-D-G-E-H-C-F-I 三、遍历二叉树的应用2：推导出第三种遍历序列 A B C D G E F H I 二、二叉树的遍历 已知某二叉树的前序遍历为A-B-D-C-E-F-G，后序遍历为D-B-F-E-G-C-A,请绘制二叉树形态示意图，写出中序遍历序列，思考二叉树是否唯一。 A B C D G E F A B C D G E F 结论：只有前序遍历和后序遍历序列，不能确定唯一的二叉树，即没有中序遍历序列无法确定唯一的二叉树。 练习：绿本P42例3 四、课堂总结 二叉树的建立 数组实现 完全二叉树 非完全二叉树 链表实现 二叉树的遍历 前序遍历 – 根左右 中序遍历 – 左根右 后序遍历 – 左右根 $$