经过前面的学习我们已经熟悉了二叉树的基本操作,其中包括遍历(前中后)查找(前中后)删除等操作,有了这些二叉树的基础后,本节我们在前面的基础上来学习二叉树的另外一种,也就是它的顺序存储过程,简单说白了,也就是我们可以将二叉树上的节点按照数组的方式来存储,首先我们来看看对它的基本介绍.
顺序存储二叉树的介绍
我们从数据的存储来看,数组存储的方式和树的存储方式是可以相互转换的,我们来看张图:
image.png
从图中我们看到了树中节点我们可以按照数组存储的方式来实现,接着我们来了解下它的特点:
- 1.其实我们也从图中发现了,顺序存储二叉树是针对于完全平衡二叉树(即树的叶子节点在同一级)
- 2.我们可以发现第n个元素的左子点为 2 *n+1
- 3.发现第n个元素的右子点为 2 *n+2
- 4.第n个元素的父节点为(n-1)/2
- 5.这其中n表示二叉树中的第几个元素(也就是图中所示编号从0开始节点)
看完了这些特点之后,我们就上述说的结合图来简单的举个例子,这里就以左子树节点2来说,我们验证上述理论
从图中来看节点2的下标是1,首先我们来计算下它的左子点即:2 *1(节点2所对应的下标)+1=3也就是我们的节点4,再来计算它的右节点即2 * 1+2 = 4,我们计算得到编号为4也就是代表节点5.
我们来计算节点6的父节点,图中可以发现节点6的下标是5,按照上述规则可得到 (5-1)/2 = 2,我们计算得到下标是2,也就是节点为3
通过上述的验证,我们证实了这些特点,接着我们通过具体的案例来实现树和数组存储之间的转化
案例
假设我有一组数组如{1,2,3,4,5,6,7},要求我们以二叉树的前序遍历的方式进行遍历操作,其前序遍历的结果为1,2,4,5,3,6,7,接着我们来看代码实现过程
代码实现
//顺序存储二叉树的实现过程
class ArrayBinaryTree{
private int[] arr; //用来存储我们二叉树节点的数组
public ArrayBinaryTree(int[] arr) {
this.arr = arr;
}
//重载方法
public void preOrder(){
this.preOrder(0);
}
//前序遍历完成顺序存储过程
/**
*
* @param index 我们数组的下标
*/
public void preOrder(int index){
if (arr ==null || arr.length == 0){
System.out.println("数组为null,不能利用二叉树的前序遍历来打印!");
}
//利用二叉树的前序遍历特点来实现
//首先打印当前节点
System.out.println(arr[index]);
//向左递归遍历
if ((index *2+1) <arr.length){
preOrder(index *2+1);
}
//向右递归遍历
if ((index *2+2) <arr.length){
preOrder(index *2+2);
}
}
上述就是前序遍历的代码实现过程,接着我们来看看测试代码
public class ArrayBinaryTreeCase {
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7};
ArrayBinaryTree binaryTree = new ArrayBinaryTree(arr);
binaryTree.preOrder();
}
测试结果如下图所示:
前序测试结果图.png
从结果来看是没有问题的,跟我们预想的一样,实际上还有中序和后续的遍历操作的代码,这里就不在说了,感兴趣的猿友们可以在我的码云地址下载对应的代码看看:
那么关于顺序存储二叉树的学习就到这里了
网友评论