计算机数据结构 第6章 树和二叉树.ppt

第6章树和二叉树 树的定义和基本术语 二叉树 遍历二叉树和线索二叉树 树和森林 哈夫曼树及其应用 本章学习要点 掌握 树和二叉树的性质，相关术语及基本概念。 二叉树的两种存储方法，重点是链式存储据。 二叉树三种顺序遍历及其递归实现算法。 二叉树的层次遍历 创建链式存储的二叉树的算法。 中序线索二叉树的算法：中序线索二叉树上基本算法（遍历、求指定结点的前驱和后继、查找指定值的结点）。 树的遍历算法（先根遍历、后根遍历）；森林的遍历算法（前序遍历，后序遍历） 哈夫曼树的概念；哈夫曼树的构造算法；哈夫曼编码 通过本章的算法的学习，让学生认识到递归定义的数据结构之下求解相应问题，思路清晰和简洁算法设计方法是采用递归的方式。 理解 二叉树三种遍历的非递归算法及其与栈的关系 在中序线索树指定结点下插入新结点的算法，学会在复杂情形下分类讨论的方法。 树的三种存储结构（双亲表示法、孩子表示法、孩子兄弟表示法）及各自的特点（优点、缺点） 掌握树、森林和对应的二叉树相互转换算法。 本章作业 6.3 6.5 6.7 6.12 6.13 6.19 6.21 6.27 6.29 6.42 6.43 本章教学重点和难点 教学重点 二叉树的性质；二叉树的链式存储。 二叉树三种顺序遍历算法，遍历算法的应用。 中序线索二叉树的算法及其简单应用。 哈夫曼树的构造和编码算法—注意程序实现方法 教学难点 二叉树性质的运用 二叉树三种遍历的非递归算法。 中序线索二叉树的理解及先序后序线索算法的实现。 二叉树中，学会递归的思想求解问题，用遍历的典型算法解决一些具体问题。 第6章树和二叉树 树型结构是一类重要的非线性数据结构。 其中常见的是树和二叉树 树是以分支关系定义的层次结构 树结构在客观世界中广泛存在 人类社会的族谱 社会组织结构 在计算机领域 编译程序中表示源程序的语法结构 数据库中是信息的重要组织形式之一 操作系统中的进程管理 本章主要讨论 二叉树的存储及各种操作 研究树和森林与二叉树的转换关系 树的应用 6.1树的定义和基本术语 树(tree)是n(n≥0)个结点的有限集。 在任意一颗非空树中 有且仅有一个特定的称为根(root)的结点; 当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一颗树，并且称为根的子树(SubTree)。 特点 没有结点的树称为空树 树中各子树是互不相交的 树的示例 抽象数据类型树的定义 ADT Tree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树 若D仅含一个数据元素，则R为空集，否则R={H}，H是如下二元关系： (1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2)若D-{root}≠Φ，则存在D-{root}的一个划分，D1,D2,…,Dm(m0)，对任意j≠k(1≤j,k≤m)有Dj∩Dk=Φ，且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di,有root,xi∈H。 (3)对应于D-{root}的划分，H-{root,x1,…,root,xm}有唯一的一个划分H1,H2,…,Hm(m0)，对任意j≠k(1≤j,k≤m)有Dj∩Dk=Φ,且对任意的i(1≤i≤m)，Hi是D上的二元关系，(Di,{Hi})是一颗符合本定义的树，称为根root的子树 基本操作 InitTree(T) DestroyTree(T) CreateTree(T,definition) ClearTree(T) TreeEmpty(T) TreeDepth(T); Root(T) Value(T,cur_e); Assign(T,cur_e,value) Parent(T,cur_e) LeftChild(T,cur_e) RightChild(T,cur_e) InsertTree(T,p,I,c) DeleteTree(T,p,i) TraverseTree(T,visit()) }//ADT Tree 基本术语 结点(node)——包括一个数据元素及若干指向其子树的分支 结点的度(degree)——结点拥有的子树数 叶子(leaf)或终端结点——度为0的结点 非终端结点或分支结点——度不为0的结点 内部结点——除根结点外的分支结点 树的度——树中各结点度的最大值 孩子(child)——结点的子树的根称为该结点的孩子 双亲(parents)——孩子结点的上层结点叫该结点的双亲 兄弟(sibling)——同一个双亲的孩子互为兄弟 祖先——从根结点到该结点所经分支上的所有结点 子孙——以某结点为根的子树中的任一结点称为根的子孙 结点的层次(level)——从根结点算起，