二叉树的定义及其基本性质

二叉树（Binary Tree, BT）是一种特殊的树型结构，每个结点最多有两个子节点。

5种基本形态

• 空二叉树
• 仅有根结点的二叉树
• 右子树为空的二叉树
• 左右子树均非空的二叉树

• 左子树为空的二叉树

  性质

• 在二叉树的第 i 层上最多有个结点

• 深度为 depth 的二叉树，至多有个结点
• 对任意一棵二叉树，如果叶子结点数为 ，度为 2 的结点数为，一定满足

证明：，算两次

• 具有 n 个结点的完全二叉树，深度为。注意，根的深度，有的定义是0，有的定义是1
• 对于一棵具有 n 个结点的完全二叉树，对于任意一个结点，编号为 i

if (i > 1) 父结点编号 i / 2
if (2 i > n) 没有左儿子 else 左儿子编号为 2 i
if (2 i + 1 > n) 没有右儿子 else 右儿子编号为 2 i + 1

Catalan数

• 具有 n 个结点的不同形态的二叉树，有多少棵 ```cpp 一棵具有 n(n > 1) 个结点的二叉树

可以看成是, 由 一个根结点， 一棵具有 i 个结点的左子树， 一棵具有 n - i - 1个结点的右子树组成

i 的取值范围[0, n - 1] ```