二叉树的建树，先序，中序，后序，层次遍历

 PS：输入测试数据时候采用先序遍历的方式用#作为分隔符来输入，例如：此二叉树

 

 

用这种方式输入ABC##DE#G##F###

 

 

 

 

package cn.jinyejun.experiment_Tree;

public class BNode{
	int data;
	BNode lchild;
	BNode rchild;
}

 

package cn.jinyejun.experiment_Tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class BinTree {
	static int index = 0;

	static class Info {
		int numOfNode = 0;
		int degree_1 = 0;
		int degree_2 = 0;
		int numOflNode = 0;
		int maxData;
		int minData;
	}

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		String toBuild = cin.nextLine();
		BNode bd = buildTree(toBuild);
		System.out.print("先序遍历： ");
		preOrder(bd);
		System.out.println();
		System.out.print("中序遍历： ");
		inOrder(bd);
		System.out.println();
		System.out.print("后序遍历： ");
		postOrder(bd);
		System.out.println();
		Info info = Non_recursive(bd);
		System.out.println("二叉树节点数： " + info.numOfNode + " 度为1节点数 :"
				+ info.degree_1 + " 度为2节点数：" + info.degree_2 + " 叶节点数： "
				+ info.numOflNode + " 最大数据 ：" + info.maxData + " 最小数据： "
				+ info.minData);
		System.out.print("层次遍历： ");
		levOrder(bd);
		System.out.println();
	}

	// 建二叉树(采用先序的算法建树)
	public static BNode buildTree(String str) {
		BNode bd;
		char ch = str.charAt(index++);
		if (ch == '#') {
			return null;
		} else {
			bd = new BNode();
			bd.data = (int)ch-48;
			bd.lchild = buildTree(str);
			bd.rchild = buildTree(str);
			return bd;
		}
	}

	// 先序遍历
	public static void preOrder(BNode bd) {
		if (bd != null) {
			System.out.print(bd.data + " ");
			preOrder(bd.lchild);
			preOrder(bd.rchild);
		}
	}

	// 中序遍历
	public static void inOrder(BNode bd) {
		if (bd != null) {
			inOrder(bd.lchild);
			System.out.print(bd.data + " ");
			inOrder(bd.rchild);
		}
	}

	// 后续遍历
	public static void postOrder(BNode bd) {
		if (bd != null) {
			postOrder(bd.lchild);
			postOrder(bd.rchild);
			System.out.print(bd.data + " ");
		}
	}
	//层次遍历
	public static void levOrder(BNode bd){
		Queue<BNode> queue = new LinkedList<BNode>();
		BNode tempbd;
		if(bd !=null){
			queue.offer(bd);
		}
		while(!queue.isEmpty()){
			tempbd = queue.poll();
			System.out.print(tempbd.data+" ");
			if(tempbd.lchild!=null){
				queue.offer(tempbd.lchild);
			}
			if(tempbd.rchild!=null){
				queue.offer(tempbd.rchild);
			}
		}
	}

	// 非递归统计二叉树的节点个数、度为1、度为2和叶子节点的个数，以及数据值的最大值和最小值
	public static Info Non_recursive(BNode bd) {
		Stack<BNode> st = new Stack<BNode>();
		Info info = new Info();
		BNode tempBd;
		int degree;
		//初始化最大值最小值
		if (bd != null) {
			st.push(bd);
			info.maxData = bd.data;
			info.minData = bd.data;
			info.numOfNode++;
		}
		while (!st.isEmpty()) {
			//每次遍历节点计算度
			degree = 0;
			tempBd = st.pop();
			info.maxData = (tempBd.data > info.maxData) ? tempBd.data
					: info.maxData;
			info.minData = (tempBd.data < info.minData) ? tempBd.data
					: info.minData;
			if (tempBd.rchild != null) {
				st.push(tempBd.rchild);
				info.numOfNode++;
				degree++;
			}
			if (tempBd.lchild != null) {
				st.push(tempBd.lchild);
				info.numOfNode++;
				degree++;
			}
			//如果度为0，说明就是叶节点，如果为1或2统计度为1或2的节点数
			switch (degree) {
			case 0:
				info.numOflNode++;
				break;
			case 1:
				info.degree_1++;
				break;
			case 2:
				info.degree_2++;
				break;
			}
		}
		return info;
	}
}