顺序存储二叉树

男娘i 2021-10-01 12:16 255阅读 0赞

# Overview #

顺序存储二叉树，是由数组转换成的二叉树，一个元素为数组的二叉树。

提供了数组转换成二叉树的思路

# 基本说明 #

![18721752-8985566782eff6e9.png][]

image.png

# 要求 #

将arr:\[1,2,3,4,5,6,7\]转换为二叉树，并能够前序，中序，后序查找。

![18721752-8cd96c3f70a4b320.png][]

image.png

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

![18721752-cacdfabe08787ed1.png][]

image.png

## notice： ##

这里n指的是数组中的索引，左右子节点公式计算的是对应数组的索引，而不是具体的数组的值。

比如3的左子节点：

3的index=2，

那么其左子节点索引为：

5，即对应数组arr\[5\]=6

右子节点索引：

6，即arr\[6\]=7

# code #

## ArrayBinaryTree ##

package com.pl.arithmetic.arrayBinaryTree;
    
    /**
     * <p>
     *
     * @Description: 数组二叉树，顺序二叉树
     * </p>
     * @ClassName ArrayBinaryTree
     * @Author pl
     * @Date 2020/11/6
     * @Version V1.0.0
     */
    public class ArrayBinaryTree {
        private int arr[];
    
        public ArrayBinaryTree(int[] arr) {
            this.arr = arr;
        }
    
        public void preOrder(){
            preOrder(0);
        }
    
        /**
         * 前序遍历
         *
         * @param index 数组索引，角标
         * @return void
         * @exception
         * @author silenter
         * @date 2020/11/6 21:57
        */
        public void preOrder(int index){
            //@1 先判断是否数组越界 和数组是否为空
            if (index>arr.length){
                System.out.println("无此节点");
                return;
            }
            if (arr==null && arr.length == 0){
                System.out.println("数组为空");
                return;
            }
            System.out.println(arr[index]);
            //数组角标和数组大小永远是小于关系
            //@2 左子树
            if (index*2+1<arr.length){
                preOrder(index*2+1);
            }
            //@3 右子树
            if (index*2+2<arr.length){
                preOrder(index*2+2);
            }
    
        }
    }

ArrBinaryTreeDemo

package com.pl.arithmetic.arrayBinaryTree;
    
    /**
     * <p>
     *
     * @Description: TODO
     * </p>
     * @ClassName ArrBinaryTreeDemo
     * @Author pl
     * @Date 2020/11/6
     * @Version V1.0.0
     */
    public class ArrBinaryTreeDemo {
    
        public static void main(String[] args) {
            int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
            //创建一个 ArrBinaryTree
            ArrayBinaryTree arrBinaryTree = new ArrayBinaryTree(arr);
            arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7
        }
    }

输出

![18721752-ba02c523a6a9222f.png][]

image.png

[18721752-8985566782eff6e9.png]: /images/20210918/bd74e2549f054eebaeec0d5719179f67.png
[18721752-8cd96c3f70a4b320.png]: /images/20210918/d4ab503163434fb59624fc7b767d51c8.png
[18721752-cacdfabe08787ed1.png]: /images/20210918/f18c789e634f47b6a8681a63813ea4ba.png
[18721752-ba02c523a6a9222f.png]: /images/20210918/9f4968f6b20f43cbb82c06cb72023752.png