4.2二叉树的基本操作课件-浙教版高中信息技术选修1

4.2二叉树的基本操作PART1二叉树的建立一数组实现1.完全二叉树从二叉树的根节点开始，按从上而下、自左往右的顺序对n个节点进行编号,根节点的编号为0，最后一个节点的编号为n-1。然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与数组的下标一一对应。如图甲所示的完全二叉树所对应的一维数组表示如图乙所示。一数组实现2.非完全二叉树

对于非完全二叉树，先将它补全为一棵完全二叉树，补上的节点及分支用虚线表示，如图甲所示的一棵非完全二叉树补全为图乙所示的完全二叉树。然后将补全后的完全二叉树，从它的根节点开始,按从上而下、自左往右的顺序对n个节点进行编号,根节点的编号为0，最后一个节点的编号为n-1。如图丙所示，依次把完全二叉树中原二叉树的节点用一维数组的各个元素来表示，节点编号与数组的下标一一对应。若元素值为None，则节点为空节点。思考用数组表示的二叉树的方式更适合完全二叉树还是非完全二叉树？为什么？

【例1】已知二叉树T的形态如图所示,则其对应的一维数组表示为（

）练习A.bt=["A","B","C","D","E"]

B.bt=["A","B","C",None,"D",None,None,None,"E"]C.bt=["A","B","C",None,"D",None,None,None,None,"E"]D.bt=["A","B","C",None,"D",None,None,None,None,None,"E“]C练习A【举一反三1】已知完全二叉树T可用一维数组表示为bt=[“A”,“B”,“C”,“D”,“E”,“F”,“G”]，则节点C的父节点为

，左孩子节点为

，右孩子节点为

(选填:字母A~G)。FG二链表实现由于二叉树的节点可能有两个孩子，即左孩子和右孩子，因此二叉树的节点至少需要3个域:一个数据域和两个指针域。两个指针域分别指向节点的左孩子和右孩子，这两个指针分别称为左指针和右指针，这样得到的链表也称为二叉链表。如图所示的是二叉树及其对应的二叉链表实现示意图。左指针数据右指针三list实现用嵌套列表list来实现二叉树（1）空树用None表示（2）非空二叉树用饱含三个元素的列表[d,l,r]表示，其中：d是根节点，r和l是左节点和右节点[“A”,,][“B”，“D”,“E”][“C”，None,None]二链表实现ABCGEIDFHList1=[‘A’,[‘B’,None,None],[‘C’,[‘D’,[‘F’,None,None],[‘G’,None,None]],[‘E’,[‘H’,None,None],[‘I’,None,None]]]]有如图所示的二叉树。用list表示该二叉树为（

）练习A.[‘a’,’b’,’d’,’c’,’e’]B.[‘a’,[‘b’,[‘c’,None,None],None],[‘d’,[‘e’]]]C.[‘a’,[‘b’,[‘c’]],[‘d’,[‘e’,None,None]]]D.[‘a’,[‘b’,[‘c’,None,None]],[‘d’,[‘e’,None,None]]]Dabcde练习【例2】已知二叉树T的形态如图所示，则其对应的嵌套列表为( ）A.bt=["'A",["B",["D",["E",None,None],None]],["C",None,None]]B.bt=["A",["B",None,["D",["E",None,None],None]],["C",None,None]]C.bt=["A",["'B",None,["D",["E",None,Non]],["C",None,None]]D.bt=["A",["B",None,["D",["E",None,None],None]],["C"]]B练习【举一反三2】已知二叉树T可用一维数组表示为bt=["A","B"，"C",None,"D","E","F"],请根据二叉树的建立方法,回答下列问题:(1)请绘制出二叉树的形态图。(2)请写出该二叉树list实现方法的嵌套列表bt=['A',['B',None,['D',None,None]],['C',['E',None,None],['F',None,None]]]PART2二叉树的遍历一前序遍历规则：（中左右）先访问根节点，再访问左子树，最后访问右子树。如右图的前序遍历顺序为：A-B-D-H-E-C-F-I-G-J-KABCEGKFIJDH1245678910二中序遍历规则：（左中右）先访问左子树，再访问根节点，最后访问右子树。如右图的中序遍历顺序为：D-H-B-E-A-I-F-C-J-G-K。ABCEGKFIJDH12345689107三后序遍历规则：（左

右

中）先访问左子树，再访问右子树，最后访问根节点。如右图的后序遍历顺序为：H-D-E-B-I-F-J-K-G-C-AABCEGKFIJDH12345689107三后序遍历四二叉树的基本操作

计算表达式和逆波兰式用二叉树表示例如：计算表达式：8-(3+2*6)/5+4

用二叉树表示，如右图。+-4532/+*86计算表达式：中序遍历顺序逆波兰式：后序遍历顺序若用后序遍历，则它的顺序为：8326*+5/-4+------逆波兰式四二叉树的基本操作1.二叉树的唯一性例如：前序遍历：E-A-C-B-D-G-F

中序遍历：A-B-C-D-E-F-G

求其后序遍历顺序？先画出二叉树，再用后序遍历规则求出其输出顺序后序遍历：B-D-C-A-F-G-EEACBDGFABCDEFGEABCDFGGFABCDCBD四二叉树的基本操作1.二叉树的唯一性练习：

后序遍历：H-D-E-B-I-F-J-K-G-C-A

中序遍历：D-H-B-E-A-I-F-C-J-G-K

求其前序遍历顺序？

A-B-D-H-E-C-F-I-G-J-K四二叉树的基本操作思考：前序遍历序列和后序遍历序列能否唯一确定一棵子树？前序序列：A-B后序序列：B-AABAB练习A一棵二叉树的先序遍历序列为A-B-C-D-E-F,中序遍历序列为C-BA-E-D-F,则后序遍历序列为（

）A.A-C-B-E-DB.D-E-C-B-AC.D-E-A-B-CD.C-E-D-B-A练习B一棵二叉树的前序遍历序列是A-B-D-E-C-F-