DS006.1 树与二叉树(I).ppt

Data Structure Chpter 6: Binary Tree Chpter 6: Binary Tree Data Structure College of Science, Xidian University 第六章 树与二叉树 西安电子科技大学·理学院 hjTang@xidian.edu.cn 主要内容 $6.1 树的定义和基本术语 $6.2 二叉树 $6.3 遍历和线索二叉树 $6.4 哈夫曼树及其应用 $6.5 回溯法与树的遍历 $6.1 树的定义与基本术语 树的定义 ADT描述 树的表示 树的基本概念 森林的概念 人机对弈问题的树状结构 树的示例 一棵树包含一个称作结点的有限集 和一个用于连接顶点的称之为边的有限集 T = {D, E}，其中D为顶点集，E为边集 树是n个结点的有限集 $6.1.1 树的定义 树的定义：在任意一棵非空的树中 有且只有一个特定的，称为根的结点 当结点的个数大于1时，其余的结点又可以分为m个互补相交的有限集T1~Tm，其中每个集合本身又是一棵树，并称之为根的子树 树的另一种理解 在一棵非空树中 有且只有一个结点没有直接前驱，我们称之为根结点 除根结点外，其它所有结点有且只有一个直接前驱。 每个结点可以有多个直接后继 树的基本术语 图中关于顶点的度的定义 与一个顶点相关联的边的数目称作顶点的度 入边——指向顶点的边 出边——逆向顶点的边 入度——顶点的入边数目 出度——顶点的出边数目 顶点的度＝入度＋出度 树的度 节点的度：节点拥有子树的个数 树的度：最大节点的度 在非空树中 有且只有一个根结点（root） 根结点的入度定义为0 除根结点外，其余顶点有且只有一条入边 每个结点可以有0条、1条或多条出边 叶(终端)结点：出度为0的结点 分支结点：出度非0的结点 内部结点：非根非叶 前驱与后继 孩子结点(child)：结点子树的根结点称为该结点的～ 双亲结点(parent)： 兄弟结点(sibling)－具有相同双亲的结点 子孙结点(descendent) 祖先结点(ancestor)：从根到该结点路径上的所有结点 结点的层次 根结点的层次＝1 孩子结点的层次＝双亲结点的层次＋1 树的深度(高度)＝最大结点的层次 结点的层次＝结点到根结点间的距离(边的数目)+1 路径 在结点序列{N1, N2, …, Ni}中，恒有结点Ni-1为结点Ni的双亲结点，我们称这样的一个结点序列为一条路径 {A, B, C}, {A, E}, {A, F, G}, {A, F, H}, {A, F, I} 祖先与子孙结点 最长路径中结点的数目＝树的深度 子树 根结点下的任意一个连接结构称之为一棵子树 当结点数1时，其余结点可以分为m个互不相交的有限集，每一个集合本身又是一棵树，称为根的子树。 子树——以子树的根结点命名 子树： 子树可以是一棵空树（没有结点的树） 子树又可以有根结点和子树的树 有序树与无序树 如果将树中的各个子树看成从左到右是有次序的（即不能互换的），则称该树是有序的，否则称之为无序的 无序：交换任一结点的两棵子树后认为是相同的树 有序：交换任一结点的两棵子树后认为是不同的树 森林与树的表示 M棵互不相交的树的集合 树的表示 任何一棵树是一个二元组Tree=(root, F),其中root是数据元素，称作树的根结点，F是m棵树的森林， F=(T1, T2, …, Tm)，其中Ti=(ri, Fi)称作根root的第i棵子树；若m≠0，树与子树森林之间存在关系 RF = {root, ri} 树的应用举例 计算机组成 家族族谱 学校机构 软件分类 二叉树 二叉树是一种特殊的树型结构 二叉树的每个结点最多有2条出边（出度2） 二叉树中任何一个结点最多有两个孩子结点 二叉树是一棵有序树(左右子树不能任意交换) 二叉树的根结点最多有两棵子树，分别称为左子树和右子树 二叉树是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。 二叉树的定义 T = (D, E)，其中D为结点集，E为边集 D=Ф，则关系R= Ф，称为空二叉树 若D≠Ф, 则R={H}, H有如下二元关系 D中存在唯一的称为根的数据元素root, 它在关系R中无前驱 若D-{root}≠Ф, 则存在D1=D-{root}的一个划分{Dl, Dr} 若Dl≠Ф, 则Dl中存在唯一的元素xl, root, xl∈H,且存在Dl上的关系Hl是H的子集;若Dr≠Ф, 则Dr中存在唯一的元素xr, root, xr∈H,且存在Dr上的关系Hr是H的子集;且存在关系H={root, xl, root, xr, Hl, Hr} (Dl, {Hl})是一棵