首页 > 代码库 > 二叉树的顺序存储及其Java实现
二叉树的顺序存储及其Java实现
顺序存储充分利用满二叉树的特性,即每层的节点数分别为1、2、4、8。。。2i+1,一个深度为i的二叉树最多只能包含2i-1个节点,因此只要定义一个长度为2i-1的数组即可存储这颗二叉树。
对于普通的不是满二叉树的,那些空出来的节点对应的数组元素留空即可,因此顺序存储会造成一定的空间浪费。如下图。
显然,如果是完全二叉树,那么就不会有空间浪费的情况;若是只有右子树,那么会造成相当大的浪费。
Java实现代码:
package com.liuhao.DataStructures; import java.util.Arrays; public class ArrayBinTree<T> { // 使用数组来记录所有节点 private Object[] datas; private final int DEFAULT_DEEP = 8; // 保存该树的深度 private int deep; // 数组的长度 private int arraySize; // 以默认深度创建二叉树 public ArrayBinTree() { this.deep = DEFAULT_DEEP; this.arraySize = (int) Math.pow(2, deep); datas = new Object[arraySize]; } // 以指定深度创建 public ArrayBinTree(int deep) { this.deep = deep; this.arraySize = (int) Math.pow(2, deep); datas = new Object[arraySize]; } // 以指定深度,指定根节点创建 public ArrayBinTree(int deep, T data) { this.deep = deep; this.arraySize = (int) Math.pow(2, deep); datas = new Object[arraySize]; datas[0] = data; } /** * 为指定节点添加子节点 * * @param index * 需要添加子节点的父节点索引 * @param data * 新的子节点的数据 * @param left * 是否为左节点 */ public void add(int index, T data, boolean left) { if (datas[index] == null) { throw new RuntimeException(index + "处节点为空,无法添加子节点!"); } if (2 * index + 1 > arraySize || 2 * index + 2 > arraySize) { throw new RuntimeException("树底层数组已满"); } if (left) { if (datas[2 * index + 1] == null) { datas[2 * index + 1] = data; } else { throw new RuntimeException("该节点已存在!"); } } else { if (datas[2 * index + 2] == null) { datas[2 * index + 2] = data; } else { throw new RuntimeException("该节点已存在!"); } } } // 判断二叉树是否为空 public boolean isEmpty() { return datas[0] == null; } // 获取根节点 public T getRoot() { return (T) datas[0]; } // 返回指定节点的父节点 public T getParent(int index) { if (index == 0) { throw new RuntimeException("根节点不存在父节点!"); } return (T) datas[(index - 1) / 2]; } //获取右子节点 public T getRight(int index){ if (2 * index + 1 > arraySize || 2 * index + 2 > arraySize) { throw new RuntimeException("该节点不存在右子节点!"); } return (T) datas[index * 2 + 2]; } //获取左子节点 public T getLeft(int index){ if (2 * index + 1 > arraySize || 2 * index + 2 > arraySize) { throw new RuntimeException("该节点不存在左子节点!"); } return (T) datas[index * 2 + 1]; } //返回该二叉树的深度 public int getDeep(){ return deep; } //返回指定数据的位置 public int getPos(T data){ for(int i=0;i<arraySize;i++){ if(datas[i].equals(data)){ return i; } } return -1; } public String toString(){ return Arrays.toString(datas); } }
从上面的介绍可以看出,顺序存储的思想就是将数中不同的节点存入数组的不同位置。比如,根节点,永远使用数组的第一个元素来保存;第二层的第二个节点,永远使用数组的第三个元素来保存。。。以此类推。
对于顺序存储的二叉树,不管是遍历还是查找,都可以有非常高的效率,唯一的缺点是空间浪费很大。
测试代码:
package com.liuhao.test; import org.junit.Test; import com.liuhao.DataStructures.ArrayBinTree; public class ArrayBinTreeTest { @Test public void test() { ArrayBinTree<String> binTree = new ArrayBinTree<String>(4,"根"); binTree.add(0, "0右", false); binTree.add(2, "2右", false); binTree.add(2, "2左", true); binTree.add(0, "0左", true); binTree.add(1, "1左", true); System.out.println(binTree); System.out.println(binTree.getLeft(2)); System.out.println(binTree.getParent(6)); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。