Javajava算法
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 createTree() {
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 size(Node root) {
if (root == null) {
return 0;
}
return size(root.left) + size(root.right) + 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 getHeight(Node root) {
if (root == null) {
return 0;
}
int leftH = getHeight(root.left);
int rightH = getHeight(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;
}
return find(root.right, val);
}
树形结构是一种'一对多'的层级数据组织方式，而二叉树作为它的特殊形式（每个节点最多俩孩子），凭借满二叉树、完全二叉树等细分类型，以及明确的性质（比如节点数和层数的关系），成了实际开发中常用的结构。我们可以用不同方式存储二叉树，也能通过前/中/后序遍历'逛遍'树里的每个节点——掌握这些内容，不仅能理解数据的组织逻辑，也能为后续学更复杂的树结构（比如红黑树）打牢基础。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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