数据结构课件C语言 第0 6章.ppt

《数据结构课件C语言 第0 6章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《数据结构》第六章树和二叉树（重点）第六章树和二叉树内容树、二叉树、森林的概念和性质，树与二叉树的转换，树形结构的存储，遍历，哈夫曼树的概念及应用。要求通过学习和上机，深刻理解树形结构的递归特性，为应用它解决实际问题奠定理论基础并获得实践经验。理解并准确叙述树、二叉树、森林及其有关概念并熟悉它们的基本性质，熟悉树形结构的存储结构和中序线索二叉树，熟悉树的遍历方法，尤其是二叉树的前序、中序和后序遍历的递归与应用，知道树形结构的若干应用。2重点1、树、二叉树的概念和性质2、树结构的存储3、树和二叉树的遍历算法以及树的前序、中序和后序遍历算法

2、难点1、树形结构的存储方法2、中序线索树3、二叉树遍历的非递归算法4、树的应用第六章树和二叉树3树的逻辑结构——它定义一类重要的非线性结构。树结构在计算机科学的很多领域都得到了广泛的应用。树结构可应用于诸如编译程序中表示源程序的语法结构数据库系统中的信息组织文件目录电路分析社会各个组织和管理机构家谱书的章节编目军队编制树型结构是结点之间有分支、层次关系的结构，它非常类似于自然界中的树。树型结构在客观世界中大量存在。树的结构定义4定义1树Tree=(D,R)是一种层次数据结构，其中D是具有相同特性的数据元素（称为树结点）的有限集合，R是

3、定义在D上的二元关系。在这种关系中，有且仅有一个特定的无前趋的结点（称为树的根，记作root），其余的每一个结点有且仅有一个直接前趋。注.树的这种结构对每一个结点的后继不加限制，任何一个结点都可以有0至多个后继结点。定义2（树的递归定义）树是n(n≥1)个结点的有限集合，其中(1)有且仅有一个特定的称之为根（root）的结点；(2)其余的结点可分为m(m≥0)个互不相交的集合T1,T2,…，Tm，而每一个集合本身又是一棵树，并且称为根的子树（subtree）。为了讨论方便，有时也将结点数为0的空集合也看成树，并称之为空树。树的结构定义

4、5树的表示示例ABCACDBEF－/+aefb－cdA仅有根结点的树一般树ACDBEFHJKLGIM二叉树树的结点：一个个的记录树的枝或边：指向其他结点的指针树的表示6非树表示示例不是树，因为它没有一个根结点不是树，因为其中的一个结点有两个前趋结点不是树，因为它是不相交的两棵树的集合。它是森林树的表示7树的其它三种表示方法文氏图表示法用集合的嵌套即包含关系来表示广义表表示法用嵌套括号表示。根作为由子树森林组成的表的名字写在表的左边(A(B(E(K,L),F),C(G),D(H(M),I,J)))AEKLFBHMIJDGC树的表示

5、8凹入表示法类似于书的编目，即分成章节、小节，分别缩进表示ABEKLFCGDHMIJ树的表示9以如图所示的一棵树为范例结点（node）树中的的一个独立单元。它包括一个信息项和若干个指示其他树结点的位置信息。结点的信息项可包含一个关键字和其他的数据项。常用圆圈内的一个字母或数字表示该结点的信息项或关键字，并用来标识该结点，如结点A，结点B。根（root）树唯一无前趋（前件）的结点，如结点A。有时也用根结点标记整棵树，称其为树A。结点的度（degreeofnode）结点拥有的子树（或后件）数。如结点A的度为3，B的度为2，C的度为1，D的

6、度为3，E的度为2，F的度为0，等等。ACDBEFHJKLGIM树的基本术语树的度（degreeoftree）树内各结点度的最大值，如示例树的度为3。10叶结点（leafnode）或称终端结点，系指树中度为0（或没有后件）的结点。如K，L，G，M，I，J都是叶结点。双亲（parent）树中各结点的直接前趋称为该结点的双亲。如结点A是结点D的双亲，结点H是结点M的双亲等等。祖先（ancestor）从根结点到该结点所经分支上的所有结点。如结点K的祖先分别为A，B，E。分支结点（branchnode）亦称非终端结点，系指度不为0的结点，包括

7、根结点。孩子（children）一个树结点的直接后继均是该树结点的孩子。如结点B，C，D均是结点A的孩子。兄弟（Sibling）同一个双亲的孩子之间互称兄弟。如结点E，F互为兄弟，H，I，J互为兄弟，等等。树的基本术语ACDBEFHJKLGIM11子孙（descendant）以某结点为根的子树中的任一结点都称为该结点的子孙。比如，除根结点A之外的所有结点都是A的子孙树枝（branch）亦称为树边，系指连接两个结点的有向线段。一般是由父结点指向子结点。为了画图方便，一般将箭头方向省略树的深度（depthoftree）亦称树的高度，系指树

8、中各结点层次的最大值。如树A的深度为4。堂兄弟（brother-in-law）其双亲在同一层的结点。如结点E，G和H均为堂兄弟。结点的层次（levelofnode）结点所位于的层数（以根结点为第一层）。如结