资源描述：
《数据结构《第6章 树和二叉树》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《数据结构》第6章树和二叉树第6章树和二叉树本章学习要点◆熟悉树的递归定义、相关术语以及基本概念◆熟悉二叉树的递归定义、二叉树的有关术语以及基本概念◆掌握二叉树的基本性质以及相应的证明方法◆了解二叉树的两种存储结构、各种存储方法的特点和适用范围◆熟练掌握二叉树的各种遍历算法，能通过应用二叉树的遍历操作实现二叉树的其它基本操作◆了解线索二叉树的实质和目的，掌握在中序线索化的二叉树中，查找给定结点的前驱和后继的方法◆掌握树、森林与二叉树之间的关系和转换方法◆掌握树的各种存储结构的特点、适应范围以及树
2、和森林的遍历算法树型结构是一种应用非常广泛的非线性结构，其中以二叉树最为常用。树型结构反映了元素之间的层次关系和分支关系，它非常类似于自然界中的树。树型结构在计算机领域中广泛应用。比如，在计算机操作系统中对文件的目录管理就是采用树型结构；在编译程序中，使用树来表示程序的语法结构；在数据库系统中，树型结构也是信息的重要组织形式之一。本章将详细讨论二叉树的逻辑结构、各种存储结构及其基本操作的实现，研究树、森林和二叉树之间的转换关系，最后介绍一个二叉树的应用实例____Huffman树及其应用。6.1
3、树的定义和基本术语6.1.1树的定义树T（Tree）是n(n>=0)个数据元素（结点）的有限集合D，如果D为空集，则称T为空树；否则有下面的定义：（1）在D中有且仅有一个特定的结点，称为根结点；（2）当n>1时，其余的结点可分成m(m>0)个互不相交的有限集：T1,T2,…,Tm，期中每个集合又都是一棵树，并称它们为树T的根结点的子树。树是以递归的方式来定义的，即在叙述树的定义的过程中又用到了树的概念。树的这种递归定义方式反映了树型结构的层次特性。直观地讲，树是由根结点和若干棵子树组成，其中的每
4、棵子树又都是由一个根结点和它自己的若干棵子树组成，依此类推。例如，图6.1是用图形表示法表示的一棵树T。根据树的定义，T的数据元素集合D中一共包含有10个结点：D={A,B,C,D,E,F,G,H,I,J}，其中结点A为T的根结点。根结点A有三棵子树T1,T2,T3，子树的根结点分别为B、C、D均为A的孩子结点，每棵子树中所含数据元素的集合分别为D1、D2、D3，它们互不相交且为：D1={B,E,F},D2={C,G}和D3={D,H,I}。树的表示方法还有广义表表示法、集合表示法和凹入表示法等
5、。图6.2分别给出图6.1中所表示的树T的其它三种表示方法。39/39《数据结构》第6章树和二叉树6.1.2树结构中的基本术语（1）结点（Node）树的结点包含一个数据元素以及若干个指向其子树的分支指针。（2）结点的度（Degree）结点所拥有的子树个数称为该结点的度。例如，在图6.1所示的树T中，度为零的结点有E、F、G、H、I、J，度为1的结点有C，度为2的结点有B，度为3的结点有A、B。（3）叶子结点（Leaf）度为0的结点称为叶结点或终端结点。例如，树T中，其叶结点为E、F、G、H、I、
6、J。（4）分支结点（Offshoot-Node）度不为0的结点称为分支结点或非终端结点。例如，树T中，分支结点有A、B、C、D。（5）树的度（Tree-Degree）树内各结点的度的最大值称为该树的度。例如，树T的度等于3。（6）孩子（Child）结点的子树的根称为该结点的孩子。显然叶结点无孩子，例如，树T中，根结点A的孩子结点有B、C、D，结点B的孩子结点有E、F，结点C的孩子结点为G，结点D的孩子结点有H、I、J。（7）双亲（Parents）结点称为该结点的所有子树的根的双亲。显然根结点无双
7、亲，例如，树T中，根结点A为B、C、D的双亲结点，结点B为E、F的双亲结点，结点C为G的双亲结点，结点D为H、I、J的双亲结点。（8）兄弟（Brother）同一个双亲的孩子之间互为兄弟。显然根结点无兄弟，例如，树T中，结点B、C、D为兄弟结点，结点H、I、J为兄弟结点，（9）祖先（Ancestor）从根到该结点所经分支上的所有结点均为该结点的祖先。例如，树T中，结点E的祖先有A、B。（10）子孙（Offspring）以某结点为根的树中的任一个结点都是该结点的子孙。在非空树中所有结点（根结点除外）
8、均为其根结点的子孙。（11）层次（Level）从根开始定义起，根为第一层，根的孩子为第二层，若某结点在第m层，则其子树的根就在第m+1层。例如，在树T中，第一层的结点为A，第二层的结点为B、C、D，第三层的结点为E、F、G、H、I、J。（12）堂兄弟（Brother-in-low）双亲在同一层的结点互为堂兄弟。例如，在树T中，结点E、G、H为堂兄弟。（13）树的深度（Tree-Degree）树中结点的最大层数称为该树的深度。显然树的深度等于该树中叶结点的最大层数。（14）有序树与无序树如果将树中
