天津理工大学——数据结构期末总结2new

《天津理工大学——数据结构期末总结2new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构期末总结2Capter3Tree&Binarytree(树和二叉树)一棵树是一些节点（node）的集合。这个集合可以是空集；若非空，则一棵树由称作根（root）的节点r以及0个或多个非空的（子）树（subtrees）T1，T2„„，TK组成，这些子树中每一颗的根都被来自根r的一条有向的边（edge）所连接。每一颗子树的根叫做根r的孩子（child），而r是每一颗子树的双亲（parent）。节点的度（degree）：节点的度就是其子树的数量。度为0的节点称为叶子（leaf）。树的深度（depth）：树的高度（层数）。二叉树定义：二叉树是一棵树，其中每个节点都不能有多于

2、两个的孩子。另有完全二叉树（CompleteBT）和满二叉树（FullBT），具体定义，自行看课件。考点提示：选择题，考概念。树的性质：性质1：树中的节点数等于所有节点的度数加1。i-1性质2：度为k的树中第i层上最多有K个节点（i≥1）。h性质3：深度为h的k叉树最多有K-1/K-1个节点。性质4：具有n个节点的k叉树的最小高度为logk(n(k-1)+1)向上取整。对于二叉树，求最小深度的计算公式为：log2(2n+1)。二叉树的性质：i-1性质1：一颗非空二叉树的第i层上最多有2个节点（i≥1）。k-1性质2：一颗深度为k的二叉树中，最多具有2个节点。性质3：对于一颗

3、非空的二叉树，如果叶子节点数为n0，度为2的节点数为n2，则有n0=n2+1。性质4：具有n个节点的完全二叉树的深度k为log2n+1。考点提示：多为利用性质算节点数的选择题。二叉树的遍历（traverse）重点哦亲~~：前序遍历（Preordertraversal）、中序遍历（Preordertraversal）、后序遍历（Postordertraversal）。熟练掌握三种遍历，并且灵活运用！具体见课件CH3第24~28页，中文书122页。考点提示：已知二叉树，求三种遍历。可能题型：选择题，简答题。树、森林与二叉树的转换：树转换为二叉树、森林转换为二叉树、二叉树转换

4、为树和森林。中文书135~136页，课件CH3第61~67页。具体题目看作业。哈弗曼树（Huffmantree）：1.带权路径长度（WeightedPathLength,WPL）：了解并学会计算。2.构造哈弗曼树：掌握构造哈弗曼树的方法，并计算构造出的哈弗曼树的WPL。3.哈弗曼编码：什么是哈弗曼编码，如何求出哈弗曼编码。具体参见：课件CH3第38~49页。考点提示：哈弗曼树的实际应用，即使用哈弗曼树编码。可能题型：选择题。简答题。Capter4Graphs（图）一个图G=（V,E）由顶点（vertex）集V和边（edge）集组成。每一条边就是一个点对（v，w），其中，v，

5、w∈V。图的一些概念：1.有向图（directedgraph）和无向图（undirectedgraph）：在图中，若用箭头标明了边是有方向的，则称这样的图为有向图，否则称为无向图。2.完全图（completegraph）：具有n个顶点，n(n-1)/2条边的无向图，称为完全无向图。具有n个顶点，n(n-1)条弧的有向图，称为完全有向图。完全无向图和完全有向图统称为完全图。3.稠密图与稀疏图。4.权（weight）：与边有关的数据信息称为权。5.子图（subgraph）。6.邻接点。7.度、入度、出度：在无向图中，一个顶点依附的边的数目称为该顶点的度。在有向图中，指向顶点的弧

6、的数目称为该顶点的入度。从顶点出发的弧的数目称为该顶点的出度，有向图的某个顶点的入度和出度之和称为该顶点的度。8.路径（path）、回路。9.连通图、连通分量。10.强连通图、强连通分量。11.生成树。中文书第148~151页。邻接矩阵表示法：在图的邻接矩阵（adjacentmatrix）表示中，除用一个一维数组存放顶点本身的信息外，还用一个n×n的矩阵表示各个顶点之间的邻接关系。即若(I,j)或属于边集E，则矩阵中第i行、第j列元素值为1，否则为0。邻接表表示法：邻接表（adjacencylist）是图的一种顺序存储与链式存储相结合的存储方法。就是把每个顶点发出

7、的边链接在一个单链表中，这样的单链表叫边链表。边链表中的每一个节点代表一条边，叫做边节点。边节点中的数据代表该顶点通过这条边所邻接的那个顶点。每个顶点对应一个边链表，每个边链表都有一个头节点，所有头节点组成一个一维数组，称这样的表示法为邻接表表示法。中文书第152~160页。课件CH4第13~24页。以上两种方法必须熟练掌握！考点提示：给出有向图或无向图，画出邻接矩阵与邻接表。可能题型：简答题。图的遍历（GraphTraversals）：深度优先遍历（depth-firstsearch）广度优先遍历（breadth