第7章树和二叉树第1讲-树的概念.pptx

第7章 树和二叉树; 树：T={D，R}。D是包含n个结点的有限集合（n≥0）。当n=0时为空树，否则关系R满足以下条件: ;　树是由n（n≥0）个结点组成的有限集合（记为T）。其中： ;思考题 请你列出几个现实生活中属于树形结构的数据。;7.1.2 树的（逻辑）表示;（2）文氏图表示法。使用集合以及集合的包含关系描述树结构。;（3）凹入表示法。使用线段的伸缩关系描述树结构。;（4）括号表示法。用一个字符串表示树。 基本形式: 根(子树1，子树2，…，子树m);1、结点的度与树的度：树中一个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为树的度，通常将度为m的树称为m次树或者m叉树。 ;2、分支结点与叶结点：度不为零的结点称为非终端结点，又叫分支结点。度为零的结点称为终端结点或叶结点（或叶子结点）。 度为1的结点称为单分支结点；度为2的结点称为双分支结点，依此类推。;;;;6、结点的层次和树的高度：树中的每个结点都处在一个层次上。结点的层次从树根开始定义，根结点为第1层，它的孩子结点为第2层，以此类推，一个结点所在的层次为其双亲结点所在的层次加1。 树中结点的最大层次称为树的高度（或树的深度）。;7、有序树和无序树：若树中各结点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。;8、森林：n（n＞0）个互不相交的树的集合称为森林。 只要把树的根结点删去就成了森林。 反之，只要给n棵独立的树加上一个结点，并把这n棵树作为该结点的子树，则森林就变成了一颗树。;性质1 树中的结点数等于所有结点的度数之和加1。;? 根结点加上一个分支;;性质2 度为m的树中第i层上至多有mi-1个结点（i≥1）。; 性质3 高度为h的m次树至多有 个结点。;性质4 具有n个结点的m次树的最小高度为?logm(n(m-1)+1)?。;　 解：设含n个结点的3次树的最小高度为h：;则有： 1+31+32+…+3h-2 ＜ n ≤ 1+31+32+…+3h-1 (3h-1-1)/2 ＜n≤ (3h-1)/2 3h-1＜2n+1≤3h 即：h= ? log3(2n+1)?。;最大高度？; ━━本讲完━━