js实现二叉树之顺序存储

假设现在我们已经把数据存到数组中:[1, 3, 4, 6, 8, 10, 2, 5],其存储可表示如下:

1.png

对于任意节点,我们怎么找到它的父节点和左右子节点?

1
索引为0的节点,没有父节点,左子节点索引为1,右子节点索引为2;
索引为1的节点,父节点索引为0,左子结点索引为3,右子节点索引为4;
索引为2的节点,父节点索引为0,左子结点索引为5,右子节点为索引为6;
...
索引为i的节点,父节点索引为Math.floor((i - 1) / 2),左子结点索引为2i + 1,右字节点为索引为2i + 2

将数组表示二叉树的形式,应该长这样(最左边数字表示树的层序号):

2.png

表示成二叉树结构之后,我们该怎么索引节点? 一般会用到以下两个参数:

  • level,节点所在的层,从1开始
  • order,节点在当前层中的序号(从左至右),从1开始

例如上图,节点3可以通过level = 2, order = 1来定位,再如节点8,可以通过level = 3, order = 2来定位。

观察一下,我们可以发现以下规律(从根节点开始顺序左往右数):

1
第一层第一个节点序号:1
第二层第一个节点序号:2
第三层第一个节点序号:4
第四层第一个节点序号:8
...

第k层第一个节点:Math.pow(2, k - 1)

有了以上规律,我们现在就可以来映射一下levelorder与数组下标之间的关系:

1
2
3
4
5
// storage mapping function
// level、order从1开始
function smf(level, order) {
return Math.pow(2, level - 1) + order - 2;
}

为啥-2?因为数组的索引是从0开始的,而我定义的level、order都是从1开始的(其实你也可以让它们从0开始)。

通过以上函数获取索引之后,就可以直接从数组中取出节点。

基本操作

先定义一个构造器,表示二叉树类:

1
2
3
4
5
function SqBinaryTree(data) {
data = data || [];
// 顺序存储空间
this.nodes = data.slice(0);
}

data参数表示用户输入的数据,二叉树构造器要做的就是把数据存储到nodes中,然后我们就可以用树的形式来访问数据。

现在我们就可以通过以下方式来获得一颗顺序存储二叉树:

1
var sbt = new SqBinaryTree([1, 3, 4, 6, 8, 10, 2, 5]);

获取深度

一棵树的深度就是它的层数,怎么计算呢?

顺序存储可能不是紧凑的,比如:[1, undefined, 3, 2, 10, 12],其中的undefined表示该位置没有节点。

因此要计算深度得先从后往前找到最后一个非undefined的节点,该节点所在的索引+1就是总的节点数,然后就可以用一个循环来计算深度:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
SqBinaryTree.prototype.getDepth = function() {
var n = this.nodes.length;
// 找到最后一个节点
while(--n) {
if (this.nodes[n] !== undefined) {
break;
}
}
// 总节点数
n += 1;

var k = -1;

// 深度为k的二叉树最多有2^k - 1个节点
do {
k++;
} while (Math.pow(2, k) - 1 < n);

return k;
}

例如:

1
sbt.getDepth(); // 4

获取节点

获取指定位置的节点:

1
2
3
4
5
SqBinaryTree.prototype.getNode = function(level, order) {
var idx = smf(level, order);

return this.nodes[idx];
}

插入节点

在指定位置上插入节点时,如果待插入节点的位置上没有对应的父节点,则无法插入,如下图所示:

3.png

红色圆框表示待插入节点的位置,虚线框表示该位置上没有节点,此时如果在红色圆框位置插入节点,因为红色圆框的父节点虚线框的位置上不存在节点,因此插入失败:

1
2
3
4
5
6
7
8
9
SqBinaryTree.prototype.setNode = function(level, order, value) {
var idx = smf(level, order);
if (this.nodes[Math.floor((idx - 1) / 2)] === undefined) {
return false;
}

this.nodes[idx] = value;
return idx;
}

删除节点

本文实现的二叉树是一个普通的二叉树,没有特殊二叉排序树那种约束,因此删除节点时就不需要重建树了,直接把待删除节点的整颗子树都删掉即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
SqBinaryTree.prototype.deleteNode = function(level, order) {
var idx = smf(level, order);
if (this.nodes[idx] === undefined) {
return false;
}
var queue = [idx];
var k = queue.shift();
while(k !== undefined) {
if (this.nodes[2 * idx + 1] !== undefined) {
queue.push(2 * idx + 1);
}
if(this.nodes[2 * idx + 2] !== undefined) {
queue.push(2 * idx + 2);
}
// 删除节点
this.nodes[idx] = undefined;

k = queue.shift();
idx = k;
}

return true;
}

源代码已经放在Github上了,有兴趣的可以围观一下,传送门

参考文章