二叉树的基本操作　课件　 【核心知识精讲精析】 浙教版（2019）高中信息技术选修1

4.2二叉树的基本操作02PART二叉树的基本操作Clickheretoaddyourtitle树的实现树的遍历满二叉树节点个数为7=23-1完全二叉树节点个数为10<24-11.每个节点的度均为2或02.

每一层上的结点数都达到最大值1.至多只有最下两层节点度数小于22.最下层的叶子节点依次排在左侧满二叉树是完全二叉树，完全二叉树不一定是满二叉树。数组表示完全二叉树把它不全为一颗完全二叉树，补上的结点分别用虚线表示。非完全二叉树优点和缺点对完全二叉树而言，顺序存储结构既简单又节省存储空间。一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。

链表表示树的实现二叉树的节点可能有两个孩子，即左孩子和右孩子，因此二叉树的节点至少需要3个域，一个数据域，2个指针域。也称为二叉链表。N个节点有几个空指针树的遍历前序遍历(根左右)树的遍历中序遍历(左根右)树的遍历后序遍历(左右根)1.8-(3+2*6)/5+42.8326*+5/-4+分别输出中序遍历和后序遍历的结果练一练后续序遍历就是逆波兰式，逆波兰式用栈是怎么样计算的？2、对应的中序遍历为？1、请画出序列为ABC所对应所有的二叉树？练一练

二叉树的基本操作

树

·二叉树的唯一性

通过二叉树任二种遍历方式能否确定一颗唯一的二叉树呢？有唯一二叉树：

前序遍历+中序遍历

后序遍历+中序遍历

前序遍历+后序遍历-----没有唯一二叉树

二叉树的基本操作

树

·二叉树的唯一性例如：前序遍历：E-A-C-B-D-G-F

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

求其后序遍历顺序？先画出二叉树，再用后序遍历规则求出其输出顺序后序遍历：B-D-C-A-F-G-EEACBDGFABCDEFGEABCDFGGFABCDCBD

二叉树的基本操作

树

·二叉树的唯一性练习：

后序遍历：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练一练一棵二叉树的前序遍历序列为“abdgecf”，中序遍历序列为“gdbeacf”，则该二叉树的后序遍历序列是()A.gdebfca B.gdebcfaC.gdebafc D.gedbfcaA二叉树Python代码实现classNode:#建立二叉树def

__init__(self,value=None,left=None,right=None):self.value=value

self.left=left#左子树

self.right=right#右子树二叉树Python代码实现root=Node('A',Node('B',Node('D'),Node('E')),Node('C',rigt=Node('F',Node('G'))))print("前序遍历：")preTraverse(root)print("中序遍历：")midTraverse(root)print("后序遍历：")afterTraverse(root)

if

__name__=='__main__’:二叉树Python代码实现defpreTraverse(root):#前序遍历ifroot==None:

returnprint(____________)preTraverse(_____________)preTraverse(______________)defmidTraverse(root):#中序遍历

if

root==None:

returnmidTraverse(____________)print(_____________)midTraverse(____________)

defafterTraverse(root):#后序遍历

if

root==None:

returnafterTraverse(_____________)afterTraverse(_____________)

print(______________)root.valueroot