Java資料結構學習之二元樹

package com.notes.data_structure6;
 
import com.notes.data_structure6.NumberOfNodesException;
 
public class MyBinaryTree {
	// 樹的根結點
	private Node[] root;
	// 樹的深度（當前層級數）
	private int depth;
	// 將每一層所有的 結點 都儲存在陣列中，結點數是 2的 層數 次冪
	private Node[] currentLevel;
	
	
	public MyBinaryTree(String data) {
		Node[] rootArray = new Node[] {new Node(data)};
		this.root = rootArray;
		this.currentLevel = rootArray;
	}
 
	// 定義一個結點類
	private class Node{
		private String data; // 資料
		private Node leftNext; // 左指標
		private Node rightNext; // 右指標
		
		// 構造方法：Node範例化時傳入資料
		public Node(String data) {
			this.data = data;
		}	
	}
	
	// 向樹中增加一層結點
	public void add(String[] datas) throws NumberOfNodesException {
		// 層級數增加1
		depth++;
		// 新增 層級 的最大結點數
		int nodeNum = numberOfNextNodes();
		// 如果傳入的 資料數 與 當前層級 最大結點數 不符，丟擲異常
		if(datas.length != nodeNum) {
			throw new NumberOfNodesException("第"+depth+"層最大父節點數為"+nodeNum);
		}
		// 將傳入的 資料陣列 轉換為 結點陣列
		Node[] newLevel = new Node[nodeNum];
		// 當前 層級的 結點數量（新增層級的父）
		int nodeNum2 = (int) Math.pow(2, depth-1);
		// 讓每一個結點都與上層 父結點 建立連線
		for(int i=0;i<nodeNum2;i++) {
			// 讓父結點 的左指標 指向 左子結點
			int leftIndex = (i+1)*2-2; // 計算左子結點對應的新層級陣列的索引
			currentLevel[i].leftNext = new Node(datas[leftIndex]); // 建立指標指向
			newLevel[leftIndex] = currentLevel[i].leftNext; // 將結點加入新層級結點陣列
			// 讓父結點 的右指標 指向 右子結點
			int rightIndex = leftIndex+1; // 計算右子結點對應的新層級陣列的索引
			currentLevel[i].rightNext = new Node(datas[rightIndex]); // 建立指標指向
			newLevel[rightIndex] = currentLevel[i].rightNext; // 將結點加入新層級結點陣列
		}
		// 讓新增層級的陣列成為當前層級的陣列
		currentLevel =  newLevel;
	}
	
	// 前序遍歷所有結點
	public void preTraversal(Node node) {
		if(node==null) {
			return;
		}
		System.out.print(node.data+" ");
		preTraversal(node.leftNext);
		preTraversal(node.rightNext);
	}
	
	// 重寫 前序遍歷 方法，讓遍歷從 根結點 開始
	public void preTraversal() {
		Node node = root[0];
		if(node==null) {
			return;
		}
		// 遞迴時呼叫帶引數的方法
		System.out.print(node.data+" ");
		preTraversal(node.leftNext);
		preTraversal(node.rightNext);
	}
	
	// 中序遍歷所有結點
	public void midTraversal(Node node) {
		if(node==null) {
			return;
		}
		midTraversal(node.leftNext);
		System.out.print(node.data+" ");
		midTraversal(node.rightNext);
	}
	
	// 重寫中序遍歷 方法，讓遍歷從 根結點 開始
	public void midTraversal() {
		Node node = root[0];
		if(node==null) {
			return;
		}
		// 遞迴時呼叫帶引數的方法
		midTraversal(node.leftNext);
		System.out.print(node.data+" ");
		midTraversal(node.rightNext);
	}
	
	// 後序遍歷所有結點
	public void posTraversal(Node node) {
		if(node==null) {
			return;
		}
		posTraversal(node.leftNext);
		posTraversal(node.rightNext);
		System.out.print(node.data+" ");
	}
	
	// 重寫後序遍歷 方法，讓遍歷從 根結點 開始
	public void posTraversal() {
		Node node = root[0];
		if(node==null) {
			return;
		}
		// 遞迴時呼叫帶引數的方法
		posTraversal(node.leftNext);
		posTraversal(node.rightNext);
		System.out.print(node.data+" ");
	}
	
	// 檢視 新增層級 的最大結點數
	public int numberOfNextNodes() {
		return (int) Math.pow(2,depth);
	}
	
	// 檢視 樹 的深度（層級數）
	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 {
		// 範例化二元樹類，並且傳入根節點的資料
		MyBinaryTree tree = new MyBinaryTree("句子");
		// 加入第一層節點的資料
		tree.add(new String[] {"主語","謂語"});
		// 加入第二層節點的資料
		tree.add(new String[] {"定語","中心語","述語","賓語"});
		
		// 前序遍歷
		tree.preTraversal(); // 句子 主語 定語 中心語 謂語 述語 賓語 
		System.out.println();
		// 中序遍歷
		tree.midTraversal(); // 定語 主語 中心語 句子 述語 謂語 賓語 
		System.out.println();
		// 後序遍歷
		tree.posTraversal(); // 定語 中心語 主語 述語 賓語 謂語 句子 
	}
}