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(); // 定语 中心语 主语 述语 宾语 谓语 句子 
	}
}