参考:https://www.jianshu.com/p/3965a6e424f5
线索二叉树节点:
package demo7;
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 void frontShow() {
//先遍历当前节点的内容
System.out.println(value);
//左节点
if(leftNode!=null) {
leftNode.frontShow();
}
//右节点
if(rightNode!=null) {
rightNode.frontShow();
}
}
//中序遍历
public void midShow() {
//左子节点
if(leftNode!=null) {
leftNode.midShow();
}
//当前节点
System.out.println(value);
//右子节点
if(rightNode!=null) {
rightNode.midShow();
}
}
//后序遍历
public void afterShow() {
//左子节点
if(leftNode!=null) {
leftNode.afterShow();
}
//右子节点
if(rightNode!=null) {
rightNode.afterShow();
}
//当前节点
System.out.println(value);
}
//前序查找
public ThreadedNode frontSearch(int i) {
ThreadedNode target=null;
//对比当前节点的值
if(this.value==i) {
return this;
//当前节点的值不是要查找的节点
}else {
//查找左儿子
if(leftNode!=null) {
//有可能可以查到,也可以查不到,查不到的话,target还是一个null
target = leftNode.frontSearch(i);
}
//如果不为空,说明在左儿子中已经找到
if(target!=null) {
return target;
}
//查找右儿子
if(rightNode!=null) {
target=rightNode.frontSearch(i);
}
}
return target;
}
//删除一个子树
public void delete(int i) {
ThreadedNode parent = this;
//判断左儿子
if(parent.leftNode!=null&&parent.leftNode.value==i) {
parent.leftNode=null;
return;
}
//判断右儿子
if(parent.rightNode!=null&&parent.rightNode.value==i) {
parent.rightNode=null;
return;
}
//递归检查并删除左儿子
parent=leftNode;
if(parent!=null) {
parent.delete(i);
}
//递归检查并删除右儿子
parent=rightNode;
if(parent!=null) {
parent.delete(i);
}
}
}
线索二叉树:
package demo7;
public class ThreadedBinaryTree {
ThreadedNode root;
//用于临时存储前驱节点
ThreadedNode pre=null;
//遍历线索二叉树
public void threadIterate() {
//用于临时存储当前遍历节点
ThreadedNode node = root;
while(node!=null) {
//循环找到最开始的节点
while(node.leftType==0) {
node=node.leftNode;
}
//打印当前节点的值
System.out.println(node.value);
//如果当前节点的右指针指向的是后继节点,可能后继节点还有后继节点、
while(node.rightType==1) {
node=node.rightNode;
System.out.println(node.value);
}
//替换遍历的节点
node=node.rightNode;
}
}
//设置根节点
public void setRoot(ThreadedNode root) {
this.root = root;
}
//中序线索化二叉树
public void threadNodes() {
threadNodes(root);
}
public void threadNodes(ThreadedNode node) {
//当前节点如果为null,直接返回(递归的结束条件)
if(node==null) {
return;
}
//处理左子树
threadNodes(node.leftNode);
//处理前驱节点
if(node.leftNode==null){
//让当前节点的左指针指向前驱节点
node.leftNode=pre;
//改变当前节点左指针的类型
node.leftType=1;
}
//处理前驱的右指针,如果前驱节点的右指针是null(没有指下右子树)
if(pre!=null&&pre.rightNode==null) {
//让前驱节点的右指针指向当前节点
pre.rightNode=node;
//改变前驱节点的右指针类型
pre.rightType=1;
}
//每处理一个节点,当前节点是下一个节点的前驱节点
pre=node;
//处理右子树
threadNodes(node.rightNode);
}
//获取根节点
public ThreadedNode getRoot() {
return root;
}
//前序遍历
public void frontShow() {
if(root!=null) {
root.frontShow();
}
}
//中序遍历
public void midShow() {
if(root!=null) {
root.midShow();
}
}
//后序遍历
public void afterShow() {
if(root!=null) {
root.afterShow();
}
}
//前序查找
public ThreadedNode frontSearch(int i) {
return root.frontSearch(i);
}
//删除子树
public void delete(int i) {
if(root.value==i) {
root=null;
}else {
root.delete(i);
}
}
}
测试线索二叉树:
package demo7;
public class TestThreadedBinaryTree {
public static void main(String[] args) {
//创建一颗树
ThreadedBinaryTree binTree = new ThreadedBinaryTree();
//创建一个根节点
ThreadedNode root = new ThreadedNode(1);
//把根节点赋给树
binTree.setRoot(root);
//创建一个左节点
ThreadedNode rootL = new ThreadedNode(2);
//把新创建的节点设置为根节点的子节点
root.setLeftNode(rootL);
//创建一个右节点
ThreadedNode rootR = new ThreadedNode(3);
//把新创建的节点设置为根节点的子节点
root.setRightNode(rootR);
//为第二层的左节点创建两个子节点
rootL.setLeftNode(new ThreadedNode(4));
ThreadedNode fiveNode = new ThreadedNode(5);
rootL.setRightNode(fiveNode);
//为第二层的右节点创建两个子节点
rootR.setLeftNode(new ThreadedNode(6));
rootR.setRightNode(new ThreadedNode(7));
//中序遍历树
binTree.midShow();
System.out.println("===============");
//中前线索化二叉树
binTree.threadNodes();
binTree.threadIterate();
}
}