二叉树

• 二叉树：是一个有限的结点集合，该集合或者为空，或者由一个根结点及其两颗互不相交的左右二叉子树组成。

非空二叉树的特点

1. 非空二叉树只有一个根结点
2. 每一个结点最多有两颗子树，分别称左子树和右子树

二叉树的五种基本形态

1. 空二叉树
2. 只有一个结点的二叉树
3. 只有左子树的二叉树
4. 只有右子树的二叉树
5. 左右子树双全的二叉树

特殊二叉树

• 满二叉树：除最后一层外，每一层上的节点数均达到最大值。
• 完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点