二叉树的一些性质

二叉树

二叉树的性质

• 第i层，节点最多$2^{i-1}$个
• 深度为k的二叉树，最多有$2^k-1$个 节点
• 二叉树有n个节点，高度至少为${\log }_2(n+1)$
• $n_0=n_2+1$，叶子节点和度为2的节点的关系

种类

满二叉树

高为h，有$2^h-1$个节点

完全二叉树

二叉查找树

$\mathrm{l}\mathrm{e}\mathrm{f}\mathrm{t}<\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}<\mathrm{r}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}$ ， 没有相等的节点

二叉平衡树

左右子树的高度差的绝对值小于等于1

二叉查找树