Java实现前序、中序、后序线索化二叉树及遍历

小灰灰 2023-07-17 06:16 1阅读 0赞

[*点击进入尚硅谷数据结构和算法Java代码导航*][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() {
        
    		turnToPre(this.root);
    	}
    	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() {
        
    		turnToIn(this.root);
    	}
    	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) {
        
    				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() {
        
    		turnToPost(this.root);
    	}
    	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();
    		tbt.root = A;
    		A.left = B;
    		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

[Java]: https://blog.csdn.net/weixin_44963741/article/details/105228982