二叉树的一些性质

二叉树

二叉树的性质

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

种类

满二叉树

高为h，有\(2^h-1\)个节点

完全二叉树

二叉查找树

\(\rm{left < root < right}\) ， 没有相等的节点

二叉平衡树

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

二叉查找树