目录

二叉树的顺序存储

基本概念

二叉树顺序存储是二叉树的一种存储方式。将二叉树存储在一个数组中,通过存储元素的下标反映元素之间的父子关系。用于一些特殊场合,如结点个数已知的完全二叉树或接近完全二叉树的二叉树。

重要性质

对于一棵有n个结点的完全二叉树,结点按照从上至下和从左至右的顺序对所有结点从零开始到 n-1 进行顺序编号,则对于序号为i的结点(0≤i<n),有: (1)如果 i=0,则结点i是二叉树的根;如果i>0,则其双亲是结点(i-1)/2(整除)。 (2)如果2i+1≥n,则结点i无左孩子;否则,其左孩子是结点 2i+1。 (3)如果2i+2≥n,则结点i无右孩子;否则,其右孩子是结点 2i+2。

对于非完全二叉树的存储一律转为完全二叉树处理,空缺的地方内容为空。

优缺点

  1. 对于完全二叉树或接近于完全的二叉树,用顺序存储可以省空间简化操作;否则,都不适宜用顺序存储。
  2. 顺序存储结构通病:必须预先给出数组的存储空间大小MaxSize。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package com.eh.ftd.dsa.ds;

import java.util.Date;

/**
 * 二叉树的顺序存储结构
 *
 * @author David Li
 * @create 2020/06/27 15:14
 */
public class SequentialStorageOfBinaryTree {
    int[] data;

    public SequentialStorageOfBinaryTree(int[] data) {
        this.data = data;
    }

    /**
     * 前序遍历
     *
     * @param i 当前节点所在数组下标
     */
    void preOrder(int i) {
        // 1. 输出当前节点
        System.out.print(data[i] + " ");
        // 2. 如果左节点不为空则遍历左子树
        if (2 * i + 1 < data.length) {
            preOrder(2 * i + 1);
        }
        // 3. 如果右节点不为空则遍历右子树
        if (2 * i + 2 < data.length) {
            preOrder(2 * i + 2);
        }
    }

    /**
     * 中序遍历
     *
     * @param i 当前节点所在数组下标
     */
    void inOrder(int i) {
        // 1. 如果左节点不为空则遍历左子树
        if (2 * i + 1 < data.length) {
            inOrder(2 * i + 1);
        }
        // 2. 输出当前节点
        System.out.print(data[i] + " ");
        // 3. 如果右节点不为空则遍历右子树
        if (2 * i + 2 < data.length) {
            inOrder(2 * i + 2);
        }
    }

    /**
     * 后序遍历
     *
     * @param i 当前节点所在数组下标
     */
    void postOrder(int i) {
        // 1. 如果左节点不为空则遍历左子树
        if (2 * i + 1 < data.length) {
            postOrder(2 * i + 1);
        }
        // 2. 如果右节点不为空则遍历右子树
        if (2 * i + 2 < data.length) {
            postOrder(2 * i + 2);
        }
        // 3. 输出当前节点
        System.out.print(data[i] + " ");
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        SequentialStorageOfBinaryTree sequentialStorageOfBinaryTree = new SequentialStorageOfBinaryTree(arr);
        sequentialStorageOfBinaryTree.postOrder(0);
    }
}

参考

二叉树_顺序存储