严蔚敏数据结构复习整理完整版

1、本文格式为Word版，下载可任意编辑 严蔚敏数据结构复习整理完整版 1.繁杂性分析 对各种操作的时间繁杂性的分析。 主要是链表，树，排序等简单一些的分析。 分析的时候，从简单的入手，学会方法。 后续的各种豆可能让你分析时间繁杂度。 线性链表（顺序表和单链表） 链表循环链表 双向链表 2.线性结构队列（循环队列） 栈 链表主要操作：找某一个元素，插入一个（在哪个位置增加），删除一个（在哪个位置删除）。栈：查找，插入（位置固定），删除（位置固定） 队列：查找，插入（位置固定），删除（位置固定） 顺序表（可以视为一个数组） 单链表： （删除） （插入） 倒置： （查找） 循环链表 双向链表 栈： （

2、插入删除查找） 队列 （插入删除查找） 循环队列的实现，并不是像上面的图那样，实现了一个循环的样子。 3.二叉树 基本概念 二叉树是每个节点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特别情形。 二叉树是每个结点最多有两个子树的有序树。寻常根的子树被称作“左子树（left subtree）和“右子树（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。 二叉树不是树的一种特别情形，尽管其与树有大量相像之处，但树和二叉树有两个主

3、要区别： 1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2； 2. 树的结点无左、右之分，而二叉树的结点有左、右之分。 二叉树是递归定义的，其结点有左右子树之分，规律上二叉树有五种基本形态： (1)空二叉树如图(a)； (2)只有一个根结点的二叉树如图(b)； (3)只有左子树如图(c)； (4)只有右子树如图(d)； (5)完全二叉树如图(e) 注意：尽管二叉树与树有大量相像之处，但二叉树不是树的特别情形 性质 (1) 在非空二叉树中，第i层的结点总数不超过 , i=1； (2) 深度为h的二叉树最多有2h-1个结点(h=1)，最少有h个结点； (3) 对于任意一棵二叉树，假如其

4、叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1； (4) 具有n个结点的完全二叉树的深度为 (5)有N个结点的完全二叉树各结点假如用顺序方式存储，则结点之间有如下关系： 若I为结点编号则假如I1，则其父结点的编号为I/2； 假如2*IN，则无左儿子； 假如2*I+1N，则无右儿子。 (6)给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。 （7）设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i 存储结构 顺序存储表示 二叉树可以用数组或线性表来存储，而且假如这是满二叉树，这种方法不会浪费空间。

5、用这种紧凑排列，假如一个结点的索引为i，它的子结点能在索引2i+1和2i+2找到，并且它的父节点（假如有）能在索引floor(i-1)/2)找到（假设根节点的索引为0）。这种方法更有利于紧凑存储和更好的访问的局部性，特别是在前序遍历中。然而，它需要连续的存储空间，这样在存储高度为h的n个结点组成的一般普通树时将会浪费好多空间。一种最极坏的状况下假如深度为h的二叉树每个节点只有右孩子需要占用2的h次幂减1，而实际却只有h个结点，空间的浪费太大，这是顺序存储结构的一大缺点。 /* 二叉树的顺序存储表示 */ #define MAX_TREE_SIZE 100 /* 二叉树的最大节点数 */ typ

6、edef TElemType SqBiTreeMAX_TREE_SIZE; /* 0号单元存储根节点 */ typedef struct int level,order; /* 节点的层，本层序号(按满二叉树计算) */ position; 二叉链表存储表示 /* 二叉樹的二叉鏈表存儲表示 */ typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /* 左右孩子指針 */ BiTNode,*BiTree; 遍历算法 二叉树的遍历三种方式，如下： （1）前序遍历（DLR），首先访问根结点，然后遍历左子树，结

7、果遍历右子树。简记根-左-右。 （2）中序遍历（LDR），首先遍历左子树，然后访问根结点，结果遍历右子树。简记左-根-右。 （3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，结果访问根结点。简记左-右-根。 例1：如上图所示的二叉树，若按前序遍历，则其输出序列为。若按中序遍历，则其输出序列为。若按后序遍历，则其输出序列为。 前序：根A，A的左子树B，B的左子树没有，看右子树，为D，所以A-B-D。再来看A的右子树，根C，左子树E，E的左子树F，E的右子树G，G的左子树为H，没有了终止。连起来为C-E-F-G-H,结果结果为ABDCEFGH 中序：先访问根的左子树,B没有左子树，其有右子

8、树D，D无左子树，下面访问树的根A，连起来是BDA。 再访问根的右子树，C的左子树的左子树是F，F的根E，E的右子树有左子树是H，再从H出发找到G，到此C的左子树终止，找到根C，无右子树，终止。连起来是FEHGC, 中序结果连起来是BDAFEHGC 后序：B无左子树，有右子树D，再到根B。再看右子树，最下面的左子树是F，其根的右子树的左子树是H，再到H的根G，再到G的根E，E的根C 无右子树了，直接到C，这时再和B找它们其有的根A，所以连起来是DBFHGECA 深度优先遍历 在深度优先中，我们希望从根结点访问最远的结点。和图的深度优先探寻不同的是，不需记住访问过的每一个结点，由于树中不会有环。

9、 广度优先遍历 和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。 完全二叉树，满二叉树 1.满二叉树：一棵深度为k，且有个节 点称之为满二叉树 2.完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k 的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树 4.树 基本概念 树（tree）是包含n（n0）个结点的有穷集，其中： （1）每个元素称为结点（node）； （2）有一个特定的结点被称为根结点或树根（root）。 （3）除根结点之外的其余数据元素被分为m（m0）个互不相交的集合T1，T2，Tm-1，其中每一个集合Ti（1=0）棵互不相交的树的集合称为森

10、林； 存储 父节点表示法 /* 树节点的定义 */#define MAX_TREE_SIZE 100typedef struct TElemType data; int parent; /* 父节点位置域 */ PTNode;typedef struct PTNode nodesMAX_TREE_SIZE; int n; /* 节点数 */ PTree; 孩子链表表示法 /*树的孩子链表存储表示*/typedef struct CTNode / 孩子节点 int child; struct CTNode *next; *ChildPtr;typedef struct ElemType data； / 节点的数据元素 ChildPtr firstchild； / 孩子链表头指针 CTBox;typedef struct CTBox nodesMAX_TREE_SIZE； int n, r； / 节点数和根节点的位置 CTree; 5.森林 6.森林、树与二叉树的转换 将树转换为二叉树 树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。依照这种关系很自然地就能将树转换成相应的二叉树： 在所有兄弟结点之间加一连线； 对每个结点，除了保存与其长子的连线外，去掉该结点与其它孩子的连线。 注意： 由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。 2）将一个