数据结构学习——树形结构之递归遍历二叉树
时间：2022-09-05 03:00:00
目录
一. 二叉树是什么？
二. 二叉树分类
2.完全二叉树
2.2、满二叉树
2.三、扩大二叉树
2.四、平衡二叉树
三. 二叉树的应用场景
四. 遍历方式
五. 为什么要研究遍历？
六. 前序遍历
七. 中序遍历
八. 后序遍历
九. 数据结构专栏
一. 什么是二叉树
二叉树是每个结点最多有两个子树的树结构。子树通常被称为左子树和右子树。
二. 二叉树分类
2.完全二叉树
- 若设二叉树的高度为h，除第 h 层外，其他层 (1～h-1) 结点数达到最大数，h层有叶结点，叶结点从左到右依次排列，这是完全二叉树。
- 一维数组可作为完全二叉树的存储结构，堆排序中使用的数据结构为完全二叉树。
2.2、满二叉树
- 国际标准的定义是，除叶结点外，每个结点都有左右结点的二叉树
- 国内定义是：除叶结点外，每个结点都有左右叶，叶结点在底部。显然，根据这个定义，上面的二叉树并不是满的二叉树。
2.三、扩大二叉树
- 扩展二叉树是对现有二叉树的扩展，扩展后的二叉树节点变成度数为2的分支节点。也就是说，如果原节点的度数为2，则不变，度数为1，则增加一个分支，度数为0的叶节点增加两个分支。
2.四、平衡二叉树
- 左右两个子树的绝对值不超过1，是一棵空树或它的任何节点
三. 二叉树的应用场景
- 普通的二叉树很难成真实的应用场景，但由于其简单，常用于学习和研究，平衡二叉树更实用。它在快速匹配、搜索等方面很常见。
- 常用的树有：AVL树，红黑树，B 树、Trie(字典)树。
1、AVL树: 与其他数据结构相比，最早的平衡二叉树之一。windows应用于过程地址空间的管理AVL树。
2、红黑树: 平衡二叉树广泛应用于C 的STL中。如map和set都是红黑树做的。Linux文件管理。
3、B/B 树: 用于磁盘文件组织 数据索引和数据库索引。
4、Trie树(字典树)： 自动机、M数据库索引。
四. 遍历方式
- 前序遍历：root -> left -> right
- 中序遍历：left -> root -> right
- 后序遍历：left ->right -> root
- 已知的后序遍历和中序遍历可以确定前序遍历(即唯一可以确定的二叉树)。
- 已知的前序遍历和中序遍历可以确定后序遍历(即唯一可以确定的二叉树)。
五. 为什么要研究遍历？
当我们介绍数组和链表时，为什么不专注于他们的遍历呢？
二叉树的遍历有什么特别之处？
遍历本身就是计算机程序中的线性操作。因此，同样具有线性结构的数组或链表很容易遍历。另一方面，二叉树是典型的非线性数据结构，需要将非线性相关节点转换为线性序列，以不同的方式传播，传播的序列顺序也不同。
那么，二叉树些遍历呢？
从节点之间的位置关系来看，二叉树的遍历分为三种。
- 前序遍历。
- 中序遍历。
- 后序遍历。
六. 前序遍历
前序遍历（DLR，lchild,data,rchild），它是一种二叉树遍历，又称先根遍历、先序遍历、前序周游。你可以记得做根。先访问根结点，然后遍历左子树，最后遍历右子树。
前序遍历先访问根结点，再遍历左子树，最后遍历右子树。遍历左右子树时，仍先访问 根点，然后遍历左子树，最后遍历右子树。
若 如果二叉树是空的，返回将结束，否则：
(1)访问根结点。
（2）前序遍历左子树 。
(3)前序遍历右子树 。
需要注意的是:左遍历子树时仍然采用前序遍历方法。
如图所示:
前序遍历结果：ABDECF
其实在遍历二叉树的时候有三次遍历， 比如前序遍历：A->B->D->D(D左子节点并返回到D)->D(D右子节点并返回到D)->B->E->E(左)->E(右)->->B->A->C->F->F(左)->F(右)->C->C(右)，可以用递归的方式，递归的输出当前节点，然后递归的输出左子节点，最后递归的输出右子节点。直接看代码更能理解：
package test0910;
public class Test {
public static void main(String[] args) {
TreeNode[] node = new TreeNode[10];// 以数组形式生成一棵完全二叉树
for (int i = 0; i < 10; i++) {
node[i] = new TreeNode(i);
}
for (int i = 0; i < 10; i++) {
if (i * 2 + 1 < 10)
node[i].left = node[i * 2 + 1];
if (i * 2 + 2 < 10)
node[i].right = node[i * 2 + 2];
}
preOrderRe(node[0]);
}
public static void preOrderRe(TreeNode biTree) {
if (biTree == null)
return;
else {
System.out.print(biTree.value + " ");
preOrderRe(biTree.left);
preOrderRe(biTree.right);
}
}
}
//节点结构
class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.value = value;
}
}七. 中序遍历
中序遍历（LDR）是 二叉树遍历的一种，也叫做 中根遍历、中序周游。在二叉树中，先左后根再右。巧记：左根右。
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树
若 二叉树为空则结束返回，
否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树
如图所示：
中序遍历结果：DBEAFC
public class Test {
public static void main(String[] args) {
TreeNode[] node = new TreeNode[10];// 以数组形式生成一棵完全二叉树
for (int i = 0; i < 10; i++) {
node[i] = new TreeNode(i);
}
for (int i = 0; i < 10; i++) {
if (i * 2 + 1 < 10)
node[i].left = node[i * 2 + 1];
if (i * 2 + 2 < 10)
node[i].right = node[i * 2 + 2];
}
midOrderRe(node[0]);
}
public static void midOrderRe(TreeNode biTree) {
// 中序遍历递归实现
if (biTree == null)
return;
else {
midOrderRe(biTree.left);
System.out.print(biTree.value + " ");
midOrderRe(biTree.right);
}
}
}
// 节点结构
class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.value = value;
}
}八. 后序遍历
后序遍历（LRD）是 二叉树遍历的一种，也叫做 后根遍历、后序周游，可记做左右根。后序遍历有 递归算法和非递归算法两种。在二叉树中，先左后右再根。巧记：左右根。
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：
若 二叉树为空则结束返回，
否则：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根结点
如图所示:
后序遍历结果：DEBFCA
public class Test {
public static void main(String[] args) {
// 以数组形式生成一棵完全二叉树
TreeNode[] node = new TreeNode[10];
for (int i = 0; i < 10; i++) {
node[i] = new TreeNode(i);
}
for (int i = 0; i < 10; i++) {
if (i * 2 + 1 < 10)
node[i].left = node[i * 2 + 1];
if (i * 2 + 2 < 10)
node[i].right = node[i * 2 + 2];
}
postOrderRe(node[0]);
}
public static void postOrderRe(TreeNode biTree) {
// 后序遍历递归实现
if (biTree == null) {
return;
} else {
postOrderRe(biTree.left);
postOrderRe(biTree.right);
System.out.print(biTree.value + " ");
}
}
}
//节点结构
class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.value = value;
}
}九. 数据结构专栏
后文有介绍二叉树以及非递归遍历二叉树的内容，有兴趣的朋友可以去看看：树形结构之非递归遍历二叉树
