树：顺序存储二叉树

绝地灬酷狼 2023-02-28 01:23 14阅读 0赞

# 1，顺序存储二叉树基本介绍 #

*  ***顺序存储二叉树是堆排序的基本思想***
 *  从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换为树，树也可以转换为数组，如下图所示  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE5NzYzODg_size_16_color_FFFFFF_t_70]
 *  顺序存储二叉树**只考虑完全二叉树**，并且元素间存在函数对应关系
    
     *  第n个元素的左子节点为：`index = 2 * n + 1`
     *  第n个元素的右子节点为：`index = 2 * n + 2`
     *  第n个元素的父节点为：`index = （n - 1）/ 2`
     *  其中n表示在完全二叉树中的第几个元素，同时也表示数组中的索引下标，**从0开始**

# 2，代码实现 #

package com.self.datastructure.tree;
    
    /** * 顺序存储二叉树 * 只对完全二叉树有效 * * @author pj_zhang * @create 2020-03-22 18:40 **/
    public class ArrayBinaryTree { 
    
        private static int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    
        /** * 讲一个二叉树的节点, 以数组的顺序按层依次存放, 则该二叉树肯定是一个完全二叉树 * 在生成的完全二叉树中: * 第n个元素的左子节点 index = 2 * n + 1 * 第n个元素的右子节点 index = 2 * n + 2 * 第n个元素的父节点为 index = (n - 1) / 2 * @param args */
        public static void main(String[] args) { 
            System.out.println("前序输出");
            preShowDetails(0);
            System.out.println("中序输出");
            middleShowDetails(0);
            System.out.println("后序输出");
            postShowDetails(0);
        }
    
        /** * 前序遍历 * 输出结果: 0, 1, 3, 7, 8, 5, 9, 2, 5, 6 * * @param index 开始索引 */
        public static void preShowDetails(int index) { 
            // 先输出当前节点
            System.out.println("前序输出: " + array[index]);
            // 再输出左侧节点
            if ((index * 2 + 1) < array.length) { 
                preShowDetails(index * 2 + 1);
            }
            // 再输出右侧节点
            if ((index * 2 + 2) < array.length) { 
                preShowDetails(index * 2 + 2);
            }
        }
    
        /** * 中序遍历 * 输出结果: 7, 3, 8, 1, 9, 4, 0, 5, 2, 6 * * @param index 开始索引 */
        public static void middleShowDetails(int index) { 
            // 先输出左侧节点
            if ((index * 2 + 1) < array.length) { 
                middleShowDetails(index * 2 + 1);
            }
            // 再输出当前节点
            System.out.println("中序输出: " + array[index]);
            // 最后输出右侧节点
            if ((index * 2 + 2) < array.length) { 
                middleShowDetails(index * 2 + 2);
            }
        }
    
        /** * 后序遍历 * 输出结构: 7, 8, 3, 9, 4, 1, 5, 6, 2, 0 * * @param index 开始索引 */
        public static void postShowDetails(int index) { 
            // 先输出左侧节点
            if ((index * 2 + 1) < array.length) { 
                postShowDetails(index * 2 + 1);
            }
            // 再输出右侧节点
            if ((index * 2 + 2) < array.length) { 
                postShowDetails(index * 2 + 2);
            }
            // 最后输出当前节点
            System.out.println("后序输出: " + array[index]);
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE5NzYzODg_size_16_color_FFFFFF_t_70]: /images/20230209/136f5ee369e34ae6b26caabd17d9536c.png