高中信息技术浙教版（2019）选修1 第四章　课时2　二叉树的基本操作 课件.pptxVIP

课时2二叉树的基本操作;1.掌握使用数组和链表等数据结构建立二叉树的方法。2.掌握二叉树遍历的基本操作方法。;;;1.建立二叉树的方法;2.用数组实现二叉树的创建;(3)使用数组(列表)建立二叉树

空树用None表示，非空二叉树用包含三个元素的列表[d，l，r]表示，分别存储着根节点的元素和左右子树，因此二叉树的list实现采用嵌套括号([])的形式。

用数组(列表)构建二叉树的代码如下：

defcreate_tree(tree，data)：

foriinrange(len(data))：

depth＝0#程序的第0层相当于树的第1层

ifi＝＝0:#根节点

tree[depth]＝data[i];else：

#while循环结束表示找到存放数据的节点(索引)位置

whiletree[depth]！＝0：

ifdata[i]tree[depth]：#往右寻找

depth＝depth*2＋2#父节点的右孩子位置

else：#往左寻找

depth＝depth*2＋1#父节点的左孩子位置

tree[depth]＝data[i]#找到数据应存放的节点位置，并存储该节点;3.用链表实现二叉树的创建;ifself.left：

self.left.insert(data)#递归调用往下一层

else：

self.left＝Node(data)#建立新节点存放数据

else:#插入值大于当前节点值

ifself.right：

self.right.insert(data)

else：

self.right＝Node(data)

else:#如果根节点不存在;4.二叉树的遍历;②中序遍历

中序遍历的规则为：若二叉树为空，则空操作返回；否则，先访问_________，再访问根节点，最后访问_________。

③后序遍历

后序遍历的规则为：若二叉树为空，则空操作返回；否则，先访问左子树，再访问右子树，最后访问_________。;二叉树的三种遍历是根据访问根节点的先后次序来命名的，前序遍历的访问顺序为根左右(BLR)，中序遍历的访问顺序为左根右(LBR)，后序遍历的访问顺序为左右根(LRB)。;;例1下列二叉树中，中序遍历结果为BAEDFC的是();;;;;;;A.该二叉树不是完全二叉树

B.该二叉树的深度为4

C.该二叉树的前序遍历结果为ACBDEGF

D.该二叉树所对应的一维数组表示为：;;;;2.有一棵二叉树如图所示，下列说法正确的是();3.下列二叉树中，前序和中序遍历结果一??的选项是();4.有二叉树形态如图所示，后序遍历结果为abcdefg，则树中与c同层的节点是();5.某二叉树从根节点开始，按从上到下、自左往右的顺序用A－G字母表示，若补全为完全二叉树后，用一维数组表示如图所示。;;6.用一维数组表示二叉树，如下表所示：;;7.某二叉树的前序遍历结果为GFDECAB，中序遍历结果为DFGCAEB。关于该二叉树，以下说法，正确的是();8.某二叉树的中序遍历顺序为DHBEAFCG，后序遍历为HDEBFGCA，则节点E是()

A.A节点的孩子节点 B.叶子节点

C.H节点的父亲节点 D.F节点的兄弟节点;;1.如图所示的二叉树，若要得到一个递增序列，可以采用的遍历方式是();2.某二叉树如图所示，下列说法正确的是();A.该二叉树是一棵完全二叉树

B.该二叉树的叶子节点数是3个

C.该二叉树的中序遍历结果是DCBEAF

D.该二叉树的度为2;4.数学表达式3/(5*2)可用二叉树表示，如图所示。;5.某二叉树的树形结构如图所示，其后序遍历结果为FBCEAD，则前序遍历结果为();6.已知某二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBDAEF，则下列说法正确的是()

A.其后序遍历结果为DCBFEA

B.该二叉树为完全二叉树

C.该二叉树深度为3，叶子节点数为3

D.该二叉树用一维数组实现需要6个节点的存储空间才能表示;7.有一棵二叉树，如图所示，下列说法正确的是();8.对于右图所示的二叉树，下列说法正确的是();9.用一维数组表示二叉树，如下表所示：;10.某二叉树用一维数组实现的示意图如下所示。;11.二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为()

A.abcde B.abdec C.debac D.adbce;12.有二叉树的前序遍历序列为A－B－C－E－F－G－D，中序遍历序