一、遍历特点
1. 不需要递归
2. 不需要栈
3. 顺着线索指针，依次访问
4. 遍历顺序依然：左 → 根 → 右
二、先回顾结点标记
- `ltag = 0`：left 是左孩子
- `ltag = 1`：left 是前驱线索
- `rtag = 0`：right 是右孩子
- `rtag = 1`：right 是后继线索
三、遍历完整步骤
步骤1：找到中序遍历第一个结点
从根出发，一直向左走
只要 `ltag == 0` 就继续左走
走到不能左走为止，就是最左下结点
→ 中序第一个访问结点
步骤2：访问当前结点
输出当前结点数据
步骤3：找当前结点的后继结点
分两种情况：
1. `rtag == 1`
右指针是线索
直接 `p = p.right` 就是后继
2. `rtag == 0`
右指针是右孩子
进入右子树，继续往左走到最底端
那个结点就是后继
步骤4：循环
重复 2、3 步，直到 `p == null` 结束
四、遍历口诀
找首结点：一路向左到底
访问结点：直接打印
找后继：
- 右是线索 → 直接跳
- 右是孩子 → 右子树向左到底
五、Java 完整遍历代码
//中序线索二叉树遍历（非递归、不用栈） public void inThreadTraverse(ThreadNode p) { if(p == null) return; //1. 找中序第一个结点：最左下 while(p.ltag == 0){ p = p.left; } //2. 循环遍历所有结点 while(p != null){ System.out.print(p.data + " "); //判断后继 if(p.rtag == 1){ //右是线索，直接后继 p = p.right; }else{ //右是孩子，进入右子树，找最左下 p = p.right; while(p.ltag == 0){ p = p.left; } } } }六、总结
1. 中序线索树遍历空间复杂度 O(1)
2. 普通二叉树非递归遍历空间 O(h)（栈）
3. 叶子结点左右全是线索，直接顺着走就行
4. 第一个结点：整树最左下
5. 最后一个结点：整树最右下，右线索指向 null
6. 循环线索二叉树首尾相连，不会为空
七、构造 + 遍历对比一句话
-构造线索树：中序遍历 + pre 绑定空指针
-遍历线索树：不用栈递归，顺着前驱后继线索走
