二叉树

简单地理解，满足以下两个条件的树就是二叉树：

• 本身是有序树；
• 树中包含的各个节点的度（儿子）不能超过 2，即只能是 0、1 或者 2；

1. 二叉树中，第 i 层最多有 2*i - 1 个结点。
2. 如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
3. 二叉树中，终端结点数（叶子结点数）为 n₀，度为 2 的结点数为 n₂，则 n₀=n₂+1

满二叉树
如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。图1即为满二叉树。

完全二叉树
如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

 

二叉树的四种遍历

四种遍历方式分别为：先序遍历、中序遍历、后序遍历、层序遍历。

 

前三行分别为先序，中序，后序

三种遍历转化主要是找根

先序的第一个是根，中序中间位置是根，后序根在最后

然后递归就好

下面放代码

二叉搜索树