1、1. 复杂性分析对各种操作的时间复杂性的分析。 主要是链表，树，排序等简单一些的分析。分析的时候，从简单的入手，学会方法。后续的各种豆可能让你分析时间复杂度。 线性链表（顺序表和单链表） 链表 循环链表 双向链表2. 线性结构 队列（循环队列） 栈链表主要操作：找某一个元素，插入一个（在哪个位置增加），删除一个（在哪个位置删除）。栈：查找，插入（位置固定），删除（位置固定）队列：查找，插入（位置固定），删除（位置固定）顺序表（可以视为一个数组）单链表：（删除）（插入）倒置：（查找）循环链表双向链表栈：（插入删除查找）队列（插入删除查找）循环队列的实现，并不是像上面的图那样，实现了一个循环的样子
2、。3. 二叉树基本概念二叉树是每个节点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；2. 树的结点无左、右之分，而二
3、叉树的结点有左、右之分。二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：(1)空二叉树如图(a)；(2)只有一个根结点的二叉树如图(b)；(3)只有左子树如图(c)；(4)只有右子树如图(d)；(5)完全二叉树如图(e)注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形性质(1) 在非空二叉树中，第i层的结点总数不超过, i=1；(2) 深度为h的二叉树最多有2h-1个结点(h=1)，最少有h个结点；(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；(4) 具有n个结点的完全二叉树的深度为(5)有N个结点的完全二叉树
4、各结点如果用顺序方式存储，则结点之间有如下关系：若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 存储结构顺序存储表示二叉树可以用数组或线性表来存储，而且如果这是满二叉树，这种方法不会浪费空间。用这种紧凑排列，如果一个结点的索引为i，它的子结点能在索引2i+1和2i+2找到，并且它的父节点（如果有）能在索引floor(i-1)/2)找到（
5、假设根节点的索引为0）。这种方法更有利于紧凑存储和更好的访问的局部性，特别是在前序遍历中。然而，它需要连续的存储空间，这样在存储高度为h的n个结点组成的一般普通树时将会浪费很多空间。一种最极坏的情况下如果深度为h的二叉树每个节点只有右孩子需要占用2的h次幂减1，而实际却只有h个结点，空间的浪费太大，这是顺序存储结构的一大缺点。 /* 二叉树的顺序存储表示 */ #define MAX_TREE_SIZE 100 /* 二叉树的最大节点数 */ typedef TElemType SqBiTreeMAX_TREE_SIZE; /* 0号单元存储根节点 */ typedef struct int
6、level,order; /* 节点的层，本层序号(按满二叉树计算) */ position;二叉链表存储表示/* 二叉樹的二叉鏈表存儲表示 */ typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /* 左右孩子指針 */ BiTNode,*BiTree;遍历算法二叉树的遍历三种方式，如下：（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。 （3）后序遍历（LRD），首先遍历
7、左子树，然后遍历右子树，最后访问根结点。简记左-右-根。 例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没有左子树，其有右子树D，D无左子树，下面访问树的根A，连起来是BDA。再访问根的右子树，C的左子树的左子树是F，F的根E，E的右子树有左子树是H，再从H出发找到G，到此C的左
8、子树结束，找到根C，无右子树，结束。连起来是FEHGC, 中序结果连起来是BDAFEHGC后序：B无左子树，有右子树D，再到根B。再看右子树，最下面的左子树是F，其根的右子树的左子树是H，再到H的根G，再到G的根E，E的根C无右子树了，直接到C，这时再和B找它们其有的根A，所以连起来是DBFHGECA 深度优先遍历在深度优先中，我们希望从根结点访问最远的结点。和图的深度优先搜索不同的是，不需记住访问过的每一个结点，因为树中不会有环。广度优先遍历和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。完全二叉树，满二叉树1. 满二叉树：一棵深度为k，且有个节点称之为满二叉树2. 完全二叉树：
9、深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树4. 树基本概念树（tree）是包含n（n0）个结点的有穷集，其中：（1）每个元素称为结点（node）；（2）有一个特定的结点被称为根结点或树根（root）。（3）除根结点之外的其余数据元素被分为m（m0）个互不相交的集合T1，T2，Tm-1，其中每一个集合Ti（1=i=0）棵互不相交的树的集合称为森林；存储父节点表示法/* 树节点的定义 */#define MAX_TREE_SIZE 100typedef struct TElemType data; int parent;
10、/* 父节点位置域 */ 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
11、, r； / 节点数和根节点的位置 CTree;5.森林6.森林、树与二叉树的转换将树转换为二叉树 树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：在所有兄弟结点之间加一连线；对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。注意： 由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。2）将一个森林转换为二叉树具体方法是： 将森林中的每棵树变为二叉树 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。二叉树到树、森林的转换把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。图二元组的定义图G是一个有序二元组(V,E)，其中V称为顶集(Vertices Set)，E称为边集(Edges set)，E与V不相交。它们亦可写成V(G)和E(G)。E的元素都是二元组，用(x,y)表示，其中x,yV。三元组的定义图G是指一个三元组(V,E,I)，其中V称为顶集，E称为边集，E与V不相交；I称为关联函数，I将E中的每一个元素映射到。如果e被映射到(u,v)，那么称边e连接顶点u,v，而u,v则称作e的端
