线索化二叉树
前言： 对于线索化二叉树来说，他的后序线索化二叉树的遍历是其最难的地方，需要很多的辅助节点 对于中序、前序线索化二叉树相对来说比较简单。
Node节点类的代码：
代码语言：javascript复制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指针为空，说明是最后一个，遍历完成。
前序线索化
代码语言：javascript复制/**
* 前序线索化
*/
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);
}
}前序线索化的遍历
代码语言：javascript复制/**
* 前序线索化二叉树的遍历
*/
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指针为空，说明是最后一个，遍历完成。
中序线索化
代码语言：javascript复制/**
* 使用中序线索化将节点连接
* @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);
}中序线索化的遍历
代码语言：javascript复制/**
* 中序线索化遍历
*/
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节点。
后序线索化
代码语言：javascript复制/**
* 后序线索化
*/
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;
}后序线索化遍历★★★★★
代码语言：javascript复制/**
* 后序线索化遍历★★★★★
* 与前面的有所不用，终止为临时节点到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;
}
}
}
}
}
