------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7.28 树与图
node
结点的度: 子树的数量
树的度：最大结点的度
叶子结点：度为0的结点
分支结点：度不为0的结点
树的高度：最大层数（1开始或者0开始）
父亲表示法： tree[i]表示i的父节点
孩子表示法：
二叉树：
性质1：二叉树的第k层上，最多有2^(k-1)个结点
性质2：二叉树的前k层最多一共有2^k-1个结点
等比数列求和公式： a1(1-q^n)/(1-q)
拓展：三叉树的前k层最多一共有(3^k-1)/2
性质3：n0 = n2 + 1, n0表示度为0的结点(叶子节点)
点的关系：n = n0+n1+n2; （总的结点数量）
边的关系：n-1 = 2n2 + n1
合并推导：n0 + n1 + n2 = 2n2 + n1 +1 =>性质3
* 满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树
性质4：
具有n个结点的完全二叉树的深度是floor(log(n))+1;
性质5：
完全二叉树中结点编号为i的父节点是i/2，其左孩子为2i, 右孩子为2i+1
二叉树的遍历：
1.先序遍历：根左右
2.中序遍历：左根右
3.后序遍历：左右根
无向完全图: n*(n-1)/2 条边
有向完全图: n*(n-1) 条边
稀疏图：点多边少
稠密图：点少边多
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7.25初赛知识点
一、进制转换
1. K进制转换十进制：
2. 十进制转K进制：
3. 两个小特殊
二、前中后缀表达式
单目运算符： i++, --i, !0, ~
双目运算符： &&
三目运算符： (a>b)?(a):(b)
1. 中缀转后缀
三、原码， 反码 ， 补码
任何数字在计算机中的存储形式都是{补码}
1: 1001
正数的原码、反码、补码全部相同
原码：真值码
反码：符号位不变，其余位取反
补码: 反码+1
（-1）（int/32bit）
原码：1000 0000 0000 0000 0000 0000 0000 0001
反码：1111 1111 1111 1111 1111 1111 1111 1110
补码：1111 1111 1111 1111 1111 1111 1111 1111
-13：
原码：1000 ... 1101
反码：1111 ... 0010
补码：1111 ... 0011
逻辑运算符
逻辑与 &&
逻辑或 ||
逻辑非 !
位运算符：
1.按位与: &
2.按位或: |
3.按位左移: <<
左移x位：将原来的数放大2^(x)倍
4.按位右移: >>
右移x位：将原来的数缩小2^(x)倍
5.按位异或: ^
6.按位取反: ~
* 按位与、 按位或
转换为二进制之后进行计算， &表示必须两个同时成立， |表示只要成立一个
* 按位异或:
可以理解为不带进位的加法或者减法
* 按位取反: ~
int a = 6;
cout << (~a) << endl; //-7
cout << (~9) << endl;
cout << (~10) << endl;
cout << (~(-6)) << endl; //5
取反公式：~n = -(n+1)
四、排列组合
排列与顺序有关， 组合与顺序无关
1. 特殊优先
分步乘法，分类加法
2. 捆绑和插空
全排列的情况
3. 排除法
4. 隔板法
7.24 二分答案
7.23 二分查找
