UD5工具箱
二叉树（Binary Tree）
二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树是数据结构中最基础也是最重要的非线性结构之一，广泛应用于搜索、排序、表达式解析等场景。二叉树的节点数为n时，最大高度为n（斜树），最小高度为log2(n+1)（完全二叉树）。
前序遍历（Preorder Traversal）
前序遍历是二叉树深度优先遍历的一种方式，访问顺序为：根节点 -> 左子树 -> 右子树。前序遍历的特点是根节点总是最先被访问。它常用于二叉树的序列化、克隆树结构、前缀表达式求值等场景。前序遍历可以用递归或栈实现，时间复杂度为O(n)。
中序遍历（Inorder Traversal）
中序遍历是二叉树深度优先遍历的一种方式，访问顺序为：左子树 -> 根节点 -> 右子树。中序遍历最显著的特点是：对二叉搜索树（BST）进行中序遍历可以得到递增有序序列。这一特性使其在BST的有序输出和合法性验证中被广泛使用。
后序遍历（Postorder Traversal）
后序遍历是二叉树深度优先遍历的一种方式，访问顺序为：左子树 -> 右子树 -> 根节点。后序遍历的特点是根节点最后被访问，适合需要先处理子节点再处理父节点的场景，如计算目录总大小、表达式树求值、删除树释放内存等。
层序遍历（Level-order Traversal）
层序遍历是二叉树的广度优先遍历方式，按照树的深度层级从上到下、从左到右逐层访问每个节点。层序遍历使用队列作为辅助数据结构，是广度优先搜索（BFS）在树结构上的直接应用。它常用于求解最短路径、按层处理节点等场景。
递归遍历与迭代遍历
递归遍历利用函数调用栈隐式地记录遍历状态，代码简洁直观，但深度过大时可能导致栈溢出。迭代遍历使用显式栈（深度优先）或队列（层序）来模拟递归过程，避免了栈溢出的风险，在工程实践中更为健壮。三种深度优先遍历的迭代实现中，前序和后序较为直观，中序的迭代实现相对复杂。
完全二叉树（Complete Binary Tree）
完全二叉树是一种特殊的二叉树，除最后一层外，每一层的节点数都是满的，且最后一层的节点都尽可能靠左排列。完全二叉树可以用数组高效存储而不需要指针，是堆（Heap）数据结构的基础形态。在数组表示中，节点i的左子节点在2i+1，右子节点在2i+2。
斜树（Skewed Tree）
斜树是一种退化的二叉树，每个节点只有一个子节点，所有节点都排列在同一侧。左斜树只有左子节点，右斜树只有右子节点。斜树在数组表示时空间利用率极低，最坏情况下需要2^n - 1的数组空间来存储n个节点，是二叉树性能分析中的最差情况。
二叉搜索树（Binary Search Tree）
二叉搜索树是一种特殊的二叉树，其中任意节点的左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值。BST支持高效的查找、插入和删除操作，平均时间复杂度为O(log n)。中序遍历BST可以得到递增有序序列，这是验证BST合法性的常用方法。
节点状态标记
在遍历可视化中，节点通常被标记为三种状态：未访问（尚未被遍历过程触及）、正在访问（当前正在处理的节点，处于遍历栈顶或队列头部）和已访问（已经完成处理的节点）。通过不同颜色区分这三种状态，用户可以清晰地观察到遍历过程的推进顺序和当前执行位置。
层序编号与数组表示
二叉树可以用数组按层序编号进行存储：根节点放在索引0位置，对于任意节点i，其左子节点在2i+1位置，右子节点在2i+2位置，父节点在向下取整((i-1)/2)位置。null值表示某个索引位置不存在实际节点，但其索引位置被保留以维持索引关系的正确性。这种表示法在堆和线段树中非常常用。