顺序存储二叉树实战

﹏ヽ暗。殇╰゛Y 2021-07-24 21:13 363阅读 0赞

# 一 概念 #

## 1 基本说明 ##

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树， 树也可以转换成数组。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

## 2 要求 ##

a 上图的二叉树的结点，要求以数组的方式来存放 arr : \[1, 2, 3, 4, 5, 6, 6\]。

b 要求在遍历数组 arr 时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历。

## 3 顺序存储二叉树的特点 ##

a 顺序二叉树通常只考虑完全二叉树。

b 第 n 个元素的左子节点为 2 \* n + 1。

c 第 n 个元素的右子节点为 2 \* n + 2。

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

e n : 表示二叉树中的第几个元素(按 0开始编号)。

# 二 顺序存储二叉树遍历 #

## 1 需求 ##

一个数组 \{1,2,3,4,5,6,7\}，要求以二叉树前序遍历的方式进行遍历。 前序遍历的结果应当为1,2,4,5,3,6,7

## 2 代码 ##

/**
    * @className: ArrBinaryTreeDemo
    * @description: 顺序存储二叉树
    * @date: 2021/3/20
    * @author: cakin
    */
    public class ArrBinaryTreeDemo {
        /**
         * 功能描述：顺序存储二叉树测试
         *
         * @param args 命令行
         * @author cakin
         * @date 2021/3/20
         */
        public static void main(String[] args) {
            int[] arr = {1, 2, 3, 4, 5, 6, 7};
            // 创建一个顺序存储二叉树
            ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
            arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7
        }
    }
    
    /**
    * @className: ArrBinaryTree
    * @description: 顺序存储二叉树数据结构，并实现前序遍历
    * @date: 2021/3/20
    * @author: cakin
    */
    class ArrBinaryTree {
        // 存储顺序存储二叉树数据结点的数组
        private int[] arr;
    
        public ArrBinaryTree(int[] arr) {
            this.arr = arr;
        }
    
        // 重载preOrder
        public void preOrder() {
            this.preOrder(0);
        }
    
        /**
         * 功能描述：顺序存储二叉树的前序遍历
         *
         * @param index 数组的下标
         */
        public void preOrder(int index) {
            // 如果数组为空，或者 arr.length = 0，不能进行顺序存储二叉树的前序遍历
            if (arr == null || arr.length == 0) {
                System.out.println("数组为空，不能进行顺序存储二叉树的前序遍历");
            }
            // 输出当前这个元素
            System.out.println(arr[index]);
            // 向左递归遍历
            if ((index * 2 + 1) < arr.length) {
                preOrder(2 * index + 1);
            }
            // 右递归遍历
            if ((index * 2 + 2) < arr.length) {
                preOrder(2 * index + 2);
            }
        }
    }

## 3 测试 ##

1
    2
    4
    5
    3
    6
    7
    
    Process finished with exit code 0

# 三 顺序存储二叉树的应用 #

八大排序算法中的堆排序，就会使用到顺序存储二叉树。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/6b6ce891b561401a94f766ebc7f64766.png