上一篇咱们学习顺序存储二叉树，这时呈现一个问题，咱们来看看
将数列{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
找到后输入这个节点
如果以后节点的右指针也是后继节点则替换成该后也输入
若以后节点的右指针不满足后继节点则替换往下走
发表回复