java数据结构_二叉树_5.3 （几道例题搞定二叉树的遍历）
2.4 二叉树的存储
二叉树的存储结构分为：顺序存储和类似于链表的链式存储。
在这里介绍链式存储
二叉树的链式存储是通过一个一个的结点引用起来的的，常见的表示方法有二叉（孩子表示法）和三叉（孩子双亲表示法）表示方法，如下：
//孩子表示法
class Node {
int val; //数据域
Node left; //左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; //右孩子的引用，常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {
int val; //数据域
Node left; //左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; //右孩子的引用，常常代表右孩子为根的整棵右子树
Node parent; //当前节点的根节点
}
孩子双亲表示法在后序的平衡树位置介绍，本文用孩子表示法来构建二叉树。
2.5 二叉树的基本操作
2.5.1 说明
在此先手动快速创建一棵简单的二叉树，用来学习基本相关操作，后续再回过头研究二叉树的真正创建方式。
public class BinaryTree {
static class TreeNode {
private char val;
private TreeNode left;
private TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public TreeNode root; //将来这个引用 指向的就是根结点
/**
* 创建二叉树的简单方法
*/
public TreeNode createTree() {
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
A.left = B;
B.left = D;
B.right = E;
E.right = H;
A.right = C;
C.left = F;
C.right = G;
return A;
}
}在IDEA中测试可以看到
实现的二叉树模拟图为：
注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式在后面会叙述。
回看二叉树的概念：二叉树是：
1. 空树
2. 非空：由根结点，根结点的左子树，根结点的右子树组成的。
从概念和模拟图中可以发现，二叉树的定义是递归式形成的。
2.5.2 二叉树的遍历
1. 前 中 后序遍历
遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所作的操作依赖于具体的应用问题（比如：打印结点内容，结点内容+1）。遍历是二叉树最重要的操作之一，是二叉树上进行其他运算的基础。
如果用N代表根结点，L代表根结点的左子树，R代表根结点的右子树，则根据根结点的先后次序有以下遍历方式：
NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。
LNR：中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。
LRN：后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点。
2. 层序遍历
层序遍历就是从二叉树的根出发，从上到下，自左至右的逐层逐个访问树的结点。
补充：
树是递归定义的，每一棵树的遍历 都是以同样的方式进行遍历的，前 中 后 序遍历走的路线的相同的，不过是访问根结点的顺序不同。
3. 如下图二叉树，给出该二叉树的三种遍历方式
前序（根左右）：A B D E H C F G
中序（左根右）：D B E H A F C G
后序（左右根）：D H E B F G C A
4. 选择题
1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为()
A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA
解：根据题意是按层次输出的序列为ABCDEFGH，可以画出二叉树模拟图为：
前序序列的顺序是根左右：A B D H E C F G
答案为 A
2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树后序遍历的顺序为：
解：要根据两个顺序还原二叉树
先序遍历（根先后）：E F H I G J K
中序遍历（左根右）：H F I E J K G
因为先序遍历的顺序是根左右，则E为根，又因为中序遍历是根左右，所以中序遍历中，E左边的都是左子树，E右边的都是右子树，如图：
再看先序遍历E之后的结点是F，证明下一个根结点是F，在上图中H在F的左侧，即H是F的左子树，I是F的右子树
再看先序遍历F之后的结点H I 因为H和I在上图中，没有其他左子树，则继续看前序遍历I后面的元素G，即下一个根结点为G，在上图中，G没有右子树，只有J和K为左子树
再由前序遍历看G之后的元素是J，即下一个根结点为J，K在J的右边，则K为J的右子树
则上图为还原出来的二叉树模拟图，其后序遍历（左右根）：H I F K J G E
3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为()
A: adbce B: decab C: debac D: abcde
中序遍历（左根右）：b a d c e
后序遍历（左右根）：b d e c a
这道题和第二题有一点不同的是，这个是后序遍历和中序遍历，前序遍历是先根再左右，后序遍历是先左右后根，所以要找到根结点，就要从后序遍历的最后一个结点开始。
此题中后序遍历最后一个结点为a，则a为根结点，再在中序遍历中，看到b为a的左子树，dce为a的右子树
再看后序遍历在a前面的元素c，则c为下一个根结点，d为c的左子树，e为c的右子树
上图为二叉树的模拟图，前序遍历（根左右）：a b c d e
4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出(同一层从左到右)的序列为()
A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF
解：
后序（左右根）：A B C D E F
中序（左根右）：A B C D E F
后序遍历最后一个结点是F，F为根结点，中序遍历中 A B C D E均在F左侧，为F的左子树
同理向下模拟该二叉树最终为：
层次输出为 F E D C B A