数据结构-二叉树
二叉树(Binary tree)是数据结构里树形结构的一个重要类型，常常用在时间复杂度或空间复杂度为logN的场景。
二叉树
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode() {
}
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}术语
①节点：包含一个数据元素及若干指向子树分支的信息。
②节点的度：一个节点拥有子树的数目称为节点的度。
③叶子节点：也称为终端节点，没有子树的节点或者度为零的节点。
④分支节点：也称为非终端节点，度不为零的节点称为非终端节点。
⑤树的度：树中所有节点的度的最大值。
⑥节点的层次：从根节点开始，假设根节点为第1层，根节点的子节点为第2层，依此类推，如果某一个节点位于第L层，则其子节点位于第L+1层 。
⑦树的深度：也称为树的高度，树中所有节点的层次最大值称为树的深度。
⑧有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树。
⑨无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树。
⑩森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除，则该树就变成了一片森林，森林中的树由原来根节点的各棵子树构成 。
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
二叉树的性质
性质1 二叉树第i层上的结点数目最多为2^(i-1)个 (i≥1)。
性质2 深度为k的二叉树至多有2^k-1个结点(k≥1)。
性质3 在任意-棵二叉树中，若终端结点(叶子节点)的个数为n0，度为2的结点数为n2，则no=n2+1。
特殊的二叉树
二叉树按照特点， 满二叉树、完全二叉树、二叉搜索数、平衡二叉搜索树
满二叉树
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
这棵二叉树为满二叉树，也可以说深度为n，有2^(n-1)个节点的二叉树。
完全二叉树
完全二叉树：在完全二叉树中，除了最底层叶子节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第n层，则该层包含 1~ 2^(n-1) 个节点。
二叉搜索树
二叉搜索树是有数值的，二叉搜索树是一个有序树。
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树
平衡二叉搜索树
平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
二叉树的存储方式
二叉树可以链式存储，也可以顺序存储。
链式存储
顺序存储
二叉树顺序存储特点: 如果父节点的数组下标是i，那么它的左孩子下标是 2*i + 1，右孩子下标是 2*i + 2。
二叉树的遍历方式
二叉树主要有两种遍历方式：
1、深度优先遍历：先往深走，遇到叶子节点再往回走。
2、广度优先遍历：一层一层的去遍历。
这两种遍历是图论中最基本的两种遍历方式
从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：
深度优先遍历
前序遍历（递归法，迭代法）
中序遍历（递归法，迭代法）
后序遍历（递归法，迭代法）
广度优先遍历
层次遍历（迭代法）
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode() {
}
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}深度优先遍历
前序遍历，对树中的任意节点来说，先打印节点本身，然后打印它的左子树，最后打印它的右子树。 (根左右)
中序遍历，对树中的任意节点来说，先打印它的左子树，然后再打印它的本身，最后打印它的右子树。 (左根右)
后序遍历，对于树中的任意节点来说，先打印左子树，然后打印右子树，最后才打印节点本身。 (左右根)
前序遍历
二叉树的前序遍历：按照访问根节点——左子树——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。
递归法
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
preorder(root, res);
return res;
}
public void preorder(TreeNode root, List<Integer> res) {
// 结束条件 遍历到的根节点为空
if (root == null) {
return;
}
// 根节点——左子树——右子树
res.add(root.val);
preorder(root.left, res);
preorder(root.right, res);
}
} 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为O(logn)，最坏情况下树呈现链状，为 O(n)。
中序遍历
后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
postorder(root, res);
return res;
}
public void postorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
// 左右根
postorder(root.left, res);
postorder(root.right, res);
res.add(root.val);
}
}广度优先遍历
广度优先搜索(BFS)两个场景：层序遍历、最短路径。
层序遍历
/**
*
*
* 参考：https://leetcode.cn/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
// 保存遍历结果 队列是先进先出 保证每次从队列头出队
Queue<TreeNode> queue = new ArrayDeque<>();
if (root != null) {
queue.add(root);
}
// 结束条件
while (!queue.isEmpty()) {
// 上一层的节点个数 通过n来控制遍历节点个数 保证把队列
int n = queue.size();
// 当前层遍历到节点的值
List<Integer> level = new ArrayList<>();
// 上一层有n个节点 需要从队列头部出队n次
for (int i = 0; i < n; i++) {
// 从队列头出队
TreeNode node = queue.poll();
level.add(node.val);
// 把当前层遍历到的节点放到队列尾部
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res.add(level);
}
return res;
}/**
* 1. 获取根节点集合
* 2. 根据根节点获取下一层的节点
* 3. 循环 只要根节点集合不为空就循环
*/
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return Collections.emptyList();
}
List<List<Integer>> list = new ArrayList<List<Integer>>();
list.add(Collections.singletonList(root.val));
List<TreeNode> rootNodes = Collections.singletonList(root);
while (true) {
// 根据根节点集合获取下一层节点
List<TreeNode> levelNodes = getLevelNodes(rootNodes);
if (levelNodes == null || levelNodes.size() == 0) {
break;
}
// 根据节点获取值
List<Integer> levelList = getValues(levelNodes);
list.add(levelList);
// 更新根节点集合
rootNodes = levelNodes;
}
return list;
}
public List<Integer> getValues(List<TreeNode> levelNodes) {
List<Integer> list = new ArrayList();
for (TreeNode node : levelNodes) {
list.add(node.val);
}
return list;
}
public List<TreeNode> getLevelNodes(List<TreeNode> rootNodes) {
if (rootNodes == null || rootNodes.size() == 0) {
return Collections.emptyList();
}
List<TreeNode> list = new ArrayList();
for (TreeNode node : rootNodes) {
if (node.left != null) {
list.add(node.left);
}
if (node.right != null) {
list.add(node.right);
}
}
return list;
}最短路径
参考资料
[1] 《数据结构》(C语言版) 严蔚敏 吴伟民
[2] 二叉树理论基础篇
[3] 二叉树
[4] 二叉树的性质及相关证明
[5] 23-二叉树基础（上）：什么样的二叉树适合用数组来存储？