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 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');
();
A.left = B;
A.right = C;
B.left = D;
B.right = E;
E.right = H;
C.left = F;
C.right = G;
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;
}
getHeight(root.left);
getHeight(root.right);
Math.max(leftH, rightH) + ;
}
Node {
(root == ) {
;
}
(root.val == val) {
root;
}
find(root.left, val);
(ret != ) {
ret;
}
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