基于Java实现的基本二叉树

亦凉 2022-06-16 06:20 48阅读 0赞

## 基于Java实现的基本二叉树 ##

### 废话不多说，直接上代码: ###

package zychaowill.datastructure.tree;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    /**
     * 
     * @Description 基本二叉排序树
     * @author Zychaowill
     * @date 2017/04/22
     * @version V1.0
     */
    public class BinNode {
    	// 左右孩子结点
    	private BinNode lchild, rchild;
    	// 当前结点的值（可按需更换为T）
    	private int value;
    	
    	public BinNode() {}
    	// 通过左右孩子和新值构造新增结点
    	public BinNode(BinNode lchild, BinNode rchild, int value) {
    //		super();
    		this.lchild = lchild;
    		this.rchild = rchild;
    		this.value = value;
    	}
    	
    	/**
    	 * @description 添加新节点（左孩子/右孩子），采用左孩子的值小于父节点的值，
    	 * 				右孩子的值大于等于父节点的值
    	 * @param value 新节点的值
    	 */
    	public void addChild(int value) {
    		if (value < this.value) { // 向左子树添加新节点
    			if (lchild != null) { // 若左子树不为空，则递归检测左子树
    				lchild.addChild(value);
    			} else { // 若左子树为空，则创建新节点作为父节点的左孩子
    				lchild = new BinNode(null, null, value);
    			}
    		} else { // 向右子树添加新节点
    			if (rchild != null) { // 若右子树不为空，则递归检测右子树
    				rchild.addChild(value);
    			} else { // 若右子树为空，则创建新节点作为父节点的右孩子
    				rchild = new BinNode(null, null, value);
    			}
    		}
    	}
    	
    	/**
    	 * @description 通过递归实现的中序遍历输出树所有结点
    	 * @param root 二叉树的根节点或而查询树的某一个子树结点
    	 */
    	public static void printTree(BinNode root) {
    		if (root != null) {
    			printTree(root.lchild);
    			System.out.print(root.value);
    			printTree(root.rchild);
    		}
    	}
    	
    	/**
    	 * @description 通过递归实现的先序遍历输出树的所有结点
    	 * @param root 二叉树的根节点或而查询树的某一个子树结点
    	 */
    	public static void preOrder(BinNode root) {
    		if (root != null) {
    			System.out.print(root.value);
    			preOrder(root.lchild);
    			preOrder(root.rchild);
    		}
    	}
    	
    	/**
    	 * @description 基于栈实现的先序遍历输出树的所有结点
    	 * 				栈的特性: LIFO（后进先出）
    	 * @param root 二叉树的根节点或而查询树的某一个子树结点
    	 */
    	public static void preOrderStack(BinNode root) {
    		if (root != null) {
    			Stack<BinNode> stack = new Stack<>();
    			stack.push(root);
    			
    			BinNode node;
    			while (!stack.isEmpty()) {
    				node = stack.pop();
    				System.out.print(node.value);
    				
    				if (node.rchild != null) {
    					stack.push(node.rchild);
    				}
    				if (node.lchild != null) {
    					stack.push(node.lchild);
    				}
    			}
    		}
    	}
    	
    	/**
    	 * @description 基于队列实现的先序遍历输出树的所有结点
    	 * 				队列的特性: FIFO（先进先出）
    	 * @param root 二叉树的根节点或而查询树的某一个子树结点
    	 */
    	public static void readLevel(BinNode root) {
    		if (root != null) {
    			Queue<BinNode> queue = new LinkedList<>();
    			queue.add(root);
    			
    			BinNode node;
    			while (!queue.isEmpty()) {
    				node = queue.poll();
    				System.out.print(node.value);
    				
    				if (node.lchild != null) {
    					queue.add(node.lchild);
    				}
    				if (node.rchild != null) {
    					queue.add(node.rchild);
    				}
    			}
    		}
    	}
    	
    	/**
    	 * Start iterator level reading.
    	 * @description 基于队列实现的先序遍历输出树的所有结点
    	 * 				队列的特性: FIFO（先进先出）
    	 * @param root  二叉树的根节点或而查询树的某一个子树结点
    	 * @param level 二叉树的层次（深度）
    	 */
    	private static void levelIterator(BinNode root, int level) {
    		if (root == null || level < 1) {
    			return;
    		}
    		
    		if (root != null) {
    			if (level == 1) {
    				System.out.print(root.value);
    			}
    			
    			levelIterator(root.lchild, level - 1);
    			levelIterator(root.rchild, level - 1);
    		}
    	}
    	
    	/**
    	 * @description 通过递归求取二叉树的层次（深度），为levelIterator(BinNode root, int level)做准备
    	 * @param root
    	 * @return
    	 */
    	public static int depth(BinNode root) {
    		if (root != null) {
    			int ldepth = depth(root.lchild);
    			int rdepth = depth(root.rchild);
    			
    			return (ldepth > rdepth ? ldepth + 1 : rdepth + 1);
    		}
    		return 0;
    	}
    	
    	/**
    	 * @description 递归实现二叉树的层次遍历的主控制器，调用depth(BinNode root)
    	 * 				和levelInterator(BinNode root, int level)实现
    	 * @param root
    	 */
    	public static void iteratorLevel(BinNode root) {
    		int depth = depth(root);
    		
    		for (int i = 1; i <= depth; i++) {
    			levelIterator(root, i);
    		}
    	}
    	/**
    	 * End iterator level reading.
    	 */
    	
    	// test
    	public static void main(String[] args) {
    		int[] values = {4, 1, 3, 2, 5, 6, 7};
    		BinNode root = new BinNode(null, null, values[0]);
    		
    		for (int i = 1; i < values.length; i++) {
    			root.addChild(values[i]);
    		}
    		
    		printTree(root);
    		System.out.println();
    		preOrder(root);
    		System.out.println();
    		preOrderStack(root);
    		System.out.println();
    		
    		readLevel(root);
    		System.out.println();
    		iteratorLevel(root);
    		System.out.println();
    	}
    }