1. 二叉树
1.1 二叉树的概念
一棵二叉树是结点的一个有限集合，该集合：
Javajava算法
Java 二叉树基础概念、遍历与基本操作
本文介绍 Java 中二叉树的基础知识。涵盖二叉树定义、满二叉树与完全二叉树概念、五大性质及存储结构（链式）。详细讲解前序、中序、后序及层序遍历的递归与非递归实现原理与代码。包含获取节点总数、叶子节点数、第 K 层节点数、树高度、查找元素及判断完全二叉树等基本操作的 Java 代码实现。通过具体示例帮助理解二叉树的遍历逻辑与核心算法应用。
本文介绍 Java 中二叉树的基础知识。涵盖二叉树定义、满二叉树与完全二叉树概念、五大性质及存储结构（链式）。详细讲解前序、中序、后序及层序遍历的递归与非递归实现原理与代码。包含获取节点总数、叶子节点数、第 K 层节点数、树高度、查找元素及判断完全二叉树等基本操作的 Java 代码实现。通过具体示例帮助理解二叉树的遍历逻辑与核心算法应用。
一棵二叉树是结点的一个有限集合，该集合：
二叉树的存储结构分为：顺序存储和类似于链表的链式存储。顺序存储在下节介绍。二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式，具体如下：
// 孩子表示法
class TreeNode {
char val; // 数据域
TreeNode left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
TreeNode right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class TreeNode {
char val; // 数据域
TreeNode left; // 左孩子的引用
TreeNode right; // 右孩子的引用
TreeNode parent; // 当前节点的父节点
}
孩子双亲表示法后序在平衡树位置介绍，本文采用孩子表示法来构建二叉树。
在学习二叉树的基本操作前，需先创建一棵二叉树，然后才能学习其相关的基本操作。为了简单些，此处手动创建一颗简单的二叉树。先学习二叉树的操作，后续再研究二叉树真正的创建方式。
public class BinaryTree {
static class TreeNode {
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public void 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;
C.left = F; C.right = G;
E.right = H;
}
}
再看二叉树基本操作前，回顾下二叉树的概念：
下图是前序遍历的递归过程，中序遍历和后序遍历类似。
前序遍历结果：A B D E H C F G 中序遍历结果：D B H E A F C G 后序遍历结果：D H E B F G C A
以上图二叉树为例，代码实现前中后序递归遍历。
注意: 根的左子树，不只是根的左节点，而是根左边的整颗子树。右子树同理。如上右图。
代码实现前分析 (以前序遍历为例): 前序遍历的顺序为 根 左子树 右子树，凡是递归必有一终止条件，以上右图为例，从根节点往左递到 H，H 的左子树为 null，则返回。所以终止条件为 root 等于 null 则返回。按照顺序：先打印根节点，再递归左子树，后递归右子树。
// 前序遍历：根 左 右
public void preOrder(TreeNode root) {
if(root == null) return; // 终止条件
System.out.print(root.val + " "); // 先打印根
preOrder(root.left); // 再处理左子树
preOrder(root.right); // 最后处理右子树
}
// 中序遍历：左 根 右
public void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
// 后序遍历：左 右 根
public void postOrder(TreeNode root) {
if(root == null) return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
画图理解前序遍历的递归过程。
A 的右子树递归过程与上图类似。
层序遍历：除了前序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为 1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第 2 层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历，如下图所示，层序遍历的结果：A B C D E F G H
代码实现非递归层序遍历：非递归层序遍历，我们可以借助队列，利用队列'先进先出'的特点，实现层序遍历思路：二叉树以根节点、左节点、右节点的顺序入队，出队顺序即为层序遍历，如下图：
具体步骤：先将根节点入队，进入循环 while(!queue.isEmpty())，弹出栈顶元素赋给 cur。打印根节点，将 cur 的左右节点入队。
import java.util.LinkedList;
import java.util.Queue;
// 二叉树的层序遍历
public void levelOrder1(TreeNode root) {
if(root == null) { return; }
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
TreeNode cur = queue.poll();
System.out.print(cur.val + " ");
if(cur.left != null) { queue.offer(cur.left); }
if(cur.right != null) { queue.offer(cur.right); }
}
}
int size(Node root)第一种方法：通过二叉树的遍历求，每递归遍历一次，size++。
public int nodeSize(TreeNode root) {
if(root == null) return 0;
return 1 + nodeSize(root.left) + nodeSize(root.right);
}
第二种方法：通过子问题解决：总节点数 = 左子树 + 右子树 + 1。
public int nodeSize2(TreeNode root) {
if(root == null) return 0;
return nodeSize2(root.left) + nodeSize2(root.right) + 1;
}
int getLeafNodeCount(Node root)第一种思路：定义 leafSize 存储叶子节点的个数，在前序遍历中，当某个节点的左右节点都为 null 时，则 leafSize++。
public int gerLeafSize(TreeNode root) {
if(root == null) return 0;
if(root.left == null && root.right == null) { return 1; }
return gerLeafSize(root.left) + gerLeafSize(root.right);
}
第二种思路：求二叉树叶子节点的个数 = 左子树叶子节点的个数 + 右子树叶子节点的个数。
public int getLeafSize2(TreeNode root) {
if(root == null) return 0;
if(root.left == null && root.right == null) { return 1; }
return getLeafSize2(root.left) + getLeafSize2(root.right);
}
int getKLevelNodeCount(Node root, int k)
public int getKLeveNodeCount(TreeNode root, int k) {
if(root == null) return 0;
if(k == 1) { return 1; }
return getKLeveNodeCount(root.left, k-1) + getKLeveNodeCount(root.right, k-1);
}
int getHeight(Node root)思路：二叉树的高度 = 左子树与右子树之中最大高度 + 1。
public int getHeight(TreeNode root) {
if(root == null) return 0;
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
boolean find(Node root, char key)还是一样的，通过遍历来确定二叉树是否存在值为 value 的节点，以前序遍历为例，判断根节点，递归左子树，再判断左子树，递归右子树，再判断右子树。如果全都没找到则 return false。
public boolean find(TreeNode root, char key) {
if(root == null) return false;
if(root.val == key) { return true; }
boolean leftVal = find(root.left, key);
if(leftVal == true) { return true; }
boolean rightVal = find(root.right, key);
if(rightVal == true) { return true; }
return false;
}
boolean isCompleteTree(Node root)思路：利用层序遍历，将节点入队，当 cur 遇到 null 之后，如果后面还有不为空的节点就说明该二叉树不是完全二叉树，否则是。
public boolean isCompleteTree(TreeNode root) {
if(root == null) { return true; }
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
TreeNode cur = queue.poll();
if(cur != null) {
queue.offer(cur.left);
queue.offer(cur.right);
} else {
break;
}
}
while(!queue.isEmpty()) {
TreeNode cur = queue.poll();
if(cur != null) {
return false;
}
}
return true;
}
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online