package com.notes.data_structure6;
 
import com.notes.data_structure6.NumberOfNodesException;
 
public class MyBinaryTree {
	// 樹的根結(jié)點
	private Node[] root;
	// 樹的深度（當前層級數(shù)）
	private int depth;
	// 將每一層所有的 結(jié)點 都存儲在數(shù)組中，結(jié)點數(shù)是 2的 層數(shù) 次冪
	private Node[] currentLevel;
	
	
	public MyBinaryTree(String data) {
		Node[] rootArray = new Node[] {new Node(data)};
		this.root = rootArray;
		this.currentLevel = rootArray;
	}
 
	// 定義一個結(jié)點類
	private class Node{
		private String data; // 數(shù)據(jù)
		private Node leftNext; // 左指針
		private Node rightNext; // 右指針
		
		// 構(gòu)造方法：Node實例化時傳入數(shù)據(jù)
		public Node(String data) {
			this.data = data;
		}	
	}
	
	// 向樹中增加一層結(jié)點
	public void add(String[] datas) throws NumberOfNodesException {
		// 層級數(shù)增加1
		depth++;
		// 新增 層級 的最大結(jié)點數(shù)
		int nodeNum = numberOfNextNodes();
		// 如果傳入的 數(shù)據(jù)數(shù) 與 當前層級 最大結(jié)點數(shù) 不符，拋出異常
		if(datas.length != nodeNum) {
			throw new NumberOfNodesException("第"+depth+"層最大父節(jié)點數(shù)為"+nodeNum);
		}
		// 將傳入的 數(shù)據(jù)數(shù)組 轉(zhuǎn)換為 結(jié)點數(shù)組
		Node[] newLevel = new Node[nodeNum];
		// 當前 層級的 結(jié)點數(shù)量（新增層級的父）
		int nodeNum2 = (int) Math.pow(2, depth-1);
		// 讓每一個結(jié)點都與上層 父結(jié)點 建立連接
		for(int i=0;i<nodeNum2;i++) {
			// 讓父結(jié)點 的左指針 指向 左子結(jié)點
			int leftIndex = (i+1)*2-2; // 計算左子結(jié)點對應的新層級數(shù)組的索引
			currentLevel[i].leftNext = new Node(datas[leftIndex]); // 建立指針指向
			newLevel[leftIndex] = currentLevel[i].leftNext; // 將結(jié)點加入新層級結(jié)點數(shù)組
			// 讓父結(jié)點 的右指針 指向 右子結(jié)點
			int rightIndex = leftIndex+1; // 計算右子結(jié)點對應的新層級數(shù)組的索引
			currentLevel[i].rightNext = new Node(datas[rightIndex]); // 建立指針指向
			newLevel[rightIndex] = currentLevel[i].rightNext; // 將結(jié)點加入新層級結(jié)點數(shù)組
		}
		// 讓新增層級的數(shù)組成為當前層級的數(shù)組
		currentLevel =  newLevel;
	}
	
	// 前序遍歷所有結(jié)點
	public void preTraversal(Node node) {
		if(node==null) {
			return;
		}
		System.out.print(node.data+" ");
		preTraversal(node.leftNext);
		preTraversal(node.rightNext);
	}
	
	// 重寫 前序遍歷 方法，讓遍歷從 根結(jié)點 開始
	public void preTraversal() {
		Node node = root[0];
		if(node==null) {
			return;
		}
		// 遞歸時調(diào)用帶參數(shù)的方法
		System.out.print(node.data+" ");
		preTraversal(node.leftNext);
		preTraversal(node.rightNext);
	}
	
	// 中序遍歷所有結(jié)點
	public void midTraversal(Node node) {
		if(node==null) {
			return;
		}
		midTraversal(node.leftNext);
		System.out.print(node.data+" ");
		midTraversal(node.rightNext);
	}
	
	// 重寫中序遍歷 方法，讓遍歷從 根結(jié)點 開始
	public void midTraversal() {
		Node node = root[0];
		if(node==null) {
			return;
		}
		// 遞歸時調(diào)用帶參數(shù)的方法
		midTraversal(node.leftNext);
		System.out.print(node.data+" ");
		midTraversal(node.rightNext);
	}
	
	// 后序遍歷所有結(jié)點
	public void posTraversal(Node node) {
		if(node==null) {
			return;
		}
		posTraversal(node.leftNext);
		posTraversal(node.rightNext);
		System.out.print(node.data+" ");
	}
	
	// 重寫后序遍歷 方法，讓遍歷從 根結(jié)點 開始
	public void posTraversal() {
		Node node = root[0];
		if(node==null) {
			return;
		}
		// 遞歸時調(diào)用帶參數(shù)的方法
		posTraversal(node.leftNext);
		posTraversal(node.rightNext);
		System.out.print(node.data+" ");
	}
	
	// 查看 新增層級 的最大結(jié)點數(shù)
	public int numberOfNextNodes() {
		return (int) Math.pow(2,depth);
	}
	
	// 查看 樹 的深度（層級數(shù)）
	public int getDepth() {
		return depth;
	}
	
	
}

package com.notes.data_structure6;
 
public class NumberOfNodesException extends Exception{
	public NumberOfNodesException(String message) {
		super(message);
	}
}

package com.notes.data_structure6;
 
public class TreeDemo {
	public static void main(String[] args) throws NumberOfNodesException {
		// 實例化二叉樹類，并且傳入根節(jié)點的數(shù)據(jù)
		MyBinaryTree tree = new MyBinaryTree("句子");
		// 加入第一層節(jié)點的數(shù)據(jù)
		tree.add(new String[] {"主語","謂語"});
		// 加入第二層節(jié)點的數(shù)據(jù)
		tree.add(new String[] {"定語","中心語","述語","賓語"});
		
		// 前序遍歷
		tree.preTraversal(); // 句子 主語 定語 中心語 謂語 述語 賓語 
		System.out.println();
		// 中序遍歷
		tree.midTraversal(); // 定語 主語 中心語 句子 述語 謂語 賓語 
		System.out.println();
		// 后序遍歷
		tree.posTraversal(); // 定語 中心語 主語 述語 賓語 謂語 句子 
	}
}