数据结构第7章_树和二叉树

《数据结构第7章_树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第7章树和二叉树线性结构主要反映了数据元素之间的线性顺序，很难说明数据之间的层次关系。树是一种重要的非线性数据结构，它能很好地描述结构的分支关系和层次关系，所以在文件管理系统和数据库系统中，树结构是信息的重要组织形式之一。7.1树的基本概念(教材第8章)7.1.1树的定义树（Tree）是n（n≥0）个结点的有限集合。在任意一棵非空树中：（1）有且仅有一个特定的称为根（Root）的结点；（2）当n1时，其余结点可分为m（m0）个互不相交的有限集合T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且

2、称为根的子树（Subtree）。树形结构示例ACDIHGBFEMJKLA只有一个根结点的树这是一个有13个结点的树，其中A是根结点，其余结点分成三个互不相交的结点的子集：T1={B，E，F，K，L}，T2={C，G}，T3={D，H，I，J，M}。T1、T2、T3都是A的子树，且它们本身也是一棵树树的基本术语结点的度：一个结点所拥有的子树的个数。例：结点A的度为3，结点E的度为2，结点M的度为0。树的度：树中所有结点的度的最大值。即MAX{结点的度}。例：右图所示树的度为3。ACDIHGBFEMJKL树

3、的基本术语叶子结点：度为0的结点称为叶子结点或终端结点。例：右图所示树中的结点K、L、F、G、M、I、J为叶子结点。ACDIHGBFEMJKL分支结点：度不为0的结点称为非终端结点或分支结点。除根结点外，分支结点也称为内部结点。树的基本术语孩子结点和父结点（双亲结点）：一个结点的子树的根称为该结点的孩子（Child）。相应的，该结点称为孩子的双亲（Parents）或父结点。ACDIHGBFEMJKL兄弟结点：同一个双亲的孩子之间互称为兄弟（Sibling）。树的基本术语ACDIHGBFEMJKL祖先结点

4、：从根到一个结点的路径上的所有结点称为该结点的祖先结点。子孙结点：以某结点为根的子树中的所有结点都是该结点的子孙。树的基本术语树的深度树中所有结点的层次的最大值称为树的深度或高度。即MAX{结点的层次}。例：右图所示树的深度为4。ACDIHGBFEMJKL结点的层次：一棵树从根开始定义，根为第一层，根的孩子为第二层，…，依此类推。若某结点在第i层，则其子树的根就在第i＋1层。树的基本术语森林（Forest）：m（m≥0）棵互不相交的树的集合称为森林。对树中每个结点而言，其子树的集合即为森林。CDIHGB

5、FEMJKL课堂思考下面两个叙述是否正确？根结点也可以是叶子结点。度为0的结点就是叶子结点。判断右边(a)、(b)所示图形是否树？BFEKLCDHGMJ(b)(a)√√因为树是一种非线性结构，所以不能简单地用一维数组或单链表来存储树。为了存储树，必须把树中每个结点之间存在的关系反映在存储结构之中，才能如实的表现一棵树。树的存储结构有多种表示方法，下面介绍常用的三种。7.2树的存储结构(教材第8章)7.2.1双亲表示法这种表示法要求用一维数组来存储树的有关信息，每个结点对应一个数组元素，它包含两个域：一个

6、是数据域（data），存放该结点所包含的数据；一个是指针域（parent），指出该结点的双亲结点的位置（整数）。RBCFHAEDGK0R-11A02B03C04D15E16F37G68H69K6数据域指针域在树的双亲表示法中，求某个结点的双亲结点是非常容易的，但求某个结点的孩子结点比较困难，需要遍历整个结构。7.2.2孩子表示法方法之一：把每个结点的孩子结点排列起来，构成一个单链表，则n个结点有n个孩子链表（叶子结点的孩子链表为空）。而n个头指针又组成一个线性表，采用顺序存储结构存储。每个结点只要掌握了

7、这个单链表的表头，就容易找到它的全部孩子。0R1A2B^3C4D5E^6F7G^8H^9K^716^245^89^3^RBCFHAEDGK7.2.2孩子表示法在树的孩子表示法中，寻找任意结点的孩子是比较容易的，但寻找它的双亲却比较困难。我们可以将双亲表示法和孩子表示法合在一起。0-1R10A20B^30C41D^51E^63F76G^86H^96K^716^245^89^3^RBCFHAEDGK7.2.3孩子兄弟表示法又称为二叉链表表示法(或二叉树表示法)。即以二叉链表作为树的存储结构，链表中每个结点设

8、有两个链域，一个指向该结点的第一个孩子，一个指向该结点的下一个兄弟结点。结点类型定义如下：structnode{anytypedata；structnode*firstchild，*nextsibling；}；7.3二叉树7.3.1二叉树的定义和性质1．二叉树的定义二叉树的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。二叉树有五种基本形态：二叉树（Binarytree）是