二叉树操作全解析

### 二叉树操作全解析 #### 插入节点相关 在二叉树中插入新节点时，我们使用一个新变量 `parent` 来记录遇到的最后一个非空节点。这是因为在查找合适插入位置的过程中，`current` 可能会被置为 `null`，若不保存 `parent`，就会丢失插入位置信息。插入新节点时，需改变 `parent` 节点相应的子节点指针，使其指向新节点。若查找的是 `parent` 的左子节点，就将新节点作为 `parent` 的左子节点；若查找的是右子节点，则将新节点作为 `parent` 的右子节点。 相关代码逻辑如下： ```java current = current.rightChild; if(current == null) // if end of the line { // insert on right parent.rightChild = newNode; return; } ``` #### 树的遍历 树的遍历是指按指定顺序访问树中的每个节点。虽然它不像查找、插入和删除节点那样常用，因为遍历速度不是特别快，但在某些情况下很有用，且在理论上也很有趣。树的遍历有三种简单方式：前序遍历（preorder）、中序遍历（inorder）和后序遍历（postorder）。对于二叉搜索树，最常用的是中序遍历。 ##### 中序遍历 中序遍历二叉搜索树会使所有节点按键值升序被访问。若要创建二叉树数据的有序列表，中序遍历是一种方法。中序遍历可通过递归实现，递归方法接收一个节点作为参数，初始时该节点为根节点。该方法只需执行三步： 1. 调用自身遍历节点的左子树。 2. 访问该节点（可以是显示节点内容、将其写入文件等操作）。 3. 调用自身遍历节点的右子树。 中序遍历的 Java 代码如下： ```java private void inOrder(node localRoot) { if(localRoot != null) { inOrder(localRoot.leftChild); System.out.print(localRoot.iData + " "); inOrder(localRoot.rightChild); } } ``` 调用时以根节点为参数： ```java inOrder(root); ``` 以一个简单的三节点树为例，根节点为 `A`，左子节点为 `B`，右子节点为 `C`。调用 `inOrder(A)` 时，会先调用 `inOrder(B)`，由于 `B` 无左子节点，会调用 `inOrder(null)` 并立即返回；接着访问 `B`，再调用 `inOrder(null)` 并返回；然后回到 `inOrder(A)`，访问 `A`，再调用 `inOrder(C)`，同样处理后整个遍历完成，节点访问顺序为 `A, B, C`，符合中序遍历的升序规则。 使用 Workshop 小程序进行中序遍历时，反复按下 `Trav` 按钮即可。以图 8.10 中的树为例，遍历过程如下表所示： | 步骤编号 | 红色箭头所在节点 | 消息 | 已访问节点列表 | | --- | --- | --- | --- | | 1 | 50 (根节点) | 检查左子节点 | | | 2 | 30 | 检查左子节点 | | | 3 | 20 | 检查左子节点 | | | 4 | 20 | 访问该节点 | 20 | | 5 | 20 | 检查右子节点 | 20 | | 6 | 20 | 返回上一子树的根节点 | 20 | | 7 | 30 | 访问该节点 | 20 | | 8 | 30 | 检查右子节点 | 20 30 | | 9 | 40 | 检查左子节点 | 20 30 | | 10 | 40 | 访问该节点 | 20 30 | | 11 | 40 | 检查右子节点 | 20 30 40 | | 12 | 40 | 返回上一子树的根节点 | 20 30 40 | | 13 | 50 | 访问该节点 | 20 30 40 | | 14 | 50 | 检查右子节点 | 20 30 40 50 | | 15 | 60 | 检查左子节点 | 20 30 40 50 | | 16 | 60 | 访问该节点 | 20 30 40 50 | | 17 | 60 | 检查右子节点 | 20 30 40 50 60 | | 18 | 60 | 返回上一子树的根节点 | 20 30 40 50 60 | | 19 | 50 | 遍历完成 | 20 30 40 50 60 | 整个遍历过程的 mermaid 流程图如下： ```mermaid graph TD; A[开始遍历根节点 50] --> B[检查左子节点 30]; B --> C[检查左子节点 20]; C --> D[访问 20]; D --> E[检查 20 右子节点]; E --> F[返回上一子树 30]; F --> G[访问 30]; G --> H[检查 30 右子节点 40]; H --> I[检查 40 左子节点]; I --> J[访问 40]; J --> K[检查 40 右子节点]; K --> L[返回上一子树 50]; L --> M[访问 50]; M --> N[检查 50 右子节点 60]; N --> O[检查 60 左子节点]; O --> P[访问 60]; P --> Q[检查 60 右子节点]; Q --> R[返回上一子树 50]; R --> S[遍历完成]; ``` ##### 前序和后序遍历 除了中序遍历，还有前序和后序遍历。前序遍历的步骤顺序为： 1. 访问节点。 2. 调用自身遍历节点的左子树。 3. 调用自身遍历节点的右子树。 后序遍历的步骤顺序为： 1. 调用自身遍历节点的左子树。 2. 调用自身遍历节点的右子树。 3. 访问节点。 对于表示代数表达式 `A*(B+C)