一、二叉树理论基础
学习：
1. 从二叉树是否包含数值进行分类：
-
无数值：完全二叉树和满二叉树
-
有数值的：二叉搜索树和平衡二叉搜索树(AVL，Adelson-Velsky and Landis)。其中二叉搜索树指数值按照从小到大的顺序是左子树<根结点<右子树，平衡指的是左右子树高度差不超过1
2. 二叉树存储方式
- 链式存储：通常采用的存储方式
- 顺序存储：根结点的下标为i，则左孩子为2i+1，右孩子为2i+2
3. 二叉树遍历
-
深度优先遍历----发展出前序遍历、中序遍历、后序遍历，其中方位指的是根结点遍历的顺序
-
广度优先遍历----层序遍历
二、对三种遍历顺序的两种遍历方式
题目链接：
1. 递归遍历
递归调用的主函数是一样的，具体递归过程中递归参数和返回值、终止条件是一样的，只有单次循环内容的根结点、左孩子、右孩子的顺序不一样
- 前序遍历：根左右
- 中序遍历：左根右
- 后序遍历：左右根
2. 分别迭代遍历
用栈来存储结点，其中只有前序遍历是使得遍历结点和取值结点保持一致的，后序结点可以是前序结点调整顺序后遍历结果的翻转
- 前序遍历：弹出栈顶结点并取值，然后若存在则将右孩子和左孩子依次入栈
- 中序遍历：需要指针，指向要取值的结点。指针非空时，入栈然后指向当前结点的左孩子；指针为空时，返回根结点即栈顶元素，取值然后指向当前结点的右孩子
- 后序遍历：与前序类似，弹出栈顶结点并取值，然后若存在则将左孩子和右孩子依次入栈，最后翻转
3. 统一迭代遍历
核心思路为添加标记符，即标记这个结点的左右孩子若存在已入栈，这样解决了中序和后序重复添加结点的问题
五、学习总结
-
时间：4h
-
掌握了递归三步法
-
掌握了迭代遍历，以及统一迭代遍历
- 分别迭代会产生当前元素和取值元素不一致且重复添加孩子结点的问题
- 统一迭代对当前结点进行标记，当遇到标记时，才取值并出栈，使得两类元素变成一致，并且不会重复添加