圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台第6章树和二叉树[视频讲解]树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结构。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。本章将详细讨论树和二叉树数据结构，主要介绍树和二叉树的概念、术语，二叉树的遍历算法。树和二叉树的各种存储结构以及建立在各种存储结构上的操作及应用等。6.1树的定义和基本术语一、树的定义和基本术语1．树的定义树（Tree）是n（n≥0）个结点的有限集，n＝0时称为空树；否则，在一棵非空树中：（1）有且只有一个特定的称为根（Root）的结点；（2）n＞1时，其余的结点被分为m（m＞0）个互不相交的有限子集T1，T2，…，Tm，其中每个子集本身又是一棵树，称其为根的子树（Subtree）。1/110圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台这是树的递归定义，即用树来定义树，而只有一个结点的树必定仅由根组成，如图6-1（a）所示。图6-1树的示例形式2．树的基本术语（1）结点（node）：树是由有限个元素组成的集合，每个元素都称作一个结点。（2）结点的度（degree）、树的度：结点拥有的子树数称为结点的度。树中各结点度的最大值称为树的度。图6-1（b）中结点A的度是3，结点B的度是2，结点M的度是0，树的度是3。（3）叶子（leaf）结点、非叶子结点：树中度为0的结点称为叶子结点（或终端结点）。度不为0的结点称为非叶子结点（或非终端结点或分支结点）。除根结点外，分支结点又称为内部结点。图6-1（b）中结点H、I、J、K、L、M、N是叶子结点，而所有其他结点都是分支结点。（4）孩子结点、双亲结点、兄弟结点一个结点的子树的根称为该结点的孩子结点（child）或子结点；相应地，该结点是其孩2/110圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台子结点的双亲结点（parent）或父结点。如图6-1（b）中结点B、C、D是结点A的子结点，而结点A是结点B、C、D的父结点；类似地结点E、F是结点B的子结点，结点B是结点E、F的父结点。同一双亲结点的所有子结点互称为兄弟结点。如图6-1（b）中结点B、C、D是兄弟结点；结点E、F是兄弟结点。（5）层次、堂兄弟结点规定树中根结点的层次为1，其余结点的层次等于其双亲结点的层次加1。若某结点在第l（l≥1）层，则其子结点在第l＋1层。双亲结点在同一层上的所有结点互称为堂兄弟结点。如图6-1（b）中结点E、F、G、H、I、J。（6）结点的层次路径、祖先、子孙从根结点开始，到达某结点p所经过的所有结点成为结点p的层次路径（有且只有一条）。结点p的层次路径上的所有结点（p除外）称为p的祖先（ancester）。以某一结点为根的子树中的任意结点称为该结点的子孙结点（descent）。（7）树的深度（depth）：树中结点的最大层次值，又称为树的高度，如图6-1（b）中树的高度为4。（8）有序树和无序树：如果将树中各结点的各子树看成从左至右是有次序的（即不能互换），则该树称为有序树，否则称为无序树。（9）森林（forest）：是m（m≥0）棵互不相交的树的集合。显然，若将一棵树的根结点删除，剩余的子树就构成了森林。3．树的表示形式（1）倒悬树。是最常用的表示形式，如图6-1（b）。3/110圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台（2）嵌套集合。是一些集合的集体，对于其中任何两个集合，或者不相交，或者一个集合包含另一个集合。图6-2（a）是图6-1（b）树的嵌套集合形式。图6-2树的表示形式（3）广义表形式。图6-2（b）是树的广义表形式。（4）凹入法表示形式，如图6-2（c）所示。树的表示方法的多样化说明了树结构的重要性。二、树的抽象数据类型定义4/110圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台ADTTree{数据对象D：D是具有相同数据类型的数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R＝{如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D－{root}≠Φ，则存在D－{root}的一个划分D1，D2，…，Dm（m＞0），对任意j≠k≤m）有Dj∩Dk＝Φ，且对任意的i（1≤i≤m），唯一存在数据元素xi∈Di，有＜root，xi＞∈H；（3）对应于D－{root}的划分，H－{＜root，x1＞，…，＜root，xn＞}有唯一的一个划分点HHm（m＞0），对任意j≠k（1≤j，k≤m）有Hj∩Hk＝Φ，且对任意i（1≤i≤m），Hi是Di上的二元关{Hi}）是一棵符合本定义的树，称为根root的子树。基本操作：（查找类）Root（T）；//求树的根结点Value（T，cur_e）；//求当前结点的元素值Parent（T，cur_e）；//求当前结点的双亲结点LeftChild（T，cur_e）；//求当前结点的最左孩子RightSibling（T，cur_e）；//求当前结点的右兄弟TreeEmpty（T）；//判定树是否为空树TreeDepth（T）；//求树的深度TraverseTree（T，Visit（））；//遍历（插入类）InitTree（&T）；//初始化置空树CreateTree（&T，definition）；//按定义构造树Assign（T，cur_e，value）；//给当前结点赋值InsertChild（&T，&p，i，c）；//将以c为根的树插入为结点p的第i棵子树（删除类）ClearTree（&T）；//将树清空DestroyTree（&T）；//销毁树的结构DeleteChild（&T，&p，i）；//删除结点p的第i棵子树}ADTTree6.2二叉树5/110
严蔚敏《数据结构》(C语言版)【教材精讲+考研真题解析】讲义(6-8章)【圣才出品】
