线索化二叉树
前言：
对于线索化二叉树来说，他的后序线索化二叉树的遍历是其最难的地方，需要很多的辅助节点
对于中序、前序线索化二叉树相对来说比较简单。
Node节点类的代码：
public class Node { public int id; public String name; public Node right; public Node left; /** * l 作用 ：标注left节点，若有值则为 0 无值,但经过序列化复制后为 1 * r 作用 ：标注right节点，若有值则为 0 无值,但经过序列化复制后为 1 */ public int l; public int r; public Node parent; //用于后序序列化遍历时使用 //前序遍历 public void prefix(){ System.out.println(this); if(this.left != null){ this.left.prefix(); } if (this.right != null){ this.right.prefix(); } } //中序遍历 public void infix(){ if(this.left != null){ this.left.infix(); } System.out.println(this); if (this.right != null){ this.right.infix(); } } //后序遍历 public void suffix(){ if(this.left != null){ this.left.suffix(); } if (this.right != null){ this.right.suffix(); } System.out.println(this); } public Node(int id, String name) { this.id = id; this.name = name; } @Override public String toString() { return "Node{" + "id=" + id + ", name='" + name + '\'' + ", left节点是否为空=" + l + ", right节点是否为空=" + r + '}'; //0为有值 / 1为线索化后有值 } }
前序线索化二叉树
思路：
线索化思路
首先判断当前节点是否为空，如果不为空再做处理。
- 左移至最左边，判定left为空时将临时节点指向当前node节点的左指针
- 处理右节点时是在下一次，此时node为下一个节点，而temp则指向上一轮的node节点。然后将temp指向的right节点连接到node（也就是当前节点）
- temp节点，让其始终跟在node节点的后面（node节点递归移动）
- 向左右分别递归移动当前节点
线索化遍历思路
根左右，所以从根节点开始，沿着左子树进行处理，当子节点的left指针类型是null时，给其left赋值，然后标注为此node的l= 1 说明到了最左子节点，然后处理子节点的right指针指向的节点，可能是右子树，也可能是后继节点，无论是哪种类型继续按照上面的方式（先沿着左子树处理，找到子树的最左子节点，然后处理right指针指向），以此类推，直到节点的right指针为空，说明是最后一个，遍历完成。
前序线索化
/** * 前序线索化 */ public void prefixSearch(Node node){ if (node == null){ return; } //先处理左节点 if(node.left == null){ node.left = temp; node.l = 1; } //然后再处理右节点 if(temp != null && temp.right == null){ temp.right = node; temp.r = 1; } temp = node; //向左递归 if(node.l == 0){ prefixSearch(node.left); } //向右递归 if(node.r == 0){ prefixSearch(node.right); } }
前序线索化的遍历
/** * 前序线索化二叉树的遍历 */ public void prefixLink(){ Node node = root; while(node != null){ System.out.println(node); while(node.l == 0){ node = node.left; System.out.println(node); } while(node.r == 1){ node = node.right; System.out.println(node); } node = node.right; } }
中序线索化二叉树
思路：
线索化思路
首先判断当前节点是否为空，如果不为空再做处理。
- 向左递归移动当前节点
- 判定left为空时将临时节点指向当前node节点的左指针
- 处理右节点时是在下一次，此时node为下一个节点，而temp则指向上一轮的node节点。然后将temp指向的right节点连接到node（也就是当前节点）
- temp节点，让其始终跟在node节点的后面（node节点递归移动）
- 向右递归移动当前节点
遍历思路
左根右，因此第一个节点一定是最左子节点，先找到最左子节点，依次沿着right指针指向进行处理（无论是指向子节点还是指向后继节点），直到节点的right指针为空，说明是最后一个，遍历完成。
中序线索化
/** * 使用中序线索化将节点连接 * @param node : 为当前节点 * temp : 为当前节点的后面的节点 */ public void infixSearch(Node node){ //首先，如果当前节点为空，那么就不用继续连接 if(node == null){ return; } //左递归找到最left的节点 infixSearch(node.left); //来处理当前节点 if (node.left == null){ node.left = temp; //如果当前节点的left为空，那么就说明已经递归到最left的节点了 node.l = 1; //标注，当前节点为叶子节点 } //后面的节点不能为空 。 因为他必须遍历到最left边（最左边的叶子节点）才能开始使用temp节点 if (temp!= null && temp.right == null){ temp.right = node; temp.r = 1; } //移动辅助节点 temp = node; //右递归找到最right的节点 infixSearch(node.right); }
中序线索化的遍历
/** * 中序线索化遍历 */ public void infixLink(){ //首先创建一个临时节点，用于遍历所有的节点 Node node = root; while(node != null){ //先循环到最left while(node.l == 0){ node = node.left; } System.out.println(node); //然后判断，继续循环其他的 while(node.r == 1){ node = node.right; System.out.println(node); } node = node.right; } }
后序线索化二叉树
思路：
线索化思路
首先判断当前节点是否为空，如果不为空再做处理。
- 向左递归移动当前节点
- 向右递归移动当前节点
- 判定left为空时将临时节点指向当前node节点的左指针
- 处理右节点时是在下一次，此时node为下一个节点，而temp则指向上一轮的node节点。然后将temp指向的right节点连接到node（也就是当前节点）
- temp节点，让其始终跟在node节点的后面（node节点递归移动）
线索化遍历思路
后序遍历线索化二叉树最为复杂，通用的二叉树数节点存储结构不能够满足后序线索化，因此我们扩展了节点的数据结构，增加了父节点的指针。后序的遍历顺序是：左右根，先找到最左子节点，沿着right后继指针处理，当right不是后继指针时，并且上一个处理节点是当前节点的右节点，则处理当前节点的右子树，遍历终止条件是：当前节点是root节点，并且上一个处理的节点是root的right节点。
后序线索化
/** * 后序线索化 */ public void suffixSearch(Node node){ if (node == null){ return; } //向左递归 suffixSearch(node.left); //向右递归 suffixSearch(node.right); //先处理左节点 if(node.left == null){ node.left = temp; node.l = 1; } //然后再处理右节点 if(temp != null && temp.right == null){ temp.right = node; temp.r = 1; } temp = node; }
后序线索化遍历★★★★★
/** * 后序线索化遍历★★★★★ * 与前面的有所不用，终止为临时节点到root节点 */ public void suffixLink(){ Node node = root; //辅助指针1 //先循环走到最左边 while(node.l == 0){ node = node.left; } Node pre = null; //辅助指针2 while(node != null){ //如果节点被序列化，那么就右移，同时移动辅助指针2 if (node.r == 1){ System.out.println(node); pre = node; node = node.right; }else{ //如果当前node节点有右节点，那么 if(node.right == pre){ System.out.println(node); if(node == root){ return; } pre = node; node = node.parent; // 回到父节点 }else{ node = node.right; while (node != null && node.l == 0){ node = node.left; } } } } }
