树

树是n个结点的有限集，n=0时成为空树。

在任何一棵非空树种应该满足：

  1. 有且仅有一个特定的成为根的结点’
  2. 当 n > 1 时，其余结点可分为m个互不相交的有限集 ，其中每个集合本身又是一颗树，并且成为根的子树

树的特点：

  1. 树根节点没有前驱，除了根节点的所有结点有且只有一个前驱。
  2. 树中所有结点都可以由0个或者多个后驱。

树中一个结点的孩子个数称为该节点的度，树中结点的最大度数称为树的度。

树中的路径是从上向下的，同一双亲的两个孩子之间不存在路径。

树的性质

  1. 树的结点数n等于所有结点的度数之和加1
  2. 度为m的树中第 i 层上至多有 个结点
  3. 高度为h的m叉树至多有个结点
  4. 度为m、具有n个结点的树的最小高度h为
  5. 度为m、具有n个结点的树的最大高度h为

错题

  1. 树的路径长度是从树根到每个结点的路径长度的总和
  2. 设树中度 的结点数分别为 ，树的结点总数为n，则n=分支数+1

二叉树

二叉树是一种特殊的树形结构，，其特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。

度为2的树至少有3个结点，二叉树可以为空

满二叉树

一棵高度为h的树，且具有 个结点的二叉树成为满二叉树

完全二叉树

高度为h，有n个结点的二叉树，当且仅当每个结点都与高度为h的满二叉树中编号为 1~n 的结点一一对应

  1. 若 则 i 为分支结点否则为叶子节点
  2. 若n为奇数，每个分支节点都有左孩子和右孩子

性质

  1. 非空二叉树上的叶结点数等于度为2结点数+1，
  2. 非空二叉树的第 k 层至多有 个结点
  3. 高度为h的二叉树至多有 个结点
  4. 结点 i 所在的深度为
  5. 有n个结点的完全二叉树高度为 或者

二叉树的根节点不被任何结点指向

二叉树的遍历和线索二叉树

已知中序序列，再给出 后序序列、先序序列、层序序列 中的任何一种都可以唯一确定一棵二叉树

1
2
3
4
5
6
typedef struct ThreadNode{
    int data;
    struct ThreadNode* lchild,rchild;
    int ltag,rtag;
    // 如果ltag==0，则lchild指向的是左孩子，否则为前驱
}ThreadNode,*ThreadTree;

  1. 二叉树有两个结点m,n，若m是n的祖先，则使用后序遍历可以找到从m到n的路径

  2. 线索二叉树是一种物理结构，二叉树是逻辑结构

  3. 二叉树在线索化之后，还是不能解决后序线索二叉树中求后序后继的问题
  4. 后序线索树的遍历仍然需要栈的支持

树和森林

  1. 双亲表示法
  2. 孩子表示法
  3. 孩子兄弟表示法

树转成二叉树

每个结点的做指针指向它的第一个孩子，右指针指向它在树中相邻右兄弟

森林转成二叉树

先把森林中的每棵树都转成二叉树，然后把第二棵树根是做第一棵树根的右兄弟。

树 森林 二叉树
先根遍历 先序遍历 先序遍历
后根遍历 中序遍历 中序遍历

将森林转换成二叉树，森林中叶节点的个数为二叉树中左孩子为空的结点个数。

哈夫曼树和哈夫曼编码

哈夫曼编码加权平均长度为 （结点权值x路径长）/ 结点权值之和

并查集

并查集优化之后其深度不超过 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const int N=1005;
int pre[N];
int rank[N];
void init(int n){
    for(int i=0;i<n;i++)
    {
        pre[i]=i;
        rank[i]=1;
        
    }
}

int find(int x){
    if(pre[x]==x) return x;
    return find(pre[x]);
}

//优化版本
int find(int x){
    if(pre[x]==x) return ;
    pre[x]=find(pre[x]);
    return pre[x];
}

bool isSame(int x,int y){
    return find(x)==find(y);
}

bool join(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return false;
    if (rank[x]>rank[y]) pre[y]=x;
    else{
        if(rank[x]==rank[y]) rank[y]++;
        pre[x]=y;
    }
    return true;
}

prim算法正确性

贪心选择性质：不失一般性，有无向图G，令其起始节点为V1，找到与V1相连的最小的边，节点为Va，连接两个节点的边为e1，现证明e1包含在最优解中。令G’为一颗最小生成树，如果包括e1，则该结论成立，若不包括e1，则将e1加入G’中，将形成一个环，在这个环中每个节点的度为2，删掉该环中最大的一条边e2，获得新的生成树G’’。由于w(e1)<w(e2)，G’’就为最小生成树。

最优子结构：不失一般性，令起始节点为V1，最小生成树G’中与V1相连的且权值最小的边为Va，边为e1，将V1和Va合并为一个新节点Vx，对于在图中与V1,Va同时相连的边，保留权值最小的与Vx相连，得到子图G1，现证明图G的最小生成树G’包含了图G1的最小生成树G1’。假设图G1的最小生成树不属于G’，而是其他生成树G1’’，把Vx拆分成V1和Va，得到一颗图G的生成树G’’。于是W(G’’)=W(G1’’)+w(e1)<W(G1’’)+w(e1)=W(G’)，这不符合G’是最小生成树，矛盾，所以假设结果不成立。综上所述，算法的正确性得证.

kruskal算法证明

由算法生成的树T1 和最小生成树T2，令e是选择T过程中的第一条不位于T2中的边。将e添加到T2就得到了一个环C，在C中由一条边e2不属于T1，考虑T2+e-e2为T3

由于选择e和e2的时候（T2包含了T中e之前的边和e2），算法选择了e，说明w（e）<w(e2)，此时T3比T2最小生成树权值还小，矛盾了。