代码随想录 二叉树：理论基础

二叉树的种类

1. 满二叉树。只有度为0的根节点和度为2的其余节点。高度为k则节点数量位2^(k+1)-1
2. 完全二叉树。仅允许最底层的节点不完全填满，且最底层的节点必须从左至右依次连续填充
3. 二叉搜索树。有数值，是一个有序树。任意一个节点，其左子节点（如果有的话）小于该节点，右子节点（如果有的话0大于该节点
4. 平衡二叉搜索树

二叉树的存储方式

链式存储

使用指针实现，每个节点有指向左右子节点的指针。

数组存储

使用一个完美二叉树占位置，然后将所有节点按照层序遍历的顺序存储在一个数组中，则每个节点都对应唯一的数组索引。

父节点索引与子节点索引之间的“映射公式”：若某节点的索引为 i ，则该节点的左子节点索引为 2i+1 ，右子节点索引为 2i+2

这个索引起到了链表中指针的作用

二叉树的遍历方式

（1）深度优先遍历

• 前序遍历（递归法、迭代法、统一迭代法（空指针法和Boolean法））
• 中序遍历（递归法、迭代法、统一迭代法（空指针法和Boolean法））
• 后序遍历（递归法、迭代法、统一迭代法（空指针法和Boolean法））

（2）广度优先遍历

• 层序遍历（迭代法）