总目录：地址如下看总纲
1、传统二叉树问题
将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树. n+1=7
公式得到的 7 ,指的是叶子节点左右两边分别为空，总共 空出的个数为 7
image.png- 问题分析：
1、当我们对上面的二叉树进行中序遍历时，数列为 {8, 3, 10, 1, 6, 14 }
2、但是 6, 8, 10, 14 这几个节点的 左右指针，并没有完全的利用上（并且为空）
3、若充分的利用 各个节点的左右指针， 让各个节点可以指向自己的前后节点【既 线索化二叉树】
2、线索化二叉树介绍：
- n个结点的二叉链表中含有n+1 【公式推导 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序（前序，中序，或者后序）下的前驱和后继结点的指针（这种附加的指针称为"线索"）
- 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
- 一个结点的前一个结点，称为前驱结点。一个结点的后一个结点，称为后继结点
3、中序线索化二叉树案例分析思路：
- 当线索化二叉树后，Node节点的 属性 left 和 right ，有如下情况：
(1) left 指向的是左子树，也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的就是前驱节点。
(2) right指向的是右子树，也可能是指向后继节点，比如 ① 节点right 指向的是右子树，而⑩ 节点的right 指向的是后继节点。图解：
image.png
4、中序线索化二叉树遍历的思路分析
- 因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历线索化二叉树。各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。 遍历的次序应当和中序遍历保持一致（既，中序线索化实现得用，中序线索化遍历。前后序亦是如此）
图解：
image.png
5、中序线索化二叉树实现 + 遍历的代码
package com.kk.datastructure.tree;
/**
* title: 中序线索化二叉树实现+遍历
* @author 阿K
* 2021年1月2日 上午12:26:17
*/
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 threadedBinaryTree = new ThreadedBinaryTree();
threadedBinaryTree.setRoot(root);
threadedBinaryTree.threadedNodes();
// 测试: 以10号节点测试
HeroNode leftNode = node5.getLeft();
HeroNode rightNode = node5.getRight();
System.out.println("10号结点的前驱结点是 =" + leftNode); // 3
System.out.println("10号结点的后继结点是=" + rightNode); // 1
// 测试中序线索化遍历
System.out.println("-------美丽的分割线------------");
threadedBinaryTree.threadedList();// 8,3,10,1,14,6
}
}
// 实现线索化二叉树
class ThreadedBinaryTree {
private HeroNode root;
public void setRoot(HeroNode root) {
this.root = root;
}
// 重载方便调用
public void threadedNodes() {
this.threadedNodes(root);
}
// 1. 要实现线索化，需要一个指向当前节点的前驱节点
// 2. 在递归进行线索化时， per 总是指向(保留)前一个节点
public HeroNode per = null;
// 遍历中序线索化二叉树 Api(中序线索化得用中序线索化遍历，前后序也如此)
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();
}
}
// 二叉树进行中序线索化二叉树实现 Api
public void threadedNodes(HeroNode node) {
// 日常判空
if (node == null) {
return;
}
/**
* 个人理解：若没有左子树指向，即为空指向，若是左空，则指向前驱，若是右空，则指向后驱
*/
// 一、先线索化左子树
threadedNodes(node.getLeft());
// 二、线索化当前节点【难】
// 1、处理当前节点的前驱节点
// 举例：如上图的叶子节点 8 为例
// 若节点 8.left == null（既没有左子树可指向，则指向前驱节点）, 节点 8.leftType =1(指定为前驱类型标识)
if (node.getLeft() == null) {
// 让当前节点的左指针，指向前驱节点
node.setLeft(per);
// 修改当前节点做指针的类型，定义为前驱
node.setLeftType(1);
}
// 2、处理当前节点的后继节点(后继：就是在后面还得继续当前节点，所以还是这个节点在处理
if (per != null && per.getRight() == null) {
// 让前驱节点的右指针指向当前节点
per.setRight(node);
// 修改前驱节点的有指针类型
per.setRightType(1);
}
// 每处理一个节点，让当前节点是下一个节点的前驱节点(后移)
per = node;
// 三、线索化右子树
threadedNodes(node.getRight());
}
}
// 节点
class HeroNode {
private int id;
private String name;
private HeroNode left;// 默认为 null
private HeroNode right;// 默认为 null
// 说明：
// 1、若 leftType == 0,表指向的是左子树；若 leftType ==1 ,表指向的是前驱节点
// 2、若 rightType == 0,表指向的是右子树；若 leftType ==1 ,表指向的是后驱节点
private int leftType;// 默认 0
private int rightType;
public HeroNode(int id, String name) {
super();
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
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;
}
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;
}
@Override
public String toString() {
return "HeroNode [id=" + id + ", name=" + name + "]";
}
}
6、前、中、后序线索化二叉树实现+遍历完整代码
package com.kk.datastructure.tree;
/**
* title: 线索化二叉树前中后序实现+遍历
* @author 阿K
* 2021年1月2日 上午2:05:23
*/
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);
// 后序专属：为节点手动绑定父节点
node4.setParent(node2);
node5.setParent(node2);
node6.setParent(node3);
node2.setParent(root);
node3.setParent(root);
// 测试中序线索化
ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
threadedBinaryTree.setRoot(root);
// threadedBinaryTree.threadedNodes();
// threadedBinaryTree.perThreadedNodes();
threadedBinaryTree.postThreadedNodes();
// 测试: 以10号节点测试
HeroNode leftNode = node5.getLeft();
HeroNode rightNode = node5.getRight();
System.out.println("10号结点的前驱结点是 =" + leftNode); // 3
System.out.println("10号结点的后继结点是=" + rightNode); // 1
// 测试中序线索化遍历
System.out.println("-------美丽的分割线------------");
// threadedBinaryTree.threadedList();// 8,3,10,1,14,6
// 测试前序线索化遍历
System.out.println("-------美丽的分割线------------");
// threadedBinaryTree.perThreadedList();// 1,3,8,10,6,14
// 测试前序线索化遍历
System.out.println("-------美丽的分割线------------");
threadedBinaryTree.postThreadedList();// 8,10,3,14,6,1
}
}
// 实现线索化二叉树
class ThreadedBinaryTree {
private HeroNode root;
public void setRoot(HeroNode root) {
this.root = root;
}
// 重载方便调用
public void threadedNodes() {
this.threadedNodes(root);
}
// 重载方便调用
public void perThreadedNodes() {
this.perThreadedNodes(root);
}
// 重载方便调用
public void postThreadedNodes() {
this.postThreadedNodes(root);
}
// 1. 要实现线索化，需要一个指向当前节点的前驱节点
// 2. 在递归进行线索化时， per 总是指向(保留)前一个节点
public HeroNode per = null;
// 遍历中序线索化二叉树 Api(中序线索化得用中序线索化遍历，前后序也如此)
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();
}
}
// 遍历前序线索化二叉树 Api(按照后继搜索遍历)
public void perThreadedList() {
// 定义一个变量，存储当前遍历的结点，从root开始
HeroNode node = root;// 此处 root 也可传参进来
while (node != null) {
while (node.getLeftType() == 0) {
System.out.println(node);
// 若不是前驱则移动
node = node.getLeft();
}
System.out.println(node);
// 替换当前遍历的节点（后移）---就像链表，缺少则是死循环
node = node.getRight();
}
}
// 遍历后序线索化二叉树 Api(按照后继)
public void postThreadedList() {
// 定义一个变量，存储当前遍历的结点，从root开始
HeroNode node = root;
while (node != null && node.getLeftType() == 0) {
// 若不是前驱则移动，直到才满足退出
node = node.getLeft();
}
// 辅助变量
HeroNode perNode = null;
while (node != null) {
// 右节点是线索
if (node.getRightType() == 1) {
System.out.println(node);
perNode = node;
node = node.getRight();
} else {
// 若上个处理的节点，是当前节点的右节点
if (node.getRight() == perNode) {
System.out.println(node);
if (node == root)
return;
// 往上移动
perNode = node;
node = node.getParent();
} else {
// 若从左节点的进入，则找到右子树的最左节点
node = node.getRight();
while (node != null && node.getLeftType() == 0) {
node = node.getLeft();
}
}
}
}
}
// 二叉树进行中序线索化二叉树实现 Api
public void threadedNodes(HeroNode node) {
// 日常判空
if (node == null) {
return;
}
/**
* 个人理解：若没有左子树指向，即为空指向，若是左空，则指向前驱，若是右空，则指向后驱
*/
// 一、先线索化左子树
threadedNodes(node.getLeft());
// 二、线索化当前节点【难】
// 1、处理当前节点的前驱节点
// 举例：如上图的叶子节点 8 为例
// 若节点 8.left == null（既没有左子树可指向，则指向前驱节点）, 节点 8.leftType =1(指定为前驱类型标识)
if (node.getLeft() == null) {
// 让当前节点的左指针，指向前驱节点
node.setLeft(per);
// 修改当前节点做指针的类型，定义为前驱
node.setLeftType(1);
}
// 2、处理当前节点的后继节点(后继：就是在后面还得继续当前节点，所以还是这个节点在处理
if (per != null && per.getRight() == null) {
// 让前驱节点的右指针指向当前节点
per.setRight(node);
// 修改前驱节点的有指针类型
per.setRightType(1);
}
// 每处理一个节点，让当前节点是下一个节点的前驱节点(后移)
per = node;
// 三、线索化右子树
threadedNodes(node.getRight());
}
// 二叉树进行前序线索化二叉树实现 Api
public void perThreadedNodes(HeroNode node) {
// 日常判空
if (node == null) {
return;
}
/**
* 个人理解：若没有左子树指向，即为空指向，若是左空，则指向前驱，若是右空，则指向后驱 补充：若
* 是前序，递归语句在后面，则需要判断，中，后序只需要调整位置即可
*/
// 一、线索化当前节点
// 1.左指针为空，将要左指针指向前驱节点
if (node.getLeft() == null) {
// 让当前节点的左指针，指向前驱节点
node.setLeft(per);
// 修改当前节点做指针的类型，定义为前驱
node.setLeftType(1);
}
// 2.前一个节点的后继节点指向当前节点
if (per != null && per.getRight() == null) {
// 让前驱节点的右指针指向当前节点
per.setRight(node);
// 修改前驱节点的有指针类型
per.setRightType(1);
}
// 每处理一个节点，让当前节点是下一个节点的前驱节点(后移)
per = node;
// 二、线索化左子树
if (node.getLeftType() == 0)
perThreadedNodes(node.getLeft());
// 三、线索化右子树
if (node.getRightType() == 0)
perThreadedNodes(node.getRight());
}
// 二叉树进行后序线索化二叉树实现 Api
public void postThreadedNodes(HeroNode node) {
// 日常判空
if (node == null) {
return;
}
// 一、线索化左子树
postThreadedNodes(node.getLeft());
// 二、线索化右子树
postThreadedNodes(node.getRight());
// 三、线索化当前节点【难】
// 1、处理当前节点的前驱节点
// 举例：如上图的叶子节点 8 为例
// 若节点 8.left == null（既没有左子树可指向，则指向前驱节点）, 节点 8.leftType =1(指定为前驱类型标识)
if (node.getLeft() == null) {
// 让当前节点的左指针，指向前驱节点
node.setLeft(per);
// 修改当前节点做指针的类型，定义为前驱
node.setLeftType(1);
}
// 2、处理当前节点的后继节点(后继：就是在后面还得继续当前节点，所以还是这个节点在处理
if (per != null && per.getRight() == null) {
// 让前驱节点的右指针指向当前节点
per.setRight(node);
// 修改前驱节点的有指针类型
per.setRightType(1);
}
// 每处理一个节点，让当前节点是下一个节点的前驱节点(后移)
per = node;
}
}
// 节点
class HeroNode {
private int id;
private String name;
private HeroNode left;// 默认为 null
private HeroNode right;// 默认为 null
private HeroNode parent;// 父节点指针，为后序线索化使用
// 说明：
// 1、若 leftType == 0,表指向的是左子树；若 leftType ==1 ,表指向的是前驱节点
// 2、若 rightType == 0,表指向的是右子树；若 leftType ==1 ,表指向的是后驱节点
private int leftType;// 默认 0
private int rightType;
public HeroNode(int id, String name) {
super();
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
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;
}
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 getParent() {
return parent;
}
public void setParent(HeroNode parent) {
this.parent = parent;
}
@Override
public String toString() {
return "HeroNode [id=" + id + ", name=" + name + "]";
}
}
7、输出结果：
image.png
8、前序、中序、后序线索化比较
- 前序线索化二叉树：
1、前序线索化二叉树遍历相对最容易理解，实现起来也比较简单。
2、由于前序遍历的顺序是：
根左右，所以从根节点开始，沿着左子树进行处理，当子节点的left指针类型是线索时，说明到了最左子节点，然后处理子节点的right指针指向的节点，可能是右子树，也可能是后继节点，无论是哪种类型继续按照上面的方式（先沿着左子树处理，找到子树的最左子节点，然后处理right指针指向），以此类推，直到节点的right指针为空，说明是最后一个，遍历完成。- 中序线索化二叉树：
1、中序线索化二叉树的网上相关介绍最多。
2、中序遍历的顺序是：
左根右，因此第一个节点一定是最左子节点，先找到最左子节点，依次沿着right指针指向进行处理（无论是指向子节点还是指向后继节点），直到节点的right指针为空，说明是最后一个，遍历完成。- 后序线索化二叉树：
1、后序遍历线索化二叉树最为复杂，通用的二叉树数节点存储结构不能够满足后序线索化，因此我们扩展了节点的数据结构，增加了父节点的指针。
2、后序的遍历顺序是：
左右根，先找到最左子节点，沿着right后继指针处理，当right不是后继指针时，并且上一个处理节点是当前节点的右节点，则处理当前节点的右子树，
遍历终止条件是：当前节点是root节点，并且上一个处理的节点是root的right节点。
9、参考文章
https://blog.csdn.net/jisuanjiguoba/article/details/81092812
