数据结构-顺序存储二叉树

文章目录

---

前言

大家好,今天给大家讲一下顺序存储二叉树

---

一 . 什么是顺序存储二叉树

顺序存储二叉树是一种将二叉树的节点按照从上到下、从左到右的顺序存储在数组中的方法。具体来说，顺序存储二叉树将二叉树的根节点存储在数组的第一个位置，然后按照从上到下、从左到右的顺序将二叉树的其他节点依次存储在数组中。

对于任意一个节点的索引为i（i从1开始),其左子节点的索引为2i，右子节点的索引为2i+1。这样，通过数组的索引关系，可以方便地找到节点的父节点、左子节点和右子节点。

顺序存储二叉树的优点是可以使用数组的随机访问特性快速找到节点，不需要通过指针进行遍历。缺点是当二叉树的节点数较少时，可能会浪费较多的存储空间。此外，如果二叉树需要进行频繁的插入和删除操作，顺序存储二叉树的效率会较低。

 顺序存储二叉树的特点:

1)顺序二叉树通常只考虑完全二叉树

2)第n个元素的左子节点为  2 * n + 1

3)第n个元素的右子节点为  2 * n + 2

4)第n个元素的父节点为  (n-1) / 2

5)n : 表示二叉树中的第几个元素(按0开始编号如上图所示)

二 . 模拟实现

准备工作

// 编写一个ArrBinaryTree类,实现顺序存储二叉树遍历
class ArrBinaryTree{
 
    private int[] arr;// 存放数据节点的数组
 
    public ArrBinaryTree(int[] arr){
        this.arr = arr;
    }
 
}

需求: 给你一个数组{1,2,3,4,5,6,7} 要求以二叉树前中后序遍历的方式进行遍历

前序遍历

思路分析

1. 定义一个指针变量index，初始值为1，表示从根节点开始遍历。
2. 从数组中取出索引为index的节点，并对其进行操作（如打印节点值）。
3. 将index的值更新为其左子节点的索引，即index = 2 * index。
4. 重复步骤2和步骤3，直到index超出数组的范围或者取出的节点为空。
5. 如果index超出数组的范围，则遍历结束；否则，将index的值更新为其右子节点的索引，即index = 2 * index + 1。
6. 重复步骤2到步骤5，直到index超出数组的范围。

代码实现

    public void preOrder(int index){
        // 如果数组为空或array.length == 0,直接返回
        if(arr == null || arr.length == 0){
            System.out.println("二叉树为空");
            return;
        }
        System.out.println(arr[index]);
        // 左递归
        if(index*2+1 < arr.length){
            preOrder(2*index+1);
        }
        // 右递归
        if(index*2+2 < arr.length){
            preOrder(index*2 +2);
        }
    }

 过程图解

 中序遍历和后序遍历过程和上图无本质区别,直接看代码

 /**
     * 顺序存储二叉树中序遍历
     * @param index 数组下标
     */
    public void infixOrder(int index) {
        // 如果数组为空或array.length == 0,直接返回
        if (arr == null || arr.length == 0) {
            System.out.println("二叉树为空");
            return;
        }
        // 左递归
        if(index*2+1 < arr.length){
            preOrder(2*index+1);
        }
        System.out.println(arr[index]);
        // 右递归
        if(index*2+2 < arr.length){
            preOrder(index*2 +2);
        }
    }
 
    /**
     * 顺序存储二叉树后序遍历
     * @param index 数组下标
     */
    public void postOrder(int index){
        // 如果数组为空或array.length == 0,直接返回
        if (arr == null || arr.length == 0) {
            System.out.println("二叉树为空");
            return;
        }
        // 左递归
        if(index*2+1 < arr.length){
            preOrder(2*index+1);
        }
        if(index*2+2 < arr.length){
            preOrder(index*2 +2);
        }
        System.out.println(arr[index]);
        // 右递归
    }

---

总结

大家根据图解过程应该很好理解,没什么难点,我们下一篇博客见。