1. 树形结构（了解）
1.1 概念
树是一种非线性的数据结构，它是由n(n>=0)个有限节点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一个倒挂的树，也就是说它是根朝上，而叶子朝下。它具有的特点：
- 有一个特殊的几点，称为根节点，根节点没有前驱节点
- 除根节点外，其余节点被分成m(m>0)个互不相交的集合 T1、T2、…、Tm，其中每一个集合Ti(1<=i<=m)又是一颗与类似的字数。每颗子树的根节点有且只有一个前驱，可以有0个或多个后继
- 树是递归定义的。
【注意】：树形结构中，子树间不能有交集，否则就不是树形结构
1.2 概念（重要）
节点的度：一个节点含有子树的个数称为该节点的度；如下图：A的度为2
树的度：一棵树中，所有的节点度的最大值称为树的度；如下图：树的度为3
叶子节点或终端节点：度为0的节点称为叶子节点；如下图：G、H、I、J、F节点为叶子节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如下图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如下图：B是A的孩子节点
根节点：一棵树中，没有双亲节点的节点；如下图：A
节点的层次：从根节点定义来，根为第1层，根的子节点为第2层，以此类推
树的高度：树中节点的最大层次；如下图：树的高度为4
树的以下概念只需了解，知道是什么意思即可：
非终端节点或分支节点：度不为0的节点；如下图：B、C、D、E节点为分支节点
兄弟节点：具有相同父节点的节点互称为兄弟节点；如下图：B、C是互为兄弟节点
堂兄弟节点：双亲在同一层的节点互为堂兄弟节点；如下图：D、E是互为堂兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如下图：A是所有节点的祖先
子孙：以某个节点为根的子树中任一节点都称为该节点的的子孙。
如下图：所有的接地那都是A的子孙森林：由m(m>=0)棵互不相交的树组成的集合称为森林
1.3 树的表示形式（了解）
树的结构相对线性表就比较复杂了，要存储不是起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法，孩子双亲表示法，孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法
class Node { int val; // 树中存储的数据 Node firstChild; // 第一个孩子引用 Node nextBrother;// 下一个兄弟引用 }
线性结构与树形结构的对比
| 线性结构 | 树形结构 |
| 第一个数据元素：无前驱 | 根节点：无双亲，唯一 |
| 最后一个数据元素：无后继 | 叶节点：无孩子，可以多个 |
| 中间元素：一个前驱，一个后继 | 中间节点：一个双亲多个孩子 |
1.4 树的应用
文件系统管理（目录和文件）
2. 二叉树
2.1 概念
二叉树是n(n>=0)个节点的有限集合，该集合或者空集（空二叉树），或者由一个根节点和两颗互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
从上图可以看出：
- 二叉树不存在度大于2的节点
- 二叉树的子树有左右之分，因此二叉树是有序树
总结：对于任意的二叉树都是由以下几种情况复合而成的
大自然中的二叉树：
2.2 特殊的二叉树
满二叉树：一颗二叉树，如果每层的节点数都达到最大值，则这课二叉树就是，满二叉树。也就是说，如果一颗二叉树的层数为K，且节点总数是 2K -1，则它就是满二叉树
完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有 n 个节点的二叉树，每个节点都与深度为 K 的满二叉树中编号从0至 n-1的节点（从上到下，从左到右，依次存放）——对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。 
2.3 二叉树的性质
若根节点的层数为1，则一颗非空二叉树的第 i 层上最多有 2i-1 （i > 0）个节点
若只有根节点的二叉树的深度为1，则深度为 k 的二叉树的最大节点数是2k - 1(k >= 0)
对任何一颗二叉树，如果其叶子节点个数为 n0，度为2的非叶子节点个数为n2，则有n0 = n2 + 1
具有 n 个节点的完全二叉树的深度 k 为long2(n+1)上取整
对于具有 n 个节点的完全二叉树，如果按照从上至下、从左至右的顺序对所有节点从0开始编号，则对于序号 i 的节点有：
若 i > 0，双亲序号：(i - 1) / 2；i = 0，i为根节点编号，无双亲节点
若 2i + 1 < n，左孩子序号：2i + 1，否则无左孩子
若 2i + 2 < n，右孩子序号：2i + 2，否则无右孩子
2.4 二叉树的存储
二叉树的存储结构分为：顺序存储和类似于链表的链式存储
二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方法有孩子表示法和孩子双亲表示法，具体如下：
// 孩子表示法 class Node { int val;// 数据域 Node left;// 左孩子的引用，常常代表左孩子为根的整棵左子树 Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树 } // 孩子双亲表示法 class Node { int val;// 数据域 Node left;// 左孩子的引用，常常代表左孩子为根的整棵左子树 Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树 Node parent; // 当前节点的根节点 }
3. 二叉树的基本操作
3.1 前置说明
在学习二叉树的基本操作前，需要先创建一颗二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树的结构掌握还不够深入，为了降低学习成本，此处手动创建一颗二叉树，快速进入二叉树的学习。
public class BinaryTree { // 节点类 static class TreeNode{ public char val; public TreeNode left; // 左节点 public TreeNode right; // 右节点 // 构造方法 public TreeNode(char val) { this.val = val; } } // 以穷举的方式 创建一颗二叉树 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; A.right = C; B.left = D; B.right = E; E.right = H; C.left = F; C.right = G; return A; // 返回根节点 } }
注意：上诉代码并不是创建二叉树的方式。
回顾一下二叉树的概念：
- 空树
- 非空：根节点，根节点的左子树、根节点的右子树组成的
从概念可以看出：二叉树的定义是递归式的，因此后续的基本操作中都是按照该概念实现的。
3.2 二叉树的遍历
学习二叉树的结构，最简单的方式就是遍历，所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加1)。 遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。
1. 前序遍历
前序遍历的顺序: 根节点-> 左子树 -> 右子树
遍历演示 :
代码 :
// 前序遍历 void preOrder(TreeNode root) { // 判断是否为空树 if (root == null) { return; } // 打印当前节点的值 System.out.print(root.val + " "); // 递归左子树 preOrder(root.left); // 递归右子树 preOrder(root.right); }
2. 中序遍历
中序遍历的顺序: 左子树 -> 根结点 -> 右子树
遍历演示:
代码 :
// 中序遍历 void inOrder(TreeNode root) { if (root == null) { return; } // 递归左子树 inOrder(root.left); // 打印当前节点的值 System.out.print(root.val + " "); // 递归右子树 inOrder(root.right); }
3. 后序遍历
后序遍历的顺序: 左子树 -> 右子树 -> 根结点
代码:
// 后序遍历 void postOrder(TreeNode root) { if (root == null) { return; } // 递归左子树 postOrder(root.left); // 递归右子树 postOrder(root.right); // 打印当前节点的值 System.out.print(root.val + " "); }
测试代码:
public class Test { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); BinaryTree.TreeNode root = binaryTree.createTree(); System.out.print("前序遍历："); binaryTree.preOrder(root); System.out.println(); System.out.print("中序遍历："); binaryTree.inOrder(root); System.out.println(); System.out.print("后序遍历："); binaryTree.postOrder(root); } }
运行结果:
