一、树型结构
在认识二叉树之前，我们可以先了解一下什么叫树。
数据结构中的树，和我们生活中的树是有类似之处的。其实是一种非线性的数据结构。它具有以下的特点：每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。
如图，就是一个普通的树形结构，这里我们一定要区分开树和图的区别。
二、二叉树
1、概念：
二叉树也是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
二叉树的特点：每个节点的度最多是2。二叉树的子树是有左右之分的，并且次序不可以颠倒。
上图就是一个二叉树的结构。
2、特殊的二叉树
满二叉树：一个二叉树，每一层的节点树都达到了最大值，就是满二叉树。如果一个树有k层，节点数就为（2^k）-1个。
完全二叉树：是由满二叉树引出来的，相比于满二叉树，完全二叉树是树结构的右小角缺少节点。
3、二叉树的遍历：
(下面的遍历结果都以这棵树为例)
（1）先序遍历：
先访问（打印）根节点，递归遍历左子树，递归遍历右子树。
遍历过程：
-
访问A（打印），再遍历左子树B。
- B作为D的根节点，访问B（打印），遍历B的左子树D。
- D作为H的根节点，访问D（打印），遍历D的左子树H。
- H的左右子树都为空，访问H（打印）。此时B的左子树遍历完，接着遍历B的右子树E
- B作为E的根节点，访问E（打印），遍历E的左子树（空），遍历E的右子树I。
- I的左右子树都为空，访问I(打印)，此时B的右子树遍历完，A的左子树遍历完。
-
A作为C的根节点，访问C（打印），遍历C的左子树
- C作为F的根节点，访问F（打印），F的左右子树都为空。此时C的左子树遍历完，接着遍历C的右子树G
- C作为G的根节点，访问G（打印），G的左右子树都为空。
最后遍历的结果就为：A B D H E I C F G
（2）、中序遍历
先递归遍历左子树，访问根节点，再递归遍历右子树。
遍历过程：
-
遍历根节点A，A的左子树为B。B的左子树为D。D的左子树为H。H的左子树为空，访问（打印）H。
-
H的根节点为D，访问（打印）D。D的右子树为空。
-
D的根节点为B，访问（打印）B。
- B的右子树为E。E的左子树为空，访问（打印）E。
- E的右子树为I，访问（打印）I。
-
A的左子树访问完，访问（打印）A。
-
A的右子树为C，C的左子树又为F。
- F的左右子树都为空，访问（打印）F。
- C的左子树访问完，访问（打印）C。
- C的右子树为G，访问（打印）G。
最后的遍历结果为：H D B E I A F C G
（3）、后序遍历
先递归遍历左子树，再递归遍历右子树，访问根节点。
递归过程：
- A的左子树为B，B的左子树为D，D的左子树为H，H的左右子树为空，访问（打印）H。
- D的左子树访问完，右子树为空，访问（打印）D。
- B的左子树访问完，B的右子树为E。E的左子树为空，右子树为I，访问（打印）I。
- E的左右子树访问完，访问（打印）E。
- B的左右子树访问完，访问（打印）B。
- A的左子树访问完，A的右子树为C，C的左子树为F，F的左右子树为空，访问（打印）F。
- C的左子树访问完，右子树为G，访问（打印）G。
- C的左右子树访问完，访问（打印）C。
- A的左右子树访问完，访问(打印)A。
最后的遍历结果为：H D I E B F G C A
（4）、层序遍历：
一层一层向下遍历，每一层从左到右访问。
遍历结果为：A B C D E F G H I
4、二叉树的表示：
class Node{
public char val;//值
public Node left;//左子树
public Node right;//右子树
}
三、代码实现（递归）：
1、先序遍历：
public static void prevOrder(Node root) {
if(root == null) {
return;
}
System.out.print(root.val + " ");
prevOrder(root.left);
prevOrder(root.right);
}
2、中序遍历
public static void inOrder(Node root) {
if(root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
3、后续遍历：
public static void postOrder(Node root) {
if(root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val+ " ");
}
4、层序遍历：
public void levelOrder(TreeNode root) {
Queue queue = new linkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
System.out.print(cur.val + " ");
if(cur.left != null) {
queue.offer(root.left);
}
if(cur.right != null) {
queue.offer(root.right);
}
}
}
