节点代码
class Node {
int value;
Node left;//左子树
Node right;//右子树
Node pre;//父节点
//左节点属性，若值为0，其指向的是子树，若值为1，其指向的是前序节点
int leftType;
//右节点属性，若值为0，其指向的是子树，若值为1，其指向的是后继节点
int rightType;
public Node(int value) {
this.value = value;
}
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 int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public Node getPre() {
return pre;
}
public void setPre(Node pre) {
this.pre = pre;
}
@Override
public String toString() {
return "Node{" + "value=" + value + '}';
}
}
前、中、后序线索化以及遍历代码
public class ThreadedBinaryTree {
//二叉树的根节点
Node root;
//用于在线索化时保存前一个节点
Node pre;
/*
* 前序线索化
* @author Eleven
* @return void
* @date 16:30 2021/11/21
*/
public void preThreaded() {
this.preThreaded(root);
}
private void preThreaded(Node node) {
if (node == null) {
return;
}
//对本节点进行线索化
threaded(node);
//若该节点的左节点类型不为1（防止成环）就向左递归
if (node.leftType != 1) {
preThreaded(node.left);
}
//若该节点的右节点类型不为1（防止成环）就向右递归
if (node.rightType != 1) {
preThreaded(node.right);
}
}
/*
* 中序线索化
* @author Eleven
* @return void
* @date 16:27 2021/11/21
*/
public void infixThreaded() {
this.infixThreaded(root);
}
private void infixThreaded(Node node) {
if (node == null) {
return;
}
//向左子树遍历
infixThreaded(node.left);
//对本节点进行线索化
threaded(node);
//向左子树遍历
infixThreaded(node.right);
}
/*
* 后序线索化
* @author Eleven
* @return void
* @date 16:59 2021/11/21
*/
public void postThreaded() {
this.postThreaded(root);
}
private void postThreaded(Node node) {
if (node == null) {
return;
}
//先向左（右）子树进行递归进行线索化
postThreaded(node.left);
postThreaded(node.right);
//再处理本节点，进行线索化
threaded(node);
}
/*
* 对传入节点进行线索化
* @author Eleven
* @param node
* @return void
* @date 19:45 2021/11/21
*/
private void threaded(Node node) {
//若该节点的左子树节点为空，就将左子树节点指向前一个节点
//并将左子树节点的属性置1
if (node.left == null) {
node.left = pre;
node.setLeftType(1);
}
//对前一个节点的右节点进行线索化
//若前一个节点的右节点为null，就将前一个节点的右节点指向该节点
if (pre != null && pre.right == null) {
pre.right = node;
pre.setRightType(1);
}
//将该节点赋给pre记录为下一个节点的前节点
pre = node;
}
/*
* 对前序线索化后的二叉树进行遍历
* @author Eleven
* @return void
* @date 17:19 2021/11/21
*/
public void preThreadedList() {
Node node = root;
if (root == null) {
System.out.println("该树为空树");
return;
}
while (node != null) {
System.out.println(node);
while (node.left != null && node.leftType != 1) {
System.out.println(node.left);
node = node.left;
}
node = node.right;
}
}
/*
* 对中序线索化后的二叉树进行遍历
* @author Eleven
* @return void
* @date 19:20 2021/11/21
*/
public void infixThreadedList() {
Node node = root;
if (root == null) {
System.out.println("该树为空树");
return;
}
while(node != null){
while (node.leftType != 1) {
node = node.left;
}
System.out.println(node);
while (node.right != null && node.rightType == 1) {
node = node.right;
System.out.println(node);
}
node = node.right;
}
}
/*
* 对后序线索化后的二叉树进行遍历
* @author Eleven
* @return void
* @date 19:20 2021/11/21
*/
public void postThreadedList() {
Node node = root;
if (root == null) {
System.out.println("该树为空树");
return;
}
while(node != null){
//寻找下一个后续节点
//若是首次进入循环为寻找需要遍历的第一个节点
while (node.leftType != 1) {
node = node.left;
}
//找到后续节点，直接输出
System.out.println(node);
//根据后续线索进行遍历
while (node.right != null && node.rightType == 1) {
node = node.right;
System.out.println(node);
}
//若当前节点的父节点为空，即该节点为root节点，说明后序线索遍历已完成
// 将node置为空，结束遍历
//若父节点不为null，说明该节点的父节点的左子树已遍历完成，将后续节点
//指向父节点的右子树，进行右子树的遍历
node = node.pre==null ? null : node.pre.right;
}
}
}
测试代码
public class ThreadedBinaryTreeTest {
Node root, node1, node2, node3, node4, node5;
ThreadedBinaryTree tbt;
@Before
public void setUp() {
root = new Node(1);
node1 = new Node(3);
node2 = new Node(6);
node3 = new Node(8);
node4 = new Node(10);
node5 = new Node(14);
root.left = node1;
root.right = node2;
node1.left = node3;
node1.right = node4;
node1.pre = root;
node2.left = node5;
node2.pre = root;
node3.pre = node1;
node4.pre = node1;
node5.pre = node2;
tbt = new ThreadedBinaryTree();
tbt.root = root;
}
@Test
public void infixThreaded() {
tbt.infixThreaded();
System.out.println(node5.left);
System.out.println(node5.right);
}
@Test
public void preThreaded() {
tbt.preThreaded();
System.out.println(node5.left);
System.out.println(node5.right);
}
@Test
public void postThreaded() {
tbt.postThreaded();
System.out.println(node3.left);
System.out.println(node3.right);
}
@Test
public void preThreadedList() {
tbt.preThreaded();
tbt.preThreadedList();
}
@Test
public void infixThreadedList() {
tbt.infixThreaded();
tbt.infixThreadedList();
}
@Test
public void postThreadedList() {
tbt.postThreaded();
tbt.postThreadedList();
}
}
