在学习二叉树之前，我们需要先知道什么是树？
树
树这个数据结构其实很有意思，因为他就是一颗倒挂的树。肯定有很多人都玩过蚂蚁森林，种过梭梭树，数据结构中的树结构其实就很像梭梭树，就是这样这样
梭梭树
数据结构-树
是不是很像？？？
节点的概念
以上图的树为例，A节点是B、C节点的父节点，由于A节点没有父节点，所以A节点称为根节点；B、C节点同属于A节点，所以B、C节点之间的互称为兄弟节点。如果一个节点没有任何子节点，如图中的D、E、F、C，它们被称为叶子节点。
树高度、深度与层
这几个概念真的是很容易混淆的概念。
首先我们来说树的高度，我们描述一个物体有多高（比如一幢楼），都是从底部打量到顶部的（可能有人不是这样的？），节点的高度也是如此，我们描述某一节点的高度指的是该节点到叶子节点的最长路径（即连接的边数）。
然后我们再来说树的深度，同样参照生活，我们描述一个物体有多深是指我们从上往下打量的过程（比如这条河有多深、这个悬崖有多深），节点的深度同样如此，我们描述一个节点有多深，指的是该节点到根节点所经历的边数
最后就是层了，层很简单，就是节点的深度+1。
以上图为例（A、B、D三个节点）
节点的高度、深度与层
好了介绍完树的一些基本概念，我们一起来正式了解二叉树
二叉树
二叉树很好理解，即每个节点最多有两个子节点，分别为左子节点和右子节点。其中二叉树根据叶子节点的不同又从中定义了两种特殊的二叉树，分别为满二叉树和完全二叉树
满二叉树
满二叉树很好理解，就和它的名字一样，是满的，即叶子节点全在最后一层，且除叶子节点外，每个节点都有左右两个子节点，这种二叉树就叫满二叉树。图例：
满二叉树
完全二叉树
完全二叉树理解起来会困难一点，完全二叉树是指叶子节点在最后两层，并且最后一层的叶子节点都靠左排列，除了最后一层，其他层的节点数都必须达到满个数，图例：
完全二叉树
二叉树的存储方式
链式存储
链式存储比较简单直观，很好理解，也是比较常用的一种存储方式，就是维护left和right两个指针分别指向左右两个子节点，通过这两个指针把整个树串起来。
链式存储
顺序存储
顺序存储会稍微复杂一点，我们把根节点的下标定为1（不定为0是因为1会方便下面的计算），则其左子节点的下标会是2，左右节点的下标会是3，如下图所示
顺序存储
通过推导可以知道，二叉树的任意节点的位置索引为n，其左子节点的位置索引为2n，右子节点的位置索引为2n+1，我们通过下标的计算就可以把整个树通过数组串起来了
二叉树的遍历
二叉树的遍历分为前序遍历、中序遍历和后续遍历。
前序遍历指的是对于任意节点而言，先访问该节点，再访问其左子树，最后访问其右子树。
中序遍历指的是对于任意节点而言，先访问该节点的左子树，再访问该节点，最后访问该节点的右子树。
后序遍历指的是对于任意节点而言，先访问该节点的左子树，再访问该节点的右子树，最后访问该节点。
你是否发现很明显的递归痕迹？
遍历的递归代码写起来很简单，就不具体写了。
网友评论