1.二叉树的性质

1. 性质1：在二叉树的第i层上至多有2^i-1个结点(i>=1)，至少由1个结点
2. 性质2：深度为h的二叉树至多有2^h-1个结点（满二叉树）
3. 性质3：一棵深度为h的二叉树，至少有h个结点
4. 性质4：对任意一棵二叉树，如果叶节点有n0个，度为2的结点有n2个，则一定满足：n0=n2+1
5. 性质5：对任意一棵完全二叉树，如果叶节点有n0个（度为0），度为1的结点有n1个，度为2的结点有n2个，总结点数有n个，则n=n0+n1+n2。因为n1=1,n2=n0-1（性质4），所以n=n0+n1+n2=n0+1+(n0-1)=n0+n0，即n=n0+n0
6. 性质6：具有n个结点的完全二叉树的深度为floor[log2n]+1
7. 性质7：对于一棵有n个结点的完全二叉树，对任意一个结点（编号为i）:
8. 如果i=1，则结点i无父结点（根结点）
9. 如果i>1，则结点i父结点编号为floor（i/2）
10. 如果2i>n，则结点i无子结点（叶子结点）；否则左孩子编号为2i
11. 如果2i+1>n，则结点i无右孩子，否则右孩子编号为2i+1

2.二叉树的存储

1. 儿子表示法

对于每个结点，存储该结点的左右孩子结点的编号。（开结构体struct）

2. 数组存储法（~~一维数组~~二维数组）

int ch[N][2];//ch[x][0]表示x的左孩子，ch[x][1]表示x的右孩子

3. 完全二叉树的数组表示法

使用一维数组进行存储 - 数组表示法（一维数组~~二维数组~~） - 对于完全二叉树，用一组地址连续的储存单元依次自上而下、自左而右存储完全二叉树上的结点元素。 - 对于一般二叉树，将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应位置中。 - 字符串表示法（与数组表示法差不多） 用字符串string表示。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com