(
课件网) 4 树 第四章 A B、C、D A B、C H、I、J 3 2 3 6 7 3 4 树与二叉树 选择性必修1《数据与数据结构》 第四章 树 4.2 二叉树的基本操作 二叉树的建立 如何建立二叉树？ 可以用数组或者链表数据结构来实现！ 如何存储完全二叉树与非完全二叉树？ 按层顺序进行：先由第1层开始，依次到下一层，在每、一层中按照从左到右的顺序创建节点。 二叉树的建立 1.数组实现 编号：从二叉树的根节点开始，按从上而下、自左往右的顺序对n个节点进行编号。 根节点的编号为0，最后一个节点的编号为n-1 将二叉树的节点用一组连续的数组元素来表示，节点编号与数组的下标一一对应。 （1）完全二叉树 二叉树的建立 （1）非完全二叉树 先补全为一棵完全二叉树，补上的节点及分支用虚线表示，如图所示； 然后将补全后的完全二叉树，对n个节点按序编号。 【从根节点开始，从上而下、自左往右，范围[0,n-1]】 依次将原二叉树的节点用一维数组的各个元素来表示，节点编号与数组的下标———对应。 如何建立？ 二叉树的数组表示 A C B A C B 如何用数组存储此二叉树？ 数组下标 0 1 2 3 4 5 6 数组元素 A B C 二叉树的建立 虽然，对完全二叉树而言，一维数组的表示方式既简单又节省存储空间。 但对于一般二叉树来说，采用一维数组表示时，结构虽然简单，却容易造成存储空间的浪费。 一个深度为k，只有k个节点的树，需要个节点的存储空间才能表示出来。 2.链表实现 二叉树的建立 二叉链表： 用任意一组存储单元来存储二叉树的节点，用指向节点的指针来表示节点之间的关系。 二叉树可能有两个孩子【左孩子+右孩子】 因此二叉树的节点至少需要3个域:一个数据域和两个指针域。【左指针指向左孩子，右指针指向孩子】 拓展链接 二叉树的list实现 二叉树节点可以看成一个三元组，元素是左、右子树和本节点数据。Python的list可以用于组合这样的三个元素。下面介绍用list构造二叉树的方法。 综上，元组特点： 格式: ( , , , ) 不可任意更改元素 元组是关系数据库中的基本概念，关系是一张表，表中的每行，即数据库中的每条记录是一个元组，每列就是一个属性，在二维表里，元组也称为行。 元组和列表十分类似，只不过元组和字符串一样是不可变的，即你不能修改元组，元组通过圆括号中用逗号分割的项目定义，元组通常用在使语句或用户定义的函数能够安全地采用一组值的时候，即被使用的元组的值不会改变。 拓展链接 二叉树的list实现 二叉树节点可以看成一个三元组，元素是左、右子树和本节点数据。Python的list可以用于组合这样的三个元素。下面介绍用list构造二叉树的方法。 (1）空树用None表示。 (2）非空二叉树用包含三个元素的列表[d,l,r]表示，【d：根节点；l和r两棵子树】 [‘A’,[‘B’,’None’,’None’], [‘C’,[’D’,[’F’,’None’,’None’], [’G’,’None’,’None’]], [’E’,[’H’,’None’,’None’], [’I’,’None’,’None’]]]] 二叉树的list实现 请将次二叉树用list来表示： [‘A’,’None’, [’B’,[’C’,’None’,[’E’,’None’,’None’]], [’D’,[’F’,’None’,’None’],’None’]]] 二叉树的遍历 图形———直观，但在计算机处理时，需要把非线性结构 线性序列，才能方便程序的实现。 通过二叉树的遍历即可，遍历方式主要分为：前序遍历、中序遍历和后序遍历等。 1.前序遍历 规则: 若二叉树为空，则空操作返回; 否则，根节点 左子树 右子树 前序遍历顺序为:A-B-D-H-E-C-F-I-G-J-K 二叉树的遍历 2.中序遍历 规则: 若二叉树为空，则空操作返回; 否则，左子树 根节点 右子树 中序遍历顺序为:D-H-B-E-A-I-F-C-J-G-K 注意事项！！！ 如果选取其中一种遍历策略 ... ...
