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

课时2二叉树的基本操作

课时目标

1.掌握使用数组和链表等数据结构建立二叉树的方法。2.掌握二叉树遍历的基本操作方法。

1.建立二叉树的方法

建立二叉树的操作方法为：按照二叉树层的顺序进行，先由第________层开始，依次到下一层，在每一层中按照从__________的顺序创建节点。

2.用数组实现二叉树的创建

(1)完全二叉树

①从二叉树的__________开始，按__________、自左向右的顺序对n个节点进行编号，根节点的编号为0，最后一个节点的编号为________。

②然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与__________一一对应。

(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.用链表实现二叉树的创建

二叉树用链表实现时，二叉树的节点至少需要三个域：一个__________和两个__________。如下图所示：

Lchild

data

rchild

其中lchild和rchild是指针域，存放指向节点的左孩子节点和右孩子节点的指针，data是数据域。

使用链表建立有哪些信誉好的足球投注网站二叉树如下：

definsert(self，data)：

ifself.data：#如果根节点不存在

ifdataself.data：#插入值小于当前节点值

ifself.left：

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

else：

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

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

ifself.right：

self.right.insert(data)

else：

self.right＝Node(data)

else:#如果根节点不存在

self.data＝data#建立根节点

4.二叉树的遍历

(1)二叉树的遍历是指按照一定的____________访问二叉树中的所有节点，使得每个节点都被访问一次且________________。

(2)根据访问根节点的先后顺序可以分为：前序遍历、____________和____________。

①前序遍历

前序遍历，也称为先序遍历，前序遍历的规则为：若二叉树为空，则空操作返回；否则，先访问________，再访问________，最后访问________。

②中序遍历

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

③后序遍历

后序遍历的规则为：若二叉树为空，则空操作返回；否则，先访问左子树，再访问右子树，最后访问________。

二叉树的三种遍历是根据访问根节点的先后次序来命名的，前序遍历的访问顺序为根左右(BLR)，中序遍历的访问顺序为左根右(LBR)，后序遍历的访问顺序为左右根(LRB)。

例1下列二叉树中，中序遍历结果为BAEDFC的是()

听课笔记：

变式训练某二叉树前序遍历为ABDFGCEH，后序遍历为FGDBHECA，则下列选项不可能是此二叉树的是()

例2某二叉树的树形结构