(10)--第4章 树和二叉树-定义和性质.pptVIP

第5章树和二叉树;教学目标;主要内容;5.1树和二叉树的定义;树是n个结点的有限集;凹入表示;根

叶子

森林

有序树

无序树;——即上层的那个结点(直接前驱)

——即下层结点的子树的根(直接后继)

——同一双亲下的同层结点（孩子之间互称兄弟）

——即双亲位于同一层的结点（但并非同一双亲）

——即从根到该结点所经分支的所有结点

——即该结点下层子树中的任一结点;——即树的数据元素

——结点挂接的子树数;二叉树（BinaryTree）是n（n≥0）个结点所构成的集合，它或为空树（n?=?0）；或为非空树，对于非空树T：

（1）有且仅有一个称之为根的结点；

（2）除根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。;普通树（多叉树）若不转化为二叉树，则运算很难实现;二叉树基本特点：

结点的度小于等于2

有序树（子树有序，不能颠倒）;4/14/2019;4/14/2019;5.2树和二叉树的抽象数据类型定义;CreateBiTree(T,definition)

初始条件；definition给出二叉树T的定义。

操作结果：按definition构造二叉树T。

PreOrderTraverse(T)

初始条件：二叉树T存在。

操作结果：先序遍历T，对每个结点访问一次。

InOrderTraverse(T)

初始条件：二叉树T存在。

操作结果：中序遍历T，对每个结点访问一次。

PostOrderTraverse(T)

初始条件：二叉树T存在。

操作结果：后序遍历T，对每个结点访问一次。;5.3二叉树的性质和存储结构;深度为5的完全二叉树的结点数不可能是;;4/14/2019;4/14/2019;满二叉树：一棵深度为k且有2k-1个结点的二叉树。（特点：每层都“充满”了结点）

;满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。;深度为7的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为（）;性质4:具有n个结点的完全二叉树的深度必为

?log2n??+?1;4/14/2019;性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编??必为i/2。