数据结构第4章树

《数据结构第4章树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教学目标1、知识目标1）掌握树的基本概念；2）掌握二叉树、满二叉树、完全二叉树的概念，掌握二叉树的性质；3）掌握二叉树的存储结构、二叉树的遍历及算法；4）了解树、森林与二叉树的转换及树的存储结构；5）掌握哈夫曼树的构造过程。2、能力目标1）具有恰当的选择二叉树作为数据的逻辑结构和存储结构的能力；2）具有应用二叉树解决实际问题的能力。3、素质目标养成良好的完成工作任务、团队合作、良好沟通、创新思维和解决问题的能力。24.1树的概念树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并具有层次关系的结构。它非常类似于自然

2、界中的树。   　树结构在客观世界中是大量存在的，在计算机领域中也有着广泛的应用，如在编译程序中，用树来表示源程序的语法结构；在数据库系统可用树来组织信息。1、树的递归定义：树是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：(1)有且仅有一个特定的称为根(Root)的结点；(2)其余的结点可分为m(m≥0)个互不相交的有限子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subtree)。注意：树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干

3、棵更小的子树构成。6666662、树的表示1）树形图表示：结点用圆圈表示，结点名字写在圆圈旁或圆圈内，子树与其根之间用无向边来连接。2）嵌套集合表示法：用集合的包含关系描述树结构。3）凹入表表示法：类似于书的目录。3、树结构的基本术语1）结点的度①结点的度：一个结点拥有子树的个数称为该结点的度。②树的度：该树中结点的最大度数称为该树的度。③叶子结点：度为零的结点称为叶子或终端结点。④分支结点：度不为零的结点称分支结点或非终端结点。即除叶子结点外的结点均为分支结点。⑤内部结点：除根结点之外的分支结点统称为内部结点。⑥开始结点

4、：根结点又称为开始结点。例如：树形图表示的树用树的递归定义来分析上图所示的树：图中的树由结点的有限集T={A,B,C,D,E,F,C,H,I,J}所构成，其中A是根结点，T中其余结点可分成三个互不相交的子集：T1={B,E,F,I,J},T2={C},T3={D,G,H}。T1、T2和T3是根A的三棵子树，且本身又都是一棵树。例如T1，其根为B，其余结点可分为两个互不相交的的子集T11={E}和T12={F,I,J}，它们都是B的子树。显然T11是只含一个根结点E的树，而T12的根F又有两棵互不相交的子树{I}和{J}，

5、其本身又都是只含一个根结点的树。ABCDEFHIJG第1层第2层第3层第4层例如：该树中结点A,B,C,D的度分别为：3,2,0,2。ABCDEFHIJG第1层第2层第3层第4层例如：该树的度为结点A的度为：3。ABCDEFHIJG第1层第2层第3层第4层EIJGHABDC嵌套集合表示法表示的树F凹入表表示法表示的树ABCDEFIJGH2）结点之间的关系①孩子结点：树中某个结点的子树的根称为该结点的孩子结点。②双亲结点：孩子结点的根称为该结点的双亲。③兄弟结点：同一个双亲的孩子互称为兄弟结点。④堂兄弟：在后面介绍。⑤祖先和

6、子孙：在后面介绍。3）路径①路径或道路：若树中存在一个结点序列k1,k2,…,kj,使得ki是ki+1的双亲(1≤i

7、G之间不存在路径，因为既不能从B出发自上而下地经过若干个结点到达G，也不能从G出发自上而下地经过若干个结点到达B。ABCDEFHIJG第1层第2层第3层第4层③祖先和子孙：若树中结点k到ks存在一条路径，则称k是ks的祖先，ks是k的子孙。一个结点的祖先是从根结点到该结点路径上所经过的所有结点，而一个结点的子孙则是以该结点为根的子树中的所有结点。约定：结点k的祖先和子孙不包含结点k本身。4）结点的层数和树的深度①结点的层数：根结点的层数为1，其余结点的层数等于其双亲结点的层数加1。②堂兄弟：双亲在同一层的结点互为堂兄弟。③

8、树的深度：树中结点的最大层数称为树的深度。注意：也有将树根的层数定义为0的。5）有序树和无序树若将树中每个结点的各子树看成是从左到右有次序的，则称该树为有序树；否则称为无序树。若不特别指明，一般讨论的树都是有序树。例如：结点A的层数为1，结点B,C,D的层数为2，结点E,F,G,H的层数为3，结点I,J