(此文为王道数据结构学习笔记，只供个人后续复习使用，若有错误，还望指出我改正，谢谢）
KMP：
next数组的计算方式：
引入前缀后缀概念：
前缀：串中包含第一个字符但不包含最后一个字符的串 即 1—n 号元素（1<n<m，m为串长）
后缀：串中包含最后一个字符但不包含第一个字符的串 即 n—m?号元素（1<n<m，m为串长）
公共前后缀：元素完全相等的两个前后缀
当模式串指针 j 移动到模式串上 p 号元素时发现到不匹配时，看到 j 之前的部分模式串，找到这部分模式串的最大公共前后缀串S，串S的长度为 n ，则新的 j 应指向 n + 1 号位模式串，记录该 p 号元素的 next 数组值为 n+1 ，按照这种方法，即可求得next数组。
于是 next 的计算方法为：p 号元素的 next 值等于其之前元素的公共前后缀长度加一。
next [ 0?] =0；next [ 1?] =1；例如
| 序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 模式串 | a | b | a | a | b | b | b | a | b |
| next [ j ]? | 0 | 1 | 1 | 2 | 2 | 3 | 1 | 1 | 2 |
使用kmp算法后，主串的扫描指针 i 无需回溯，只需要模式串指针 j 进行回溯，按照next数组回溯。当 j = 0 时，代表需要将模式串直接向后滑动，故应当让 i 也加一。
next数组计算算法实现
void get_next(SString T,int next[]){
int i=1,j=0;
next[1]=0;
while(i<T.length){
if(j==0||T.ch[i]==T.ch[j]){
++i;
++j;
next[i]=j;
}
else
j=next[j];
}
}KMP算法存在的问题：（nextval数组）
当发现元素不匹配时，利用next数组，可让 j 跳至next数组告知的位置，但如果此时，即将跳转到的那个位置的元素，和当前元素相等（则当前元素一定也不和主串指针 i 指向的元素匹配），则这个跳转多此一举。所有可以计算 nextval 数组，让两个相同元素且存在跳转关系的 nextval 值相等，都等于第一个出现时的 nextval 值即可，可以省略跳完又跳的浪费行动。例如
| 序号j | 1 | 2 | 3 | 4 | 5 | 6 |
| 模式串 | G | O | O | G | L | E |
| next | 0 | 1 | 1 | 1 | 2 | 1 |
| nextval | 0 | 1 | 1 | 0 | 2 | 1 |
则引入计算nextval数组的算法：先计算next数组，然后再根据next数组开始遍历，若发现某个元素与跳转后的元素相等，则将其next值修改成该元素的next值，完成遍历后，next数组更新成为了nextval数组。
nextval数组计算算法实现：
void get_nextval(SString T,int next[]){
int i=1,j=0;
next[1]=0;
while(i<T.length){
if(j==0||T.ch[i]==T.ch[j]){
++i;
++j;
next[i]=j;
}
else
j=next[j];
}
//前半部分和next一样，先算出next数组
for(int k=2;k<=T.length;k++){
if(T.ch[next[j]]==T.ch[j])
nextval[j]=nextval[next[j]];//如果跳转的元素相等，改变nextval
else
nextval[j]=next[j];//否则，nextval等于原next值
}树
逻辑结构：
一个根结点有几个边，连着分支结点。
空树：无结点；非空树：有且仅有一个根结点（也可以有其他结点）子树：分支产生的树
根结点没有前驱有后继，分支结点有前驱后继，叶子结点无后继有前驱；每个结点至多有一个前驱
术语：
结点之间关系：
祖先结点：向上回溯到根结点的每一个结点都为祖先结点
子孙结点：自己的分支及分支的分支所连着的结点都为子孙结点
双亲结点：父结点。自己的前驱
兄弟结点：同一个父结点下的结点
堂兄弟结点：同一层的结点（即它们的父结点为兄弟结点或堂兄弟结点）
结点的层次（深度）：从根结点开始一层一层往下数
结点的高度：从最下层的叶子节点开始一层一层往上数
树的高度（深度）：一共有多少层
结点的度：该结点一共有几个分支（孩子）
树的度：各节点度的最大值
有序树：子树从左到右有顺序
无序树：子树从左到右无顺序
森林：多个不相交的树组成
树的性质：
结点数等于总度数+1（根结点）
树的度为m：有且至少有一个结点度为m，不能没有结点
?m 叉树：每个结点的度最多为m，可以没有结点
度为m的树，第 i 层最多有??个结点。
高度为 h 的 m 叉树，最多有个结点
高度为 h 的 m 叉树，最少有 h 个结点
高度为 h 的度为 m 的树，最少有 h+m+1 个结点（即前全是只有一个分支，最后有m个叶子）
具有 n 个结点的 m 叉树，最小高度为【LOGm（n（m-1）+1）】向上取整
?
二叉树
每个结点最多两个孩子，
