树结构入门教程-二叉树的顺序存储

经过前面的学习我们已经熟悉了二叉树的基本操作,其中包括遍历(前中后)查找(前中后)删除等操作,有了这些二叉树的基础后,本节我们在前面的基础上来学习二叉树的另外一种,也就是它的顺序存储过程,简单说白了,也就是我们可以将二叉树上的节点按照数组的方式来存储,首先我们来看看对它的基本介绍.

顺序存储二叉树的介绍

我们从数据的存储来看,数组存储的方式和树的存储方式是可以相互转换的,我们来看张图:

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

从结果来看是没有问题的,跟我们预想的一样,实际上还有中序和后续的遍历操作的代码,这里就不在说了,感兴趣的猿友们可以在我的码云地址下载对应的代码看看:

• 码云地址

那么关于顺序存储二叉树的学习就到这里了