二叉树Java实现前序遍历、中序遍历、后序遍历、层次遍历获取叶子节点

对数据结构中的二叉树了解不多，今天就趁着这个时间整理一下

从很多实际问题中抽象出来的数据结构往往是二叉树的形式。 即使是一般的树也可以很容易地转化为二叉树，而且二叉树的存储结构和算法都比较简单，所以二叉树显得尤为重要。

二叉树（BinaryTree）是n（n≥0）个节点的有限集，它要么是空集（n=0），要么由一个根节点和两棵不相交的树组成，称为根的左边一棵二叉树由一个子树和一个右子树组成。

这个定义是递归的。 由于左右子树也是二叉树，所以子树也可以是空树。 下图显示了五种不同的二叉树基本形式。

其中(a)是一棵空树，(b)是一棵只有一个节点的二叉树，(c)是一棵只有左子树右子树为空的二叉树，(d)只有右子树和左子树。 tree是一棵空二叉树，(e)是一棵左右子树都非空的二叉树。 这里需要注意的是，二叉树的左子树和右子树是严格区分的，不能随意颠倒。 图（c）和图（d）是两种不同的二叉树。

二叉树遍历

对于二叉树来说，最重要也是最基本的操作就是遍历。

遍历二叉树是指按照一定的顺序访问二叉树中的每个节点。 所谓访问节点是指对节点进行各种操作的简称。 例如，查询一个节点的数据字段的内容，或者输出它的值，或者找出节点的位置，或者对节点进行其他操作。 遍历二叉树的过程本质上就是将二叉树的节点进行线性排列的过程。 假设遍历二叉树时访问节点的操作是输出节点data域的值，那么遍历的结果就是一个线性序列。

从二叉树的递归定义来看遍历以太坊节点，非空二叉树由三个基本部分组成：根节点和左右子树。 因此，在任何给定节点，可以按某种顺序执行三个操作：

(1) 访问节点本身(N)，

(2)遍历节点的左子树(L)，

(3)遍历节点的右子树(R)。

以上三个操作有六个执行顺序：

NLR、LNR、LRN、NRL、RNL、RLN。

注意：

前三阶与后三阶对称，所以只讨论先左后右的前三阶。

由于访问的节点一定是某个子树的根，所以N(Node)、L(Left subtree)和R(Right subtree)可以解释为根、根的左子树、根的右子树. NLR、LNR 和 LRN 也分别称为首根遍历、中根遍历和后根遍历。

二叉树的Java实现

首先创建一个如下图所示的二叉树，然后对二叉树进行遍历操作（遍历操作的实现分为递归和非递归实现），同时也提供了获取父节点等一些方法，获取左孩子，右孩子等

特征：

(1) 每个节点最多有两棵子树，也可以没有子树或者只有一棵子树；

(2) 左子树和右子树是有序的，不能任意颠倒顺序；

(3) 即使树中只有一颗子树，也要区分是左子树还是右子树；

(2)满二叉树：在一棵二叉树中，如果所有分支节点都有左子树和右子树，并且所有的叶子都在同一层，这样的二叉树称为满二叉树； 如图：

(3)完全二叉树：对一棵有n个节点的二叉树按顺序编号，如果编号为i的节点与二叉树中相同深度的完全二叉树中编号为i的节点处于同一位置，则这一个二叉树树称为完全二叉树； 或者可以这样理解：在一棵二叉树中，除了最后一层，如果其余层都满了，而最后一层要么满了，要么右边连续少了几个节点，那么这个树称为完全二叉树；

所以我们可以这样判断完全二叉树：也就是看树的示意图，按照完全二叉树的结构，默默地对每个节点逐层编号。 如果数字有空隙，说明不是完全二叉树，否则就是；

另一个经典问题：

问题1.求二叉树的最大距离；

编写程序求二叉树中最远的两个节点之间的距离

如下所示：

二、分析与解决

对于任意一个节点，以该节点为根，假设根有k个子节点，则最远的两个节点U和V与根节点之间的路径存在两种关系。

1). 如果路径经过Root，那么U和V属于不同的子树，并且都是子树中距离根节点最远的节点，否则与它们的最远距离矛盾

2). 如果路径不经过Root，那么它们一定属于根的k颗子树中的一颗，同时也是这颗子树中相距最远的两个顶点

因此，该问题可以转化为一个字数的解决方案，可以使用动态规划来解决。

假设第K子树中距离最远的两个节点：Uk和Vk，距离定义为d(Uk,Vk)，则节点Uk或Vk为子树K到根节点Rk距离最远的节点。 不失一般性，我们设Uk为子树K中到根节点Rk距离最长的节点遍历以太坊节点，其到根节点的距离定义为d(Uk,R)。 取 d(Ui,R)(1