二叉树：实现前序遍历、中序遍历、后序遍历、层次遍历、遍历二叉树的节点并输出、统计输出节点个数、二叉树的一般节点查找、查找最大节点

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分 。
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点 。

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class binarytree {
	public static class TreeNode 
	{
		 int value;
		 TreeNode left_Node;
		 TreeNode right_Node;
		 
		public TreeNode(int value) 
		{
			this.value=value;
			this.left_Node=null;
			this.right_Node=null;
		 }
	
		public String toString() {
	        
	        return "{叶子 value:"+ this.value+"}";
	    }
	}

	public TreeNode rootNode;
	public static int count =1;
	public void Add_Node_To_Tree(int value) {
		if (rootNode==null) {
			rootNode=new TreeNode(value);
			return;
		}
		TreeNode currentNode=rootNode;
		while (true) 
		{
			if (value<currentNode.value) 
			{
				if (currentNode.left_Node==null)
				{
					currentNode.left_Node=new TreeNode(value);
					return;
				}
				else 
					currentNode=currentNode.left_Node;
			}
			else 
			{
				if (currentNode.right_Node==null) 
				{
					currentNode.right_Node=new TreeNode(value);
					return;
				}
				else
					currentNode=currentNode.right_Node;
			}
		}

	}
	public void InOrder(TreeNode node) 
	{
		if (node!=null) {
			InOrder(node.left_Node);
			System.out.print("["+node.value+"]");
			InOrder(node.right_Node);
		}
	}
	public void PreOreder(TreeNode node) {
		if (node!=null) 
		{
			System.out.print("["+node.value+"]");
			PreOreder(node.left_Node);
			PreOreder(node.right_Node);
		}
	}
	public void PostOrder(TreeNode node) {
		if (node!=null) 
		{
			PostOrder(node.left_Node);
			PostOrder(node.right_Node);
			System.out.print("["+node.value+"]");
		}
	}
	public int size(TreeNode currentNode) {
		if (currentNode==null) {
			return 0;
		}else {
			return 1+size(currentNode.left_Node)+size(currentNode.right_Node);
		}
	}
	public int size() {
		return size(rootNode);
	}
	public int Height(TreeNode node){
        if(node == null){
            return 0;
        }
        //使用count进行层级统计。
        //nextCount保存的是每层遍历后新增到队列中的元素数量。
        //如果count++ = nextCount 就说明将该层遍历完了 deep++ nextCount等于队列中保存的下一层的所有结点数目。
        //以此类推
        int deep = 0,count = 0,nextCount = 1;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()){
            TreeNode rootNode = queue.poll();
            count ++;
            if(rootNode.left_Node != null){
                queue.add(rootNode.left_Node);
            }
            if(rootNode.right_Node != null){
                queue.add(rootNode.right_Node );
            }
            if(count == nextCount){
                nextCount = queue.size();
                count = 0;
                deep ++;
            }
        }
        return deep;
    }
	

	public List<TreeNode> outLeaf(TreeNode rootNode) {
        List<TreeNode> list = new LinkedList<TreeNode>();
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        TreeNode currentNode = null;
        nodeQueue.add(rootNode);
        while(!nodeQueue.isEmpty()){
        	currentNode = nodeQueue.poll();
            if(currentNode.left_Node == null){
                if(currentNode.right_Node == null){
                    list.add(currentNode);
                }else{
                    nodeQueue.add(currentNode.right_Node);
                }
            }else{
                nodeQueue.add(currentNode.left_Node);
                if(currentNode.right_Node != null){
                    nodeQueue.add(currentNode.right_Node);
                }
            }
        }
                 
        return list;
    }


	public Boolean findTree(int value) {
		TreeNode currentNode=rootNode;
		while (currentNode!=null) {
			if (value<currentNode.value) {
				currentNode=currentNode.left_Node;
			}
			else if (value>currentNode.value){
				currentNode=currentNode.right_Node;
			}
			else {
				return true;
			}
		}
		  return false;
	}
	
	public void levelOrder() {
		Queue<TreeNode> queue1=new LinkedList<binarytree.TreeNode>();
		TreeNode currentNode=rootNode;
		while (currentNode!=null) {
			System.out.print("["+currentNode.value+"]");
			if (currentNode.left_Node!=null) {
				queue1.add(currentNode.left_Node);
			}
			if (currentNode.right_Node!=null) {
				queue1.add(currentNode.right_Node);
			}
			currentNode=queue1.poll();
		}
	}
	public TreeNode findmax(TreeNode currentNode) {
		if (currentNode!=null) {
			while (currentNode.right_Node != null) {
				currentNode=currentNode.right_Node;
			}
		}
		return currentNode;
	}
	public int findmax() {
		return findmax(rootNode).value;
	}
	public TreeNode delect(int x,TreeNode currentNode) {
		TreeNode temp;
		if (currentNode==null) {
			System.out.println("树空");return null;
		}else if (x<currentNode.value) {
			currentNode.left_Node=delect(x, currentNode.left_Node);
		}else if (x>currentNode.value) {
			currentNode.right_Node=delect(x, currentNode.right_Node);
		}else { 
			if (currentNode.left_Node!=null&&currentNode.right_Node!=null) {
				temp=findmax(currentNode.left_Node);
				currentNode.value=temp.value;
				currentNode.left_Node=delect(currentNode.value,currentNode.left_Node);
			}else {
				temp=currentNode;
				if (currentNode.left_Node==null) {
					currentNode=currentNode.right_Node;
				}else if(currentNode.right_Node==null){
					currentNode=currentNode.left_Node;
				}
			}
		}
		return currentNode;
	}
	public static void main(String[] args) 
	{
		int i;
		int arr[]= {7,4,1,5,16,8,3,12,15,9,2};
		binarytree tree= new binarytree();
		System.out.print("原始数组的内容：\n");
		for (i = 0;i<11;i++) 
			System.out.print("["+arr[i]+"]");
		System.out.println();
		for ( i = 0; i < arr.length; i++) 
			tree.Add_Node_To_Tree(arr[i]);
		System.out.print("二叉树的内容\n");
		tree.levelOrder();
        System.out.println();
		System.out.print("前序遍历的结果：\n");//打印前、中、后序遍历的结果
		tree.PreOreder(tree.rootNode);
		System.out.print("\n");
		System.out.print("中序遍历的结果：\n");
		tree.InOrder(tree.rootNode);
		System.out.print("\n");
		System.out.print("后序遍历的结果：\n");
		tree.PostOrder(tree.rootNode);
		System.out.print("\n");
		System.out.println(tree.findTree(12));
		System.out.println(tree.findTree(88));
		System.out.println(tree.findmax());
		System.out.println(tree.size());
		System.out.println(tree.Height(tree.rootNode));
		System.out.println(tree.outLeaf(tree.rootNode));
		tree.delect(2, tree.rootNode);
		tree.PostOrder(tree.rootNode);
		System.out.println();
		System.out.println(tree.outLeaf(tree.rootNode));
	}

}