树

树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树。

特点

• 每个节点有零个或多个子节点
• 没有父节点的节点称为根节点
• 每一个非根节点只有一个父节点
• 除了根节点外，每个子节点可以分为多个不相交的子树

二叉树是一种特殊的树，特点如下：

• 每个节点最多有两个子节点，节点的度最大为2
• 左子树和柚子树是有顺序的，次序不能颠倒
• 即便某节点只有一个子树，也要区分左右子树

二叉树添加、删除元素都很快，并且在查询元素也有很多算法优化。二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。
扩展： 二叉树有很多扩展的数据结构，包括平衡二叉树、红黑树、B+树等，这些数据结构在二叉树的基础上衍生了很多的功能，在实际应用中广泛用到，例如mysql的数据库索引结构用的就是B+树，还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大，但算法上比较复杂，想学习的话还是需要花时间去深入的。

四种遍历思想

前序遍历

根结点 —-> 左子树 —-> 右子树

中序遍历

左子树—-> 根结点 —-> 右子树

后序遍历

左子树 —-> 右子树 —-> 根结点

层次遍历

只需按层次遍历即可