二叉树的顺序存储实现(java)

  顺序存储对完全二叉树而，简单又节省空间。对于一般二叉树，为了能用结点在数组中的相对位置表示结点之间的逻辑关系，也必须按完全二叉树的形式来存储树中的结点，这必然造成空间的浪费，随着二叉树高度的增大，空结点的数量也会急速增多。
 

/**
 * 顺序二叉树
 * 
 * @author liuyan
 */
public class ArrayBinaryTree<T> {

	// 节点数组
	private Object[] datas;

	// 指定的树的深度
	private int treeDeep;

	// datas数组的实际大小
	private int arraySize;

	/**
	 * 默认构造函数
	 */
	public ArrayBinaryTree() {
		// 设置默认的树深度
		treeDeep = 4;
		arraySize = (int) Math.pow(2, 4) - 1;
		datas = new Object[arraySize];
	}

	/**
	 * 指定深度构建二叉树 
	 * @param deep
	 */
	public ArrayBinaryTree(int deep) {
		// 按指定深度
		treeDeep = deep;
		arraySize = (int) Math.pow(2, treeDeep) - 1;
		datas = new Object[arraySize];
	}

	/**
	 * 指定深度和指定根节点构建二叉树 
	 * @param deep
	 * @param data
	 */
	public ArrayBinaryTree(int deep, T data) {
		// 按指定深度
		treeDeep = deep;
		arraySize = (int) Math.pow(2, treeDeep) - 1;
		datas = new Object[arraySize];
		datas[0] = data;
	}

	/**
	 * 为下标是index的节点增加子节点 
	 * @param index
	 * @param data
	 * @param isLeft
	 * @return
	 */
       public boolean addNode(int index, T data, boolean isLeft) {
	if (index * 2 + 2 > arraySize-1 || datas[index] == null) {
			throw new RuntimeException("下标无效");
		}
		if (isLeft) {
			datas[index * 2 + 1] = data;
		} else {
			datas[index * 2 + 2] = data;
		}
		return true;
	}

	/**
	 * 判断二叉树是否为空
	 * 
	 * @return
	 */
	public boolean isEmpty() {
              for(int i=0;i<datas.length;i++)
                  if(datas[i]!=null) return false;
		return true;
	}

	/**
	 * 返回根节点
	 * 
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public T getRoot() {
		return (T) datas[0];
	}

	/**
	 * 返回指定节点的父节点 
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public T getParent(int index) {
		if (index > arraySize-1 || datas[index] == null) {
			throw new RuntimeException("下标无效");
		}
		if (datas[(index - 1) / 2] == null) {
			throw new RuntimeException("无父节点");
		}
		return (T) datas[(index - 1) / 2];
	}

	/**
	 * 返回左子节点 
	 * @return
	 */
	@SuppressWarnings("unchecked")
       public T getLeftNode(int index) {
	if (index * 2 + 1 > (arraySize-1) || datas[index] == null) {
			throw new RuntimeException("下标无效");
		}
		return (T) datas[index * 2 + 1];
	}

	/**
	 * 返回右子节点 
	 * @return
	 */
	@SuppressWarnings("unchecked")
       public T getRightNode(int index) {
	if (index * 2 + 2 > (arraySize-1) || datas[index] == null) {
			throw new RuntimeException("下标无效");
		}
		return (T) datas[index * 2 + 2];
	}

	/**
	 * 返回树的深度 
	 * @return
	 */
	public int getTreeDeep() {
		return treeDeep;
	}

	/**
	 * 返回指定节点的索引位置 
	 * @param data
	 * @return
	 */
	public int getNodeIndex(T data) {

		for (int i = 0; i < arraySize; i++) {
			if (data == datas[i]) {
				return i;
			}
		}
		return -1;
	}

	@Override
	public String toString() {
		StringBuffer str = new StringBuffer("[");
		for (int i = 0; i < datas.length; i++) {
			str.append("[" + datas[i] + "],");
		}

	   if (datas.length > 0) {
	     return str.substring(0, str.lastIndexOf(",")) + "]";
	   }
		return str.append("]").toString();
	}

   //测试代码如下
      public static void main(String[] args) {
          ArrayBinaryTree<String> arrayBinaryTree1 =
               new ArrayBinaryTree<String>(4);
          System.out.println(arrayBinaryTree1.isEmpty());
	 ArrayBinaryTree<String> arrayBinaryTree = 
               new ArrayBinaryTree<String>(4,"汉献帝");
	 System.out.println(arrayBinaryTree);
	 arrayBinaryTree.addNode(0, "刘备", true);
	 arrayBinaryTree.addNode(0, "曹操", false);
	 arrayBinaryTree.addNode(1, "关羽", true);
	 arrayBinaryTree.addNode(1, "张飞", false);
	 arrayBinaryTree.addNode(2, "张辽", true);
	 arrayBinaryTree.addNode(2, "许褚", false);
          System.out.println("现在二叉树是：");
	 System.out.println(arrayBinaryTree);

          System.out.println();
          System.out.print("刘备的左手是: ");
	 System.out.println(arrayBinaryTree.getLeftNode(1));
          System.out.print("汉献帝的右手是：");
	 System.out.println(arrayBinaryTree.getRightNode(0));
          System.out.println();
          System.out.print("张飞的上司是：");
		
	 System.out.println(arrayBinaryTree.getParent(4));
          System.out.println(arrayBinaryTree.isEmpty());
	}
   }

运行：
true
[[汉献帝],[null],[null],[null],[null],[null],[null],[null],[null],[null],[null],[null],[null],[null],[null]]

现在二叉树是：
[[汉献帝],[刘备],[曹操],[关羽],[张飞],[张辽],[许褚],[null],[null],[null],[null],[null],[null],[null],[null]]

刘备的左手是: 关羽
汉献帝的右手是：曹操

张飞的上司是：刘备
false

下载源码：