树的计算题技巧：
1.在二叉树的第i层至多有2^i - 1 个节点
2.深度为k的二叉树至多有2^k-1 个节点
3. 设度为0,1,2节点为n0，n1,n2，总结点是n，则n0=n2+1;（根据4.5条推出）
4.n0 + n1 + n2 = n
5.n = 分支线数 + 1 = 2*n2 + 1*n1 + 0*n0（分支数就是两点的连线的数目，n个点两两连线有n-1条线）
满二叉树：最后一层节点有2^i - 1个节点，就是满了
完全二叉树：对满二叉树进行编号与对完全二叉树进行编号顺序位置完全一样，唯一不同就是完全二叉树最后一层叶子节点比满少
1.节点计算题
一个4叉树，度为4的结点个数为6，度为3的节点个数是10，度为2的节点个数是5，叶子节点个数为()虽然不是二叉树，但是延伸的道理都是一样的。
设度为1的节点个数为x,度为0的节点为y。该树的分叉数为4*6+3*10+2*5+x*1
又因为节点数=分叉数+1;
节点数:6+10+5+x+y= 4*6+3*10+2*5+x*1+1
解得：y=44
某棵完全二叉树上有699个节点，则该二叉树的叶子节点数为（）完全二叉树，n1的个数在1和0之前选择我们用分支数的公式
2*n2 + n1 + 1 = 699，1移过去后698是复数，很明显如果n1是1，那么n2肯定不是整数，所以n1只能是0，然后算出n2是349；然后根据公式2,n2 = n0 - 1算出n0 = 350
一个包含 n 个节点的四叉树，每个节点都有四个指向孩子节点的指针，这 4n 个指针中有多少个空指针？
答案：n个节点不管多少叉树，肯定有n-1条连线（边），意味着有n-1个非空指针
所以空指针就是4n-（n-1） = 3n+1
2.哈弗曼树
官方定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是（）。构造方法是每次取最小的两个数， 合并成一个数， 然后循环这种做法， 直到只剩一个点为止。构造的树是
30
17 13
8 9 6 7
4 5
3.森林与树
树转二叉树
森林转二叉树
设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是( )答案：M2+M3
图的计算技巧
1.n个顶点的无向完全图有n*(n-1)/2条边
2.n个顶点的有向完全图有n*(n-1)条边
3.无向图边数是各顶点度数和一半
完全图：任意两个顶点都存在边
1.图与边
设某强连通图中有 n 个顶点，则该强连通图中 至少有（）条边。
答案：n条
1)强连通图的定义：
在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。
2）分析：
可知当n个节点的图构成一个环，任意两点之间存在着回路，于是最小的边数为n;最大边数为n(n-1);
2.拓扑
在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。
A.G中有弧<Vi，Vj>
B.G中有一条从Vi到Vj的路径
C.G中没有弧<Vi,Vj>
D.G中有一条从Vj到Vi的路径答案:D
拓扑排序定义：将有向图中的顶点以线性方式进行排序。即对于任何连接自顶点u到顶点v的有向边u->v，在最后的排序结果中，顶点u总是在顶点v的前面。
比如下面的图的拓扑结构是V1，V3，V4，V6，V2，V5，V7
不是所有图都能被拓扑，拓扑排序的充要条件就是它是一个有向无环图