Javajava算法
Java 数据结构：树形结构与二叉树详解
树形结构模拟自然界层级关系，二叉树作为其特殊形式每个节点最多两棵子树。内容涵盖满二叉树与完全二叉树定义、节点性质公式、顺序与链式存储方案。提供 Java 实现的手动创建、前中后序遍历递归算法，以及节点数、叶子节点、高度查找等常用操作方法，为学习红黑树等复杂结构奠定基础。
树形结构模拟自然界层级关系，二叉树作为其特殊形式每个节点最多两棵子树。内容涵盖满二叉树与完全二叉树定义、节点性质公式、顺序与链式存储方案。提供 Java 实现的手动创建、前中后序遍历递归算法，以及节点数、叶子节点、高度查找等常用操作方法，为学习红黑树等复杂结构奠定基础。
【前言】
你有没有想过，电脑里的文件分类、通讯录的层级关系，其实都藏着'树'的影子？树形结构是数据结构里最像'现实家族关系'的存在，而二叉树更是其中的'明星选手'——它规则清晰、操作灵活，是很多复杂数据处理的基础。这篇文章会从树形结构的概念入手，一步步拆解二叉树的类型、性质、存储和操作，帮你把这些抽象的结构变成能上手用的知识~
树是一种非线性的数据结构，它模拟了自然界中树的结构。树形结构由若干个节点 (node) 组成，这些节点之间存在明确的层次关系。
树是递归定义的结点的度：⼀个结点含有⼦树的个数称为该结点的度；树的度：⼀棵树中，所有结点度的最⼤值称为树的度；叶⼦结点或终端结点：度为 0 的结点称为叶结点；双亲结点或⽗结点：指向其他节点的节点孩⼦结点或⼦结点：被其他节点指向的节点根结点：每个树形结构有一个
根节点(root)，它是树的起点；⾮终端结点或分⽀结点：度不为 0 的结点；兄弟结点：具有相同⽗结点的结点互称为兄弟结点；堂兄弟结点：双亲在同⼀层的结点互为堂兄弟；
双亲表⽰法，孩⼦表⽰法、孩⼦双亲表⽰法、孩⼦兄弟表⽰法…
class Node {
int value; //数据域
Node firstChild; //第一个孩子
Node nextBrother; //下一个兄弟
}
二叉树是一种非线性数据结构，其中每个节点最多有两棵树，分别称为左子树和右子树。
二叉树分为两种：满二叉树和完全二叉树
定义：==每个节点都有 0 个或 2 个子节点 ==
特点：没有只有 1 个子节点的节点
定义：==除最后一层外，所有层都完全填满，且最后一层节点尽可能靠左 ==
应用：常用于堆的实现
若 i>0，双亲序号：(i-1)/2；i=0，i 为根结点编号，⽆双亲结点 若 2i+1<n，左孩⼦序号：2i+1，否则⽆左孩⼦ 若 2i+2<n，右孩⼦序号：2i+2，否则⽆右孩⼦
⼆叉树的存储结构分为：顺序存储和类似于链表的链式存储。 ⼆叉树的链式存储是通过⼀个⼀个的节点引⽤起来的，常⻅的表⽰⽅式有⼆叉和三叉表⽰⽅式
//孩子表示法
class Node {
int val; //数据域
Node left; //左孩子的引用
Node right; //右孩子的引用
}
//孩子双亲表示法
class Node1 {
int val; //数据域
Node left; //左孩子的引用
Node right; //右孩子的引用
Node parent; //当前节点的根节点
}
public static class Node {
public char val;
public Node left;
public Node right;
public Node(char val) {
this.val = val;
}
}
//根节点
public Node creatTree() {
Node A = new Node('A');
Node B = new Node('B');
Node C = new Node('C');
Node D = new Node('D');
Node E = new Node('E');
Node F = new Node('F');
Node G = new Node('G');
Node H = new Node('H');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
E.right = H;
C.left = F;
C.right = G;
return A;
}
访问顺序：根节点 → 左子树 → 右子树
//前序遍历
public void preOrder(Node root) {
if (root == null) {
return;
}
System.out.println(root.val);
preOrder(root.left);
preOrder(root.right);
}
访问顺序：左子树 → 根节点 → 右子树
//中序遍历
public void inOrder(Node root) {
if (root == null) {
return;
}
inOrder(root.left); // 修正原代码中的 preOrder 调用
System.out.println(root.val);
inOrder(root.right); // 修正原代码中的 preOrder 调用
}
访问顺序：左子树 → 右子树 → 根节点
//后序遍历
public void postOrder(Node root) {
if (root == null) {
return;
}
postOrder(root.left); // 修正原代码中的 preOrder 调用
postOrder(root.right); // 修正原代码中的 preOrder 调用
System.out.println(root.val);
}
//获取节点个数
public int size2(Node root) {
if (root == null) {
return 0;
}
return size2(root.right) + size2(root.left) + 1;
}
//获取叶子节点个数
public int getLeafNodeCount(Node root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}
//获取第 k 层节点个数
public int getLevelNodeCount(Node root, int k) {
if (root == null) {
return 0;
}
if (k == 1) {
return 1;
}
return getLevelNodeCount(root.left, k - 1) + getLevelNodeCount(root.right, k - 1);
}
//获取二叉树高度
public int getHight(Node root) {
if (root == null) {
return 0;
}
int leftH = getHight(root.left);
int rightH = getHight(root.right);
return Math.max(leftH, rightH) + 1;
}
//找 val 元素是否存在
public Node find(Node root, char val) {
if (root == null) {
return null;
}
if (root.val != val) {
return root; // 逻辑保留原意，但通常应继续搜索
}
Node ret = find(root.left, val);
if (ret != null) {
return ret;
}
Node ret1 = find(root.right, val);
if (ret1 != null) { // 修正原代码中的 ret 判断
return ret1;
}
return null;
}
树形结构是一种'一对多'的层级数据组织方式，而二叉树作为它的特殊形式（每个节点最多俩孩子），凭借满二叉树、完全二叉树等细分类型，以及明确的性质（比如节点数和层数的关系），成了实际开发中常用的结构。我们可以用不同方式存储二叉树，也能通过前/中/后序遍历'逛遍'树里的每个节点——掌握这些内容，不仅能理解数据的组织逻辑，也能为后续学更复杂的树结构（比如红黑树）打牢基础。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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