数据结构的重点知识点
第七章（14大知识点）
P154 1、树的定义是递归的定义
P1562、树的基本术语：
（1）结点的度、树的度
（2）分支结点、叶子结点
（3）孩子结点、双亲结点、兄弟结点
（4）树的高度、森林
P162-1633、什么叫满二叉树、什么叫完全二叉树P163 7.2.2 第三行4、总结点数＝n0+n1+n2
第四行总的分支数＝n1+2n2
第六行总的分支数=总结点数-1
二叉树的链式存储
P1685、链二叉树的结点结构体
typedef struct node
{ ElemType data;
struct node *lchild;
struct node *rchild;
} BTNode;
P1716、二叉树查找结点算法代码
P172 7、二叉树求高度算法代码
P173-174 8、二叉树三种递归遍历算法（超重要！）
P1859、已知先序+中序序列->唯一确定一棵二叉树
P18710、已知后序+中序序列->唯一确定一棵二叉树
P189第一段中文11、由n个结点组成的二叉树一共有2n个指针域，但只有n-1个有效指针，浪费了剩下的n+1个指针
我们把这n+1个指针充分利用为线索
P189第二、三段12、线索：①某一个结点没有左孩子或没有右孩子②且没有左孩子的使它指向它的前驱，没有右孩子的使它指向它的后继
P19013、一棵二叉树中的绝对有空指针域（因为叶子结点没孩子），但已经给线索化的二叉树一定没有空指针域（因为上面空的指针值就是线索）
P19414、构造哈夫曼树的关键：每一次选取最小的两个值组成二叉树，并且把刚算出来的值跟原来题目提供的值再一起比较选取最小的两个值
第八章（8大知识点）
P205-2061、基本术语
（1）端点、邻接点
（2）顶点的度、顶点的入度、顶点的出度
（3）n个顶点组成的无向完全图有C n2条边
n个顶点组成的有向完全图有A n2条边
（4）简单回路或简单环
（5）连通图、连通分量
（6）权、网
图的存储结构
P208的代码2、邻接矩阵①无向图时，是对称矩阵②有边时为1或权值③无边时为0
P209的代码3、邻接表①先写头结点，也叫顶点结点②再写所有与头结点相邻接的邻接点
P2114、深度遍历：①是递归的算法
②访问当前顶点的任意一个没有被访问的邻接点
P2135、广度遍历：访问当前顶点的所有没有被访问的邻接点P2236、最小生成树(只能是无向图)：以最少的边连接连通图中所以顶点
①有且仅有n-1条边②包有所有n个顶点
现实应用：在n个村庄里怎么样选择边架构通信网络，使成本最低
P225普里姆算法：U代表已找到的顶点，V代表剩下的顶点目的：每次由V里加一个顶点到U，使n个顶点全部加
入到U里
条件：每加一个顶点时，满足是代价最小的边
P227克鲁斯卡尔算法：
目的：每一次添加一条边，直到n-1条边全部添加进来
条件：添加边时，满足是权值最小且不形成回路
P2317、最短路径：(既可以有向图，也可无向图)经过的边数最少
现实应用：由一个城市去另一个城市，怎么走法最短
P232狄克斯特拉算法：用来求一个顶点到其余各顶点的最短路径
P2408、拓扑排序：(只能有向图)
现实应用：工程规划(例如学了C++，才可以学数据结构)
P241第2-4行
写拓扑序列的技巧：①写出一个入度为0的顶点
②从有向图中，删除写的顶点且删除该顶点发出的边
第九章（8大知识点）
P2501、顺序查找：算法代码
P2512、二分查找（重点）熟练掌握算法代码，只针对有序表
n
二分查找的时间复杂度：log
2
P2543、索引查找①分块有序②块内无序
P2564、二叉排序树的定义：①任一结点比左孩子大，且比右孩子小②任一棵子树本身也是一棵二叉排序树
对二叉排序树使用中序遍历得到的序列一定要递增有序
P258最后一行5、二叉排序树的插入：①每插入一个都要从根结点开始往下比较②每插入一个都要作为叶子结点
P262最后一段6、二叉排序树的删除：分三种情况
①删除的结点为叶子结点
②删除结点只有单分支
③删除结点有双分支
一、前驱替换法：找删除结点的左孩子的最右端（即为最大结
点）
二、后继替换法：找删除结点的右孩子的最左端（即为最小结点）
P277第一行7、哈希函数：自变量x通过函数y＝f(x)求出的y 为地址
f为哈希函数，y为哈希地址
P277第七行8、同义词：不同的x，得出同一个y
P2789、哈希冲突函数：由于出现同义词，要解决同义词
求哈希表的方法：
P280例题9.9哈希函数（除留余数法）+哈希冲突函数（线性探查法）
P281例题9.10哈希函数（除留余数法）+哈希冲突函数（拉链法）。