二叉树的顺序存储实现(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;}/** * 指定深度构建二叉树* @param deep */public ArrayBinaryTree(int deep) {// 按指定深度treeDeep = deep;arraySize = (int) Math.pow(2, treeDeep) - 1;datas = new Object;}/** * 指定深度和指定根节点构建二叉树* @param deep * @param data */public ArrayBinaryTree(int deep, T data) {// 按指定深度treeDeep = deep;arraySize = (int) Math.pow(2, treeDeep) - 1;datas = new Object;datas = 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 == null) {throw new RuntimeException("下标无效");}if (isLeft) {datas = data;} else {datas = data;}return true;}/** * 判断二叉树是否为空 ** @return */public boolean isEmpty() { for(int i=0;i<datas.length;i++) if(datas!=null) return false;return true;}/** * 返回根节点 ** @return */@SuppressWarnings("unchecked")public T getRoot() {return (T) datas;}/** * 返回指定节点的父节点* @return */@SuppressWarnings("unchecked")public T getParent(int index) {if (index > arraySize-1 || datas == 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 == null) {throw new RuntimeException("下标无效");}return (T) datas;}/** * 返回右子节点* @return */@SuppressWarnings("unchecked") public T getRightNode(int index) {if (index * 2 + 2 > (arraySize-1) || datas == null) {throw new RuntimeException("下标无效");}return (T) datas;}/** * 返回树的深度* @return */public int getTreeDeep() {return treeDeep;}/** * 返回指定节点的索引位置* @param data * @return */public int getNodeIndex(T data) {for (int i = 0; i < arraySize; i++) {if (data == datas) {return i;}}return -1;}@Overridepublic String toString() {StringBuffer str = new StringBuffer("[");for (int i = 0; i < datas.length; i++) {str.append("[" + datas + "],");} 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
[[汉献帝],,,,,,,,,,,,,,]
现在二叉树是：
[[汉献帝],[刘备],[曹操],[关羽],[张飞],[张辽],[许褚],,,,,,,,]
刘备的左手是: 关羽
汉献帝的右手是：曹操
张飞的上司是：刘备
false
下载源码：
页:
[1]