[数据结构与算法]Java数据结构——顺序二叉树

顺序二叉树：

二叉树为顺序存储结构，数据存储基于数组

一般用于存储完全二叉树，将节点按照层序依次存储在数组中

实现思路：

通过观察可以发现顺序二叉树的父子节点对应的数组下标关系：

第n个元素的左孩子节点下标为：

第n个元素的右孩子节点下标为：

第n个元素的父节点下标为：

这里的n为数组下标，从0开始

对于顺序二叉树的前序、中序、后序遍历、同样是递归实现

代码实现：

public class SeqBinaryTree {
	public int count;
	public int[] array;

	public SeqBinaryTree(int maxSize) {
		array = new int[maxSize];
	}

	//增加节点
	public void add(int data) {
		array[count] = data;
		count++;
	}

	//前序遍历
	public void preOrder() {
		preOrder(0);
	}

	public void preOrder(int index) {
		if (count == 0) {
			System.out.println("二叉树为空");
			return;
		}
		System.out.println(array[index]);
		if (2 * index + 1 < count) {
			preOrder(2 * index + 1);
		}
		if (2 * index + 2 < count) {
			preOrder(2 * index + 2);
		}
	}

	//中序遍历
	public void inOrder() {
		inOrder(0);
	}

	public void inOrder(int index) {
		if (count == 0) {
			System.out.println("二叉树为空");
			return;
		}
		if (2 * index + 1 < count) {
			inOrder(2 * index + 1);
		}
		System.out.println(array[index]);
		if (2 * index + 2 < count) {
			inOrder(2 * index + 2);
		}
	}

	//后序遍历
	public void postOrder() {
		postOrder(0);
	}

	public void postOrder(int index) {
		if (count == 0) {
			System.out.println("二叉树为空");
			return;
		}
		if (2 * index + 1 < count) {
			postOrder(2 * index + 1);
		}
		if (2 * index + 2 < count) {
			postOrder(2 * index + 2);
		}
		System.out.println(array[index]);
	}
}