基本概念
二叉树顺序存储是二叉树的一种存储方式。将二叉树存储在一个数组中，通过存储元素的下标反映元素之间的父子关系。用于一些特殊场合，如结点个数已知的完全二叉树或接近完全二叉树的二叉树。
重要性质
对于一棵有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。
对于非完全二叉树的存储一律转为完全二叉树处理，空缺的地方内容为空。
优缺点
- 对于完全二叉树或接近于完全的二叉树，用顺序存储可以省空间简化操作；否则，都不适宜用顺序存储。
- 顺序存储结构通病：必须预先给出数组的存储空间大小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);
}
}
|
参考
二叉树_顺序存储