1. 顺序存储结构:
二叉树的顺序存储结构就是用一维数组存储二叉树中的结点。
2. 完全二叉树:
完全二叉树由于其结构上的特点,通常采用顺序存储方式存储。一棵有n个结点的完全二叉树的所有结点从1到n编号,就得到结点的一个线性系列。
如下图:完全二叉树除最下面一层外,各层都被结点充满了,每一层结点的个数恰好是上一层结点个数的2倍,因此通过一个结点的编号就可以推知它的双亲结点及左,右孩子结点的编号:
①当 2i ≤ n 时,结点 i 的左孩子是 2i,否则结点i没有左孩子;
②当 2i+1 ≤ n 时,结点i的右孩子是 2i+1,否则结点i没有右孩子;
③当 i ≠ 1 时,结点i的双亲是结点 i/2;
注意:由于数组下标从0开始,因此数组元素的下标等于结点在完全二叉树中的序号减1。
3. 一般二叉树:
对于一般的二叉树,如果仍按照从上至下,从左到右的顺序将树中的结点顺序存储在一维数组中,则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系。
这时假设将一般二叉树进行改造,增添一些并不存在的空结点,使之成为一棵完全二叉树的形式,然后再用一维数组顺序存储。在二叉树中假设增添的结点在数组中所对应的元素值为"空"用^表示。
4. Java实现顺序存储:
public class ArrayBinaryTree<T> {
private Object[] arr; // 用数组来存储树的所有节点
private int deep; // 保存该树的深度
private int size; // 数组大小
private static final int DEFAULT_DEEP = 5; // 树的默认深度
/**
* 以默认的深度来创建二叉树
*/
public ArrayBinaryTree() {
this.deep = DEFAULT_DEEP;
this.size = (int) Math.pow(2, deep) - 1; // Math.pow(2,deep)返回第一个参数的第二个参数次幂的值
arr = new Object[size];
}
/**
* 以指定深度来创建二叉树
* @param deep
*/
public ArrayBinaryTree(int deep) {
this.deep = deep;
this.size = (int) Math.pow(2, deep) - 1;
arr = new Object[size];
}
/**
* 以指定深度,指定根节点创建二叉树
*
* @param deep 树的深度
* @param data 数据
*/
public ArrayBinaryTree(int deep, T data) {
this.deep = deep;
this.size = (int) Math.pow(2, deep) - 1;
arr = new Object[size];
arr[0] = data; // 根节点
}
/**
* 为指定节点添加子节点。
*
* @param index 需要添加子节点的父节点的索引
* @param data 新子节点的数据
* @param left 是否为左节点
*/
public void add(int index, T data, boolean left) {
if (arr[index] == null) {
throw new RuntimeException(index + "处节点为空,无法添加子节点");
}
if (2 * index + 1 >= size) {
throw new IndexOutOfBoundsException();
}
if (left) {
arr[2 * index + 1] = data; // 添加左子节点
} else {
arr[2 * index + 2] = data; // 添加右子结点
}
}
/**
* 判断二叉树是否为空
* @return
*/
public boolean isEmpty() {
return arr[0] == null; // 根据根元素来判断二叉树是否为空
}
/**
* 返回根节点
* @return
*/
@SuppressWarnings("unchecked")
public T getRoot() {
return (T) arr[0];
}
/**
* 返回指定节点(非根节点)的父节点
* @param index
* @return
*/
@SuppressWarnings("unchecked")
public T getParent(int index) {
return (T) arr[(index - 1) / 2];
}
/**
* 返回指定节点(非叶子)的左子节点,当左子节点不存在时返回null
* @param index
* @return
*/
@SuppressWarnings("unchecked")
public T getLeft(int index) {
if (2 * index + 1 >= size) {
throw new RuntimeException("该节点为叶子节点,无子节点");
}
return (T) arr[index * 2 + 1];
}
/**
* 返回指定节点(非叶子)的右子节点,当右子节点不存在时返回null
* @param index
* @return
*/
@SuppressWarnings("unchecked")
public T getRight(int index) {
if (2 * index + 1 >= size) {
throw new RuntimeException("该节点为叶子节点,无子节点");
}
return (T) arr[index * 2 + 2];
}
/**
* 返回该二叉树的深度。
* @param index
* @return
*/
public int getDeep(int index) {
return deep;
}
/**
* 返回指定节点的位置。
* @param data
* @return
*/
public int index(T data) {
for (int i = 0; i < size; i++) { // 该循环实际上就是按广度遍历来搜索每个节点
if (arr[i].equals(data)) {
return i;
}
}
return -1;
}
/**
* 打印数组
*/
public String toString() {
return Arrays.toString(arr);
}
/**
* 测试方法
* @param args
*/
public static void main(String[] args) {
ArrayBinaryTree<String> binTree = new ArrayBinaryTree<String>(4, "根结点");
binTree.add(0, "第二层右子节点", false); // 第一个参数为需要添加子节点的父节点的索引: 即根节点
binTree.add(2, "第三层右子节点", false);
binTree.add(6, "第四层右子节点", false);
System.out.println(binTree);
}
}
分享到:
相关推荐
数据结构课程设计,二叉树 顺序存储 VC++ 数据结构 源代码
数据结构课程设计:内容是关于二叉树的存储和遍历还有排序。
要求选用顺序存储结构和二叉链表存储结构实现抽象数据类型二叉树的基本操作。有个亮点是利用字符在dos界面显示二叉树的结构形态。 里面包含了完整的源程序和实验报告文档。 实验报告包含了完整的步骤包括: 一.抽象...
c++实现二叉树的数组存储,代码很简单,参考即可
数据结构实用教程之二叉树,其中包含了:二叉树的定义、二叉树的递归遍历、二叉树基本操作。 数据结构实用教程之二叉树,其中包含了:二叉树的定义、二叉树的递归遍历、二叉树基本操作。 数据结构实用教程之二叉树,...
1. 一棵二叉树的顺序存储情况如下: 树中,度为2的结点数为( )。 A.1 B.2 C.3 D.4 2. 一棵“完全二叉树”结点数为25,高度为( )。 A.4 B.5 C.6 D.不确定 3.下列说法中,( )是正确的。 A. 二叉树就是...
数据结构源码:二叉树,这是一个关于二叉树的数据结构源码
实现功能:建立二叉树存储结构、求二叉树的先序遍历、求二叉树的中序遍历、求二叉树的后序遍历、求二叉树的层次遍历、求根到给定结点的路径。 主控菜单: 1.建立二叉树存储结构 2.求二叉树的先序遍历 3.求二叉树...
南邮数据结构实验使用C++描述,二叉树的基本操作
3、创建一棵二叉树: 4、实现输出以上二叉树先序、中序和后序遍历序列中第k个数据元素的操作; 5、判断二叉树是否是完全二叉树; //先序遍历递归算法 public void preRootTraverse(BiTreeNode T){ if(T != null)...
用c语言实现: 二叉树的创建(递归法) 二叉树的遍历(递归(DLR、LDR、LRD)、层次)
1. 以二叉链表为存储结构,实现二叉树的创建、遍历 1)问题描述:在主程序中设计一个简单的菜单,分别调用相应的函数功能: 1…建立树 2…前序遍历树 3…中序(非递归)遍历树 4…后序遍历树 0…结束 2)实验...
数据结构实验十:树及二叉树的应用试验
本讲主要讲述二叉树的顺序存储结构思想,和类主要的顺序存储方法。
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
将按顺序方式存储在数组中的二叉树转换为二叉链表形式。 复制一棵二叉树T到T1。 交换二叉树中每个结点的左右孩子指针的值。 设计算法以实现下面所提到以扩展二叉树的先序序列作为输入构建二叉树的功能。
二叉树的顺序存储表示和实现、自己写的、觉得应该有用吧、、
C语言实现二叉树的顺序存储
数据结构实验报告
数据结构-C语言版:二叉树例题.ppt