鲁达 树的设计初衷与操作时间复杂度
- 树这种数据结构的出现主要是对链表数据结构的优化，链表数据结构是线性结构，操作一般需要O(N)的时间复杂度，树是链表的变形，即链表的每个节点包含一个节点，而树的节点可以包含多个节点，如二叉树为根节点，左节点，右节点三个节点组成一个大节点，所以相对链表来说，相同的节点个数由于这种大节点的存在，故长度变小了，每次可以获取更多个子节点的信息，操作时间复杂度也减小了，如二叉树一般为O(logN)，多路搜索树则节点更大，故路径更短，操作时间复杂度更小。其实就是一种空间换时间的设计。
- 不只是计算机领域采用这种思路来优化，生活领域也是，如加法和乘法，其实乘法都可以通过加法来替代，但是使用乘法相对加法表示更加简单，如10个一相加，如果加法则需要写出1+1+…+1，而乘法只需要10*1。只需要让人类知道这个符号的含义即可。
算法设计
- 除了优化时间复杂度外，树的每个节点可以根据设计意图来存放不同的数据，并且可以进一步根据根节点，子树的区别来进一步设计，如二叉树如果用于处理算术表达式，则左右节点可以存放操作数，根节点存放操作符；用于排序则左节点存放最小的数据，根节点其次，右节点存放最大的。
二叉树
- 定义：每个节点包含至多两个节点，这两个节点分别称为左节点和右节点，如下：
- 树的每个节点可以
- 数据排序：如果树节点存放数值
1. 先序遍历
- 概念：先遍历根节点，再遍历左节点，最后遍历右节点。
- 根节点 -> 左子树 -> 右子树
递归实现
循环实现
- 结合栈（后进先出）来实现：根先入栈，然后开始循环遍历：根节点出栈，先右子树入栈，然后是左子树入栈，则在出栈的时候，左子树先出栈，右子树后出栈，实现：root -> left -> right。以下中序和后序设计思路类似。
2. 中序遍历
- 概念：先遍历左节点，再遍历根节点，最后遍历右节点。
- 左子树 -> 根节点 -> 右子树
递归实现
循环实现
- 由于中序遍历是：left -> root -> right，故可能会出现子树的root重复入栈来保存栈中：right -> root -> left的顺序，故需要记录root是否处理过了，处理过了则第二次出栈时直接出栈即可，不需要再处理左右子树，避免死循环。
3. 后序遍历
- 概念：先遍历左节点，再遍历右节点，最后遍历根节点。
- 左子树 -> 右子树 -> 根节点
递归实现
循环实现
- 思路与中序遍历类似。
4. 层次遍历
- 从根节点开始，逐层从左到右遍历每一层的节点。