42二叉树的基本操作课件高二上学期选择性必修1《数据与数据结构》第四章浙教版

4.2二叉树的基本操作《数据与数据结构》一、二叉树的建立1.一维数组实现–完全二叉树ABCDE01234567ABCDE01234bt=[“A”,“B”,“C”,“D”,“E”]按自上而下、自左向右的顺序对n个节点进行编号，根节点是0，最后节点是n-1。一、二叉树的建立ACB0123456ABC01234561.一维数组实现–非完全二叉树bt=[“A”,None,“B”,None,None,None,“C”]练习：绿本P41例1补全为一棵完全二叉树None：表示空节点一、二叉树的建立1.一维数组实现ABCDE0123456ABCDEACB0123456ABC对于完全二叉树，一维数组的表达方式简单又节省空间。对于非完全二叉树，一维数组的表达方式虽然简单，却容易造成存储空间的浪费。一、二叉树的建立重要结论：建议做个笔记0123456ABCDE下标为i的节点的孩子节点的下标为左孩子：右孩子：2*i+12*i+2下标为i的节点的父节点的下标为非根节点i>0(i-1)//2ABCDE01234i2*1+12*1+2i(3-1)//2=一、二叉树的建立2.链表实现ABCDEFG由二叉树定义可知，二叉树的每个节点最多有两个孩子，即左孩子和右孩子。因此，可将节点数据结构定义为一个数据域和两个指针域。两个指针域分别指向节点的左孩子和右孩子，这两个指针分别称为左指针和右指针。左孩子指针数据域右孩子指针lchilddatarchild一、二叉树的建立2.链表实现ABCDEGFAB∧C∧E∧D∧头指针∧G∧∧F∧如图所示，是将左图的二叉树采用链表结构存储，这种链表也称为二叉链表。∧代表“无后继指针”拓展链接二叉树的list（列表）实现

二叉树节点可以看成一个三元组，元素是左、右子树和本节点数据。Python的列表可以用于构造这样的三元组，可以使用嵌套列表来模拟二叉树，非空二叉树可以用包含三个元素的列表[data,left,right]来表示每一个节点，其中data是根节点的元素，left和right是两棵子树，空树或空节点用None表示。ABCDEGFHI[‘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、再访问右子树ABCDEGFHIKJ二、二叉树的遍历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/ABCDEGFHIKJ根左右BDEH左根右DH左根前序遍历的顺序为：A-B-D-H-E-C-F-I-G-J-K建议：补齐二叉树二、二叉树的遍历2.中序遍历：左

根

右ABCDEGFHIKJ根左右（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-AABCDEGFHIKJ根左右二、二叉树的遍历–课堂练习ABCDEGFIHJ前序遍历：中序遍历：后序遍历：A-B-D-H-I-E-C-F-J-GH-D-I-B-E-A-J-F-C-GH-I-D-E-B-J-F-G-C-A三、遍历二叉树的应用1

–表达式树中缀表达式（中序遍历）：8-(3+2*6)/5+48/-4++53*26构造表达式树，运算数作为叶子节点，运算符都是分支(根)节点。后缀表达式（后序遍历）：8326*+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：推导出第三种遍历序列

ABCDGEFIH绿本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：推导出第三种遍历序列

ABCDGEFHI二、二叉树的遍历已知某二叉树的前序遍历为A-B-D-C-E-F-G，后序遍历为D-B-F-E-G-C-A,请绘制二叉树形态示意图，写出中序遍历序列，思考二叉树是否唯一。ABCDG