3月12日是国家重大节日：植树节。记得小时候和老师一起种树。现在我正在工作。虽然没种过树，但是学过很多树结构，比如二叉树，B+树，红黑树。每次面试都要问，恰逢植树节。本来想讲解B树的，但是发现必须先了解二叉树才能更好的讲解B树，所以我先告诉大家什么是二叉树，我会在更新B树以下文章。用大白话解释一下二叉树。比如现在有一个数组，里面存放了很多用户的名字。需要从这个数组中找到指定的用户名。最快的方法是什么？我们会想到二分查找，虽然这种方法很快，但是要达到最快，有一个条件：数组是有序的。如果我们在插入用户名的时候可以直接对用户名进行排序，那么最终的结构就是一个有序的结构。于是有人设计了一种数据结构：二叉搜索树，也叫二叉树。如下图所示：这是一个二叉树结构。二叉树以上面的例子为基础，假设Herry在最上面，下面有Alice、Mike、Ivy、Tom，从左到右，从上到下，最后的顺序是：Alice->Herry->Ivy->Mike->Tom确实是按字母顺序排列的。有四个术语需要解释：节点、左节点、右节点和根节点。其中，每个红球算作一个节点，该节点左下方相连的节点称为左节点，右下方相连的节点称为右节点。例如，Alice被称为Herry节点的左节点，Mike被称为Herry的右节点。只会有一个根节点，它属于顶级节点。上图中的Herry是根节点。对于这些节点中的每一个，左子节点的值都比它小，右子节点的值都比它大。例如，Alice=0)个节点的有限集，它要么是空集（称为空二叉树），要么由一个根节点和两个互不相交的节点组成，分别由左子树和右子树组成，称为根节点。二叉树有5种形状空二叉树。只有一个根节点的二叉树。只有左子树和右子树。完全二叉树。节点的度定义：节点拥有的子树的个数称为该节点的度。我们看下图，一目了然。mark例如节点B的度数为2，节点E的度数为1。树的度数为所有节点度数的最大值，为2。节点层次结构如下图所示：根节点为第一层，依此类推。二叉树的特点是每个节点最多有一个子树，所以二叉树中没有度数大于2的节点。左右子树是有序的，不能随意颠倒顺序。即使一个节点只有一棵子树，也需要区分它是左子树还是右子树。二叉树遍历二叉树遍历：从二叉树的根节点开始，按照一定的顺序访问二叉树中的所有节点，使得每个节点只能被访问一次。二叉树的访问顺序可以分为四种：前序遍历。中序遍历。后续遍历。层序遍历。前序遍历：通俗地说，就是从二叉树的根节点开始，第一次到达该节点就输出节点数据，按照先左后右的方向进行访问。中序遍历：从二叉树的根节点开始，第二次到达该节点时输出节点数据，按先左后右的方向访问。后序遍历：从二叉树的根节点开始，第三次到达该节点时输出节点数据，按先左后右的方向访问。层级遍历：就是按照树的层级从上到下遍历二叉树。按照前序遍历标记的结果就是BADCE。中序遍历的结果是ABCDE。后续遍历的结果就是ACEDB。按照层级遍历的结果就是BADCE。巨人的肩膀：《算法图解》本文转载自微信公众号“悟空聊天架构”，可通过以下二维码关注。转载本文请联系悟空聊天架构公众号。
