java实现线索化二叉树(中序线索化)的创建以及遍历删除等操作

以你之姓@ 2023-03-14 10:43 19阅读 0赞

## 源代码 ##

public class ThreadedBiTreeDemo{ 
    
    	public static void main(String[] args) { 
    		ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
    		TNode root = new TNode(1, "tom");
    		TNode node2 = new TNode(3, "jack");
    		TNode node3 = new TNode(6, "smith");
    		TNode node4 = new TNode(8, "mary");
    		TNode node5 = new TNode(10, "king");
    		TNode node6 = new TNode(14, "dim");
    
    		root.setLeft(node2);
    		root.setRight(node3);
    		node2.setLeft(node4);
    		node2.setRight(node5);
    		node3.setLeft(node6);
    		
    		threadedBinaryTree.setRoot(root);
    		threadedBinaryTree.threadedNodes();
    		
    		System.out.println(node5.getRight());
    		threadedBinaryTree.threadedList();
    	}
    
    }
    
    class ThreadedBinaryTree{ 
    	// 根节点
    	private TNode root;
    	// 保存每个节点的前驱节点
    	private TNode pre = null;
    	
    	public void setRoot(TNode root) { 
    		this.root = root;
    	}
    	
    	// 遍历线索化二叉树
    	public void threadedList() { 
    		// 从root 节点开始
    		TNode node = root;
    		
    		while(node != null) { 
    			// 找到第一个有前驱节点的节点
    			while(node.getLeftType() == 0) { 
    				node = node.getLeft();
    			}
    			
    			System.out.println(node);
    			
    			// 如果当前节点的有后继节点，就一直输出 
    			while(node.getRightType() == 1) { 
    				node = node.getRight();
    				System.out.println(node);
    			}
    			// 否则，进入当前节点的右子树
    			node = node.getRight();
    		}
    	}
    	
    	public void threadedNodes() { 
    		this.threadedNodes(root);
    	}
    	
    	// 中序线索化
    	public void threadedNodes(TNode node) { 
    		if(node == null) { 
    			return;
    		}
    		
    		threadedNodes(node.getLeft());
    		if(node.getLeft() == null) { 
    			node.setLeft(pre);
    			node.setLeftType(1);
    		}
    		
    		if(pre != null && pre.getRight() == null) { 
    			pre.setRight(node);
    			pre.setRightType(1);
    		}
    		
    		pre = node;
    		threadedNodes(node.getRight());
    		
    		
    	}
    	
    	// 删除叶子节点或子树
    	public void delNode(int no) { 
    		if(this.root != null) { 
    			// 如果根节点是要删除的，直接将根节点置为空
    			if(this.root.getNo() == no) { 
    				this.root = null;
    			}else { 
    				this.root.delTNode(no);
    			}
    		}else { 
    			System.out.println("这是一棵空树!");
    		}
    	}
    	
    	// 前序遍历 
    	public void preOrder() { 
    		if(this.root != null) { 
    			this.root.preOrder();
    		}else { 
    			System.out.println("根节点为空，无法遍历!");
    		}
    	}
    	
    	public void infixOrder() { 
    		if(this.root != null) { 
    			this.root.infixOrder();
    		}else { 
    			System.out.println("根节点为空，无法遍历!");
    		}
    	}
    	
    	public void postOrder() { 
    		if(this.root != null) { 
    			this.root.postOrder();
    		}else { 
    			System.out.println("根节点为空，无法遍历!");
    		}
    	}
    	
    	// 前序查找 
    	public TNode preOrderSearch(int no) { 
    		if(this.root != null) { 
    			return this.root.preOrderSearch(no);
    		}
    		return null;
    	}
    	// 中序查找 
    	public TNode infixOrderSearch(int no) { 
    		if(this.root != null) { 
    			return this.root.infixOrderSearch(no);
    		}
    		return null;
    	}
    	// 后序查找 
    	public TNode postOrderSearch(int no) { 
    		if(this.root != null) { 
    			return this.root.postOrderSearch(no);
    		}
    		return null;
    	}
    	
    }
    
    
    class TNode{ 
    	private int no;
    	private String name;
    	private TNode left;
    	private TNode right;
    	// 0:左右子树 1:前驱/后继节点
    	private int leftType;
    	private int rightType;
    	
    	/** * * @param no * @param name */
    	public TNode(int no,String name) { 
    		this.no = no;
    		this.name = name;
    	}
    	
    	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 getNo() { 
    		return no;
    	}
    	public void setNo(int no) { 
    		this.no = no;
    	}
    	public String getName() { 
    		return name;
    	}
    	public void setName(String name) { 
    		this.name = name;
    	}
    	public TNode getLeft() { 
    		return left;
    	}
    	public void setLeft(TNode left) { 
    		this.left = left;
    	}
    	public TNode getRight() { 
    		return right;
    	}
    	public void setRight(TNode right) { 
    		this.right = right;
    	}
    	@Override
    	public String toString() { 
    		return "TNode [no=" + no + ", name=" + name + "]";
    	}
    	
    	// 前序遍历
    	public void preOrder() { 
    		// 首先输出当前节点
    		System.out.println(this);
    		// 如果左子节点不为空，递归前序遍历左子节点
    		if(this.left != null) { 
    			this.left.preOrder();
    		}
    		// 同理如果右子节点不为空，递归前序遍历右子节点
    		if(this.right != null) { 
    			this.right.preOrder();
    		}
    	}
    	// 中序遍历 
    	public void infixOrder() { 
    		
    		// 如果左子节点不为空，递归前序遍历左子节点
    		if(this.left != null) { 
    			this.left.infixOrder();
    		}
    		// 输出当前节点
    		System.out.println(this);
    		// 同理如果右子节点不为空，递归前序遍历右子节点
    		if(this.right != null) { 
    			this.right.infixOrder();
    		}
    	}
    	
    	// 后序遍历 
    	public void postOrder() { 
    		
    		// 如果左子节点不为空，递归前序遍历左子节点
    		if(this.left != null) { 
    			this.left.postOrder();
    		}
    		
    		// 同理如果右子节点不为空，递归前序遍历右子节点
    		if(this.right != null) { 
    			this.right.postOrder();
    		}
    		// 输出当前节点
    		System.out.println(this);
    	}
    	
    	// 前序查找 
    	public TNode preOrderSearch(int no) { 
    		TNode target = null;
    		if(this.no == no) { 
    			// 如果当前节点就是，直接返回
    			return this;
    		}
    		
    		// 如果左子节点为空，会抛出空指针异常
    		if(this.left != null) { 
    			target = this.left.preOrderSearch(no);
    		}
    		// 如果在左边找到了，返回目标
    		if(target != null) { 
    			return target;
    		}
    		
    		if(this.right != null) { 
    			target = this.right.preOrderSearch(no);
    		}
    		// 在右边，无论找没找到，都返回
    		return target;
    	}
    	// 中序查找 
    	public TNode infixOrderSearch(int no) { 
    		TNode target = null;
    		
    		if(this.left != null) { 
    			target = this.left.infixOrderSearch(no);
    		}
    		if(target != null) { 
    			return target;
    		}
    		
    		if(this.no == no) { 
    			return this;
    		}
    		
    		if(this.right != null) { 
    			target = this.right.infixOrderSearch(no);
    		}
    		return target;
    	}
    	// 后序查找 
    	public TNode postOrderSearch(int no) { 
    		TNode target = null;
    		
    		if(this.left != null) { 
    			target = this.left.postOrderSearch(no);
    		}
    		if(target != null) { 
    			return target;
    		}
    		
    		if(this.right != null) { 
    			target = this.right.postOrderSearch(no);
    		}
    		if(target != null) { 
    			return target;
    		}
    		
    		if(this.no == no) { 
    			return this;
    		}
    		return null;
    		
    	}
    	// 删除节点
    	public void delTNode(int no) { 
    		// 判断左子节点是不是要删除的
    		if(this.left != null && this.left.no == no) { 
    			this.left = null;
    			return ;
    		}
    		// 判断右子节点是不是要删除的
    		if(this.right != null && this.right.no == no) { 
    			this.right = null;
    			return;
    		}
    		
    		// 如果左右子节点都不是，递归遍历左右子节点
    		if(this.left != null) { 
    			this.left.delTNode(no);
    		}
    		if(this.right != null) { 
    			this.right.delTNode(no);
    		}
    		
    	}
    	
    }