程序员：数据结构和算法，中序线索化二叉树
1、中序线索化二叉树
创建如上的二叉树，线索化二叉树时，根据指定的遍历方式得到的节点的访问顺序，一个节点前面的节点，叫做前驱节点，一个节点后面的节点，叫做后继节点。
线索化二叉树的规则：
按照某一遍历规则。记录当前节点（cur），上次访问的节点（pre）。
① 如果当前节点的左孩子为空 （cur.leftNode == null），就让当前节点的左指针指向它的前驱节点 ，并把当前节点左指针的模式修改为线索类型 （cur.leftNode = pre ，cur.leftType = 1）。
② 如果当前节点的前驱节点的右孩子为空 （pre.rightNode == null），就让当前节点的前驱节点的右指针指向当前节点，并把前驱节点的右指针修改为线索类型 （pre.rightNode = cur ,pre.rightType = 1）。
代码实现：
/**
* 线索二叉树节点
*/
public class ThreadedNode {
//节点的权
int value;
//节点的左右孩子节点
ThreadedNode leftNode;
ThreadedNode rightNode;
//表示指针的类型
int leftType;
int rightType;
//设置节点的权值
public ThreadedNode(int value) {
this.value = value;
}
//设置节点的左右孩子节点
public void setLeftNode(ThreadedNode leftNode) {
this.leftNode = leftNode;
}
public void setRightNode(ThreadedNode rightNode) {
this.rightNode = rightNode;
}
//获取节点的左右孩子节点
public ThreadedNode getLeftNode() {
return this.leftNode;
}
public ThreadedNode getRightNode() {
return this.rightNode;
}
public void midShow() {
//先遍历左子树
if (this.leftNode != null){
leftNode.midShow();
}
//打印当前节点的权值
System.out.println(this.value);
if (this.rightNode != null){
rightNode.midShow();
}
}
}
/**
* 线索二叉树
*/
public class ThreadedBinaryTree {
//树的根节点
ThreadedNode rootNode;
//用于临时存储前驱节点
ThreadedNode pre = null;
//设置二叉树的根节点
public void setRootNode(ThreadedNode rootNode) {
this.rootNode = rootNode;
}
//获取二叉树的根节点
public ThreadedNode getRootNode() {
return this.rootNode;
}
//中序线索化二叉树
public void threadNode() {
threadNodes(rootNode);
}
private void threadNodes(ThreadedNode node) {
//当前节点为空，直接返回
if (node == null) {
return;
}
//处理左子树
threadNodes(node.leftNode);
//处理前驱节点
if (pre != null && node.leftNode == null) {
//当前节点的左指针指向前驱节点
node.leftNode = pre;
//修改节点为线索模式
node.leftType = 1;
}
//处理前驱节点的右指针
if (pre != null && pre.rightNode == null) {
pre.rightNode = node;
pre.rightType = 1;
}
//当前节点就是下一个节点的前驱节点
pre = node;
//处理右子树
threadNodes(node.rightNode);
}
//中序遍历二叉树
public void midShow() {
if (this.rootNode == null) {
return;
} else {
rootNode.midShow();
}
}
}
/**
* 测试类
*/
public class TestThreadedBinaryTree {
public static void main(String[] args) {
//1、创建二叉树
ThreadedBinaryTree binaryTree = new ThreadedBinaryTree();
ThreadedNode rootNode = new ThreadedNode(1);
binaryTree.setRootNode(rootNode);
ThreadedNode leftNode = new ThreadedNode(2);
ThreadedNode rightNode = new ThreadedNode(3);
rootNode.setLeftNode(leftNode);
rootNode.setRightNode(rightNode);
leftNode.setLeftNode(new ThreadedNode(4));
ThreadedNode five = new ThreadedNode(5);
leftNode.setRightNode(five);
rightNode.setLeftNode(new ThreadedNode(6));
rightNode.setRightNode(new ThreadedNode(7));
//2、中序遍历二叉树
System.out.println("中序遍历结果：");
binaryTree.midShow();
System.out.println("------------------------");
binaryTree.threadNode();
ThreadedNode beforeNode = five.leftNode;
System.out.println("节点5的前驱节点："+beforeNode.value);
ThreadedNode afterNode = five.rightNode;
System.out.println("节点5的后继节点："+afterNode.value);
}
}
