二叉树 / 满二叉树 / 完全二叉树 / 二叉查找树

1. 二叉树
每个节点最多只有两个子节点，叫左孩子和右孩子。
它只限制“数量”，不限制“大小关系”。

例如：

A
/ \
B C
/
D

———

2. 满二叉树
除了叶子节点外，每个节点都有两个子节点。
也就是说，不会出现“只有一个孩子”的节点。

例如：

A
/ \
B C
/ \ / \
D E F G

这个就是满二叉树。

———

3. 完全二叉树
除了最后一层，前面每一层都满；
最后一层的节点必须从左到右连续排列，中间不能空。

例如：

A
/ \
B C
/ \ /
D E F

这是完全二叉树。
因为最后一层是从左往右排的。

但如果是这样：

A
/ \
B C
\ /
E F

就不是完全二叉树，因为最后一层不是从左到右连续的。

———

4. 二叉查找树（BST）
它首先是一棵二叉树，同时还必须满足大小规则：

- 左子树所有节点都比根小
- 右子树所有节点都比根大

例如：

8
/ \
3 10
/ \ \
1 6 14

这是二叉查找树。

———

一句话总结

- 二叉树：最多两个孩子
- 满二叉树：每个非叶子节点都有两个孩子
- 完全二叉树：按层从左到右排满
- 二叉查找树：左小右大

它们的关系是：

- 满二叉树、完全二叉树、二叉查找树，都属于二叉树
- 满二叉树不一定是二叉查找树
- 完全二叉树不一定是二叉查找树
- 二叉查找树也不一定是满二叉树或完全二叉树