Java实现前序、中序、后序线索化⼆叉树及遍历1.1 前序线索化⼆叉树
public void turnToPre(ThreadedNode temp){
if(temp == null){
return;
}
if(temp.left == null){
temp.left = pre;
temp.leftType =true;
}
if(pre != null && pre.right == null){
pre.right = temp;
pre.rightType =true;
}
pre = temp;
//只有当类型为false时才进⼊，否则进⼊死循环
if(!temp.leftType){
turnToPre(temp.left);
}
if(!temp.rightType){
turnToPre(temp.right);
}
}
1.2 前序遍历线索化⼆叉树
//前序遍历线索⼆叉树
public void preOrderThreaded(){
ThreadedNode temp = root;
while(temp != null){
System.out.print(temp.data +" ");
//如果存在左⼦节点就往左⾛，否则往右⾛，此时右指针⼀定是前序遍历的下⼀个节点
if(!temp.leftType){
temp = temp.left;
}else{
temp = temp.right;
}
}
}
2.1 中序线索化⼆叉树
public void turnToIn(ThreadedNode temp){
if(temp == null){
return;
}
turnToIn(temp.left);
if(temp.left == null){
temp.left = pre;
temp.leftType =true;
}
if(pre != null && pre.right == null){
pre.right = temp;
pre.rightType =true;
}
pre = temp;
turnToIn(temp.right);
}
2.2 中序遍历线索化⼆叉树算法⼀
//中序遍历线索⼆叉树算法⼀
public void inOrderThreaded1(){
ThreadedNode temp = root;
while(temp != null){
while(!temp.leftType){
temp = temp.left;
}
System.out.print(temp.data +" ");
while(temp.rightType){
temp = temp.right;
System.out.print(temp.data +" ");
}
temp = temp.right;
}
}
2.3 中序遍历线索化⼆叉树算法⼆
//中序遍历线索⼆叉树算法⼆
public void inOrderThreaded2(){
ThreadedNode temp = root;
while(temp != null){
if(!temp.leftType){
temp = temp.left;
}else{
System.out.print(temp.data +" ");
//如果temp的右指针是线索指针，则需要先⾛⼀步，否则会陷⼊死循环
if(temp.rightType){
temp = temp.right;
System.out.print(temp.data +" ");
}
temp = temp.right;
}
}
}
3.3 后序遍历需要在节点中加上指向⽗节点的指针，感觉没必要，先留个坑。完整代码
package tree;
class ThreadedNode{
String data;
ThreadedNode left;
ThreadedNode right;
boolean leftType =false;
boolean rightType =false;
public ThreadedNode(String t){
this.data = t;
}
}
/
/线索化⼆叉树
public class ThreadedBinaryTree {先序中序后序遍历二叉树
private ThreadedNode root;
private ThreadedNode pre;
//转化为前序线索化⼆叉树
public void turnToPre(){
);
}
public void turnToPre(ThreadedNode temp){
public void turnToPre(ThreadedNode temp){
if(temp == null){
return;
}
if(temp.left == null){
temp.left = pre;
temp.leftType =true;
}
if(pre != null && pre.right == null){
pre.right = temp;
pre.rightType =true;
}
pre = temp;
/
/只有当类型为false时才进⼊，否则进⼊死循环
if(!temp.leftType){
turnToPre(temp.left);
}
if(!temp.rightType){
turnToPre(temp.right);
}
}
//前序遍历线索⼆叉树
public void preOrderThreaded(){
ThreadedNode temp = root;
while(temp != null){
System.out.print(temp.data +" ");
//如果存在左⼦节点就往左⾛，否则往右⾛，此时右指针⼀定是前序遍历的下⼀个节点if(!temp.leftType){
temp = temp.left;
}else{
temp = temp.right;
}
}
}
//转化为中序线索化⼆叉树
public void turnToIn(){
);
}
public void turnToIn(ThreadedNode temp){
if(temp == null){
return;
}
turnToIn(temp.left);
if(temp.left == null){
temp.left = pre;
temp.leftType =true;
}
if(pre != null && pre.right == null){
pre.right = temp;
pre.rightType =true;
}
pre = temp;
turnToIn(temp.right);
}
//中序遍历线索⼆叉树算法⼀
//中序线索⼆叉树遍历
public void inOrderThreaded1(){
ThreadedNode temp = root;
while(temp != null){
while(!temp.leftType){
temp = temp.left;
}
System.out.print(temp.data +" ");
while(temp.rightType){
while(temp.rightType){
temp = temp.right;
System.out.print(temp.data +" ");
}
temp = temp.right;
}
}
//中序遍历线索⼆叉树算法⼆
public void inOrderThreaded2(){
ThreadedNode temp = root;
while(temp != null){
if(!temp.leftType){
temp = temp.left;
}else{
System.out.print(temp.data +" ");
if(temp.rightType){
temp = temp.right;
System.out.print(temp.data +" ");
}
temp = temp.right;
}
}
}
//转化为后序线索⼆叉树
public void turnToPost(){
);
}
public void turnToPost(ThreadedNode temp){
if(temp == null){
return;
}
turnToPost(temp.left);
turnToPost(temp.right);
if(temp.left == null){
temp.left = pre;
temp.leftType =true;
}
if(pre != null && pre.right == null){
pre.right = temp;
pre.rightType =true;
}
pre = temp;
}
//后序遍历线索⼆叉树
public void postOrderThreaded(){
}
public static void main(String[] args){
// TODO Auto-generated method stub
ThreadedNode A =new ThreadedNode("A");
ThreadedNode B =new ThreadedNode("B");
ThreadedNode C =new ThreadedNode("C");
ThreadedNode D =new ThreadedNode("D");
ThreadedNode E =new ThreadedNode("E");
ThreadedNode F =new ThreadedNode("F");
ThreadedNode G =new ThreadedNode("G");
ThreadedNode H =new ThreadedNode("H");
ThreadedNode I =new ThreadedNode("I");
ThreadedBinaryTree tbt =new ThreadedBinaryTree();  = A;
A.left = B;
A.right = C;
A.right = C;
C.left = I;
B.left = D;
B.right = E;
D.left = F;
D.right = G;
E.right = H;
tbt.turnToPost();
System.out.println(I.right.data); }
}
//前序 A B D F G E H C I
/
/中序 F D G B E H A I C
//后序 F G D H E B I C A