共计 4972 个字符，预计需要花费 13 分钟才能阅读完成。
上一篇咱们学习顺序存储二叉树，这时呈现一个问题，咱们来看看
将数列{1,3,6,8,10,14}，构建成一颗二叉树
这时候咱们发现一些问题，一起进行剖析看看
1. 当咱们对 二叉树 进行 中序遍历 时，数列为 {8,3,10,1,14,6}
2.6,8,10,14 节点的 左右指针 没有充沛 利用 上
3. 遍历二叉树时除了应用递归遍历二叉树，那么有没有其余办法呢？
4. 心愿利用各个节点左右指针，间接指向左右节点怎么解决？
一、什么是线索化二叉树
针对于后面的问题咱们聊聊线索化二叉树
依据上图所示，咱们发现如果 应用二叉链表 展现 二叉树 就会 发现 n 个节点 中会含有 n+ 1 个空指针域，即上图 有七个空指针域
公式：2n - (n-1) = n+1
因为一共有 2n 个指针，除了根节点，每个节点都被自指针援用
咱们来看看是不是这样？如下图所示
线索二叉树根本介绍
1. 利用 二叉表 中空指针域 ，寄存指向该结点在 某种遍历秩序下的前驱与后续节点的指针 称为线索
2. 这种加上了 线索的二叉链表 称为 线索链表 ，相应的二叉树也称为 线索二叉树 ，依据性质不同别离有 前序、中序、后序等线索二叉树
3. 一个结点的前一个节点，称为 前驱节点
4. 一个结点的后一个节点，称为 后续节点
二、通过示例意识线索化二叉树
示例利用案例阐明:
将上面的 二叉树 进行 中序线索二叉树，中序后果为{8,3,10,1,14,6}
利用示例图解剖析
中序遍历后果：{8,3,10,1,14,6}进行线索化，该怎么操作？
咱们发现 [节点八] 的前驱节点 为Null，后继节点 为[节点三]，要 关联
而 [节点三] 的前驱节点 为[节点八]，后继节点 为[节点十]，但 [节点三] 已指向两子节点 ，则 无需关联
而 [节点十] 的前驱节点 为[节点三]，要 关联 ， 后继节点 为[节点一]，要 关联
而 [节点一] 的前驱节点 为[节点十]，后继节点 为[节点十四]，但 [节点一] 已指向两子节点 ，则无需 关联
而 [节点十四] 的前驱节点 为[节点一]，要 关联 ， 后继节点 为[节点六]，要 关联
而 [节点六] 的前驱节点 为[节点十四]，后继节点 为Null，则无需 关联
线索化问题发现
那么有没有发现，如果这样安顿关联就会发现 [节点一] 的一些 问题
1.前驱节点 应该是 [节点十]，但[节点一] 并没有指向[节点十]
2.后继节点 应该是 [节点十四]，但[节点一] 并没有指向[节点十四]
left、right 属性的状况阐明
当 线索化二叉树 后，Node 节点的属性left、right 会有以下状况
①：[left 指向的是左子树，也可能是指向的前驱节点 ]，比方[节点一] 的 left 指向的 左子树 , 而[节点十] 的 left 指向的就是 前驱节点.
②：[right 指向的是右子树，也可能是指向后继节点 ]，比方[节点一]right 指向的是 右子树 ，而[节点十] 的 right 指向的是 后继节点.
所以咱们须要加多 [标记 Type] 代表以后是指向 子树、还是节点
利用示例思路剖析
同时咱们进行中序线索化，当初各位小伙伴还记得 二叉树遍历 形式吗？
- 前序是先输入父节点，再遍历左子树和右子树
- 中序是先遍历左子树，再输入父节点，最初遍历右子树
- 后序是先遍历左子树，再遍历右子树，最初输入父节点
所以中序思路步骤分：先线索化左子树、再线索化以后节点、最初线索化右子树
当咱们线索化 [某个节点 node] 时，其实须要一个 [前驱节点 pre] 形成关系关联，这样才有可能实现线索化。如图所示
当初咱们来剖析 [ 线索化前驱节点的思路]：队列的[节点八]
每解决完后，记得让以后 node 成为下一个节点的前驱节点：pre = node
当初咱们来剖析 [ 线索化后继节点的思路]：队列的[节点八]
当初咱们依据思路定义节点 HeroNode 信息
// 创立 HerNode
class HeroNode {
private int no;
private String name;
private HeroNode left; // 默认 null 左节点
private HeroNode right; // 默认 null 右节点
/**
* 阐明
* 1. leftType == 0 示意指向的是左子树
* 2. leftType == 1 示意指向的是前驱节点
*
* 3.rigthType == 0 示意指向的是右子树
* 4.rightType == 1 标识指向的是后续节点
*/
private int leftType;
private int rightType;
public int getLeftType() {return leftType;}
public void setLeftType(int leftType) {this.leftType = leftType;}
public int getRightType() {return rightType;}
public void setRightType(int rightType) {this.rightType = rightType;}
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
public int getNo() {return no;}
public void setNo(int no) {this.no = no;}
public String getName() {return name;}
public void setName(String name) {this.name = name;}
public HeroNode getLeft() {return left;}
public void setLeft(HeroNode left) {this.left = left;}
public HeroNode getRight() {return right;}
public void setRight(HeroNode right) {this.right = right;}
@Override
public String toString() {return "HeroNode [no =" + no +", name =" + name +"]";
}
}创立一颗线索化二叉树 ThreadedBinaryTree 信息
class ThreadedBinaryTree{
private HeroNode root;
// 为了实现线索化，须要创立要给指向以后节点的前驱节点的指针
// 在进行递归线索化时，pre 总是保留前一个节点
private HeroNode prenode = null;
public void setRoot(HeroNode root) {this.root = root;}
public void setPrenode(HeroNode prenode) {this.prenode = prenode;}
public void threadedNodes(){this.threadedNodes(root);
}
// 编写对二叉树进行中序线索化办法
private void threadedNodes(HeroNode node){
// 如果 node == null 则不进行线索化
if(node == null){return;}
// 中序遍历的法则：先遍历左子树，再输入父节点，再遍历右子树
//（一）先线索化左子树
threadedNodes(node.getLeft());
//（二）线索化以后节点
// 比如说中序队列：{8,3,10,1,14,6}
// 先解决[节点 8] 那么就要解决节点的前驱节点，判断是否左子树
if(node.getLeft() == null ){
// 以后节点左指针指向前驱节点
node.setLeft(prenode);
node.setLeftType(1);//1 示意指向的是前驱节点 0 示意指向的是左子树
}
// 解决后续节点
if(prenode!=null && prenode.getRight() == null){
// 让前驱节点的右指针指向以后节点
prenode.setRight(node);
// 批改前驱的右指针类型
prenode.setRightType(1);
}
// 解决完每个节点的操作后，让以后 node 是下一个节点的前驱节点
prenode = node;
//（三）再线索化右子树
threadedNodes(node.getRight());
}
}
当初让咱们测试看看线索化后 [节点十] 是否已产生扭转，看看是否胜利
public class ThreadedBinaryTreeDemo {public static void main(String[] args) {
// 创立节点
HeroNode root = new HeroNode(1,"tom");
HeroNode node2 = new HeroNode(3,"jack");
HeroNode node3 = new HeroNode(6,"smith");
HeroNode node4 = new HeroNode(8,"mary");
HeroNode node5 = new HeroNode(10,"king");
HeroNode node6 = new HeroNode(14,"dim");
// 手动创立二叉树依赖
root.setLeft(node2);
root.setRight(node3);
node2.setLeft(node4);
node2.setRight(node5);
node3.setLeft(node6);
// 创立二叉树
ThreadedBinaryTree tree =new ThreadedBinaryTree();
tree.setRoot(root);
tree.threadedNodes();
// 测试节点十的前驱代码与后续节点是否扭转
HeroNode leftNode = node5.getLeft();
HeroNode rigthNode = node5.getRight();
System.out.println("[节点十]的前驱节点是" + leftNode);
System.out.println("[节点十]的后续节点是" + rigthNode);
}
}
运行后果如下：[节点十]的前驱节点是 HeroNode [no =3, name =jack]
[节点十]的后续节点是 HeroNode [no =1, name =tom]三、遍历中序线索化二叉树
因为线索化后，各个结点指向有变动，因而原来的遍历形式不能应用。
这时须要应用新的形式遍历线索化二叉树，各个节点能够通过线型形式遍历。
因而无需应用递归形式，这样也进步了遍历的效率，遍历的秩序该当和中序遍历保持一致。
也就说遍历中序线索化二叉树输入的后果也要是：{8,3,10,1,14,6}
class ThreadedBinaryTree{
// 遍历线索化二叉树的办法
public void threadedList(){
// 定义一个变量，存储以后遍历的结点，从 root 开始
HeroNode node = root;
while(node != null) {
// 循环的找到 leftType == 1 的结点，第一个找到就是 8 结点
// 前面随着遍历而变动, 因为当 leftType== 1 时，阐明该结点是依照线索化
// 解决后的无效结点
while(node. getLeftType() == 0) {node = node.getLeft();
}
// 打印以后这个结点
System.out.println(node);
// 如果以后结点的右指针指向的是后继结点, 就 - 直输入
while(node. getRightType() == 1) {
// 获取到以后结点的后继结点
node = node.getRight();
System. out . println(node);
}
// 替换这个遍历的结点
node = node.getRight();}
}
}public class ThreadedBinaryTreeDemo {public static void main(String[] args) {
// 省略..
tree.threadedList();}
}
运行后果如下：HeroNode [no =8, name =mary]
HeroNode [no =3, name =jack]
HeroNode [no =10, name =king]
HeroNode [no =1, name =tom]
HeroNode [no =14, name =dim]
HeroNode [no =6, name =smith]
咱们就要先找到[节点八]，它的特点是leftType = 1
找到后输入这个节点
如果以后节点的右指针也是后继节点则替换成该后也输入
若以后节点的右指针不满足后继节点则替换往下走