二叉树的基本性质

两种二叉树

完全二叉树：如果有n层，前n-1层全满，第n层从左向右排列。

满二叉树：每个结点都是二度结点

在二叉树的第 i 层上至多有 $2^{i-1}$ 个结点

深度为 k 的二叉树上至多含 $2^k-1$ 个结点

对于任意一棵二叉树，若它含有 $n_0$ 个叶子结点、$n_2$ 个度为 2 的结点，则必存在关系式 $n_0 = n_2 + 1$

具有n个结点的完全二叉树的深度为 $\lfloor log_2n\rfloor+1$ 。

对于完全二叉树：
按照从上到下从左到右编号1 - n，对于任意一个编号为 i 的结点：

找双亲：i = 1，是二叉树的根，无双亲；否则，编号为 $\lfloor i/2\rfloor$ 的结点为其双亲结点。

找左孩子：2i>n，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点。

找右孩子：2i+1>n，则该结点无右孩子，否则，编号为2i+1的结点为其右孩子结点。

根结点—先序遍历左子树—先序遍历右子树

中序遍历左子树—根结点—中序遍历右子树

后序遍历左子树—后续遍历右子树—根结点

结点的带权路径长度：从该结点到树根之间的路径长度与该结点上权值的乘积。

树的带权路径长度：树中所有叶子结点的带权路径长度之和。

带权路径长度最小的二叉树称为最优二叉树或哈夫曼树。