Java中如何实现二叉树及其前中后序遍历算法？

本文共计2090个文字，预计阅读时间需要9分钟。

树的概态及结构概态：树是一种非线性数据结构，由n（n≥0）个有限节点组成，具有层次关系的集合。称为树是因为它看起来像一棵倒挂的树，也说是根在上，叶在下的结构。

树的概念及结构 树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根在上，而叶在下的。

有一个特殊的结点，称为根结点，根节点没有前驱结点。除根节点外，其余结点被分成m(m > 0)个互不相交的集合T1、T2、…… 、Tm，其中每一个集合Ti(1 <= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，但可以有0个或多个后继。

由此可知，树是递归定义的。

---

下面是一个简单的树。

图中根节点就是没有父结点的结点，叶子结点就是没有子节点的结点。

---

还要注意：树的子树是不相交的；除了根节点外，每个结点有且仅有一个父结点。

下面介绍一些与树相关的概念（以上面的树为例）：

（1）结点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6，即B、C、D、E、F、G。

（2）叶结点：度为0的节点称为叶结点；如上图：B、C、H、I…等为叶结点。

（3）双亲结点或父结点：若一个节点含有子结点，则这个结点称为其子结点的父结点；如上图：A是B的父结点。