利用数组的特性实现二叉树

thousandd

这是一个纯粹的关于数据结构的示例1。该示例利用JavaScript的关联数组的特性，构造一个可以快速存取与遍历的二叉树。它的基本原理是：一个树节点（设序列为x）的左、右两个子节点，可以使用数组中序列为2x+1和2x+2两个元素来保存。其结构如下图所示：

本例代码先说明以下二叉树在该数组中的存储，再解释对该结构的深度与广度优先的遍历：

示例代码：
1// 使用数组构建的二叉树2
2var aBinTree = [1,2,3,4,5, ,6, , ,7];
3
4/**
5 * 示例1：深度优先遍历
6 */
7void function(tree, x) {
8 x in tree && (alert(tree[x]),
9  arguments.callee.call(this, tree, x*2+1),
10  arguments.callee.call(this, tree, x*2+2)
11 )
12}(aBinTree, 0);
13
14/**
15 * 示例2：广度优先遍历
16 */
17void function(tree, x) {
18 if (x in tree) {
19  var queue = { left:0, '0': x, length:1, leaf: 0 };
20  with (queue) {
21   do {
22    x=queue[left++], alert(tree[x]), leaf=2*x,
23    ++leaf in tree && (queue[length++] = leaf); // left
24    ++leaf in tree && (queue[length++] = leaf); // right
25   }
26   while (left<length);
27  }
28 }
29}(aBinTree, 0);
30
31/**
32 * 示例3：遍历完整树(无序3)
33 */
34for (var x in aBinTree) {
35 alert(aBinTree[x])
36}
示例说明：
示例1采用经典的递归方案来实现深度优先遍历，它主要利用了JavaScript的函数参数“非惰性求值”的特性。因此递归将首先发生在第9行的call()调用中，且等到所有由此发生的递归全部返回后，第10行的call()调用才开始进行。而这正是深度优先算法所需要的。
示例2使用先入先出队列来实现广度优先的遍历。通常情况下，该算法应被实现为如下的形式：
...
with ([x]) {
  do {
   x=shift(), alert(tree[x]), leaf=2*x;
   ++leaf in tree && push(leaf); // left
   ++leaf in tree && push(leaf); // right
  }
  while (length);
...
——在这个算法中，语句：
with ([idx]) ...
构建了一个数组直接量并打开了它的对象闭包，因此在该闭包中可以直接检测它的length属性以及调用push()和shift()方法。
然而shift()的使用将导致数组重排，所以会降低性能。因此在示例中构建了对象&#39;queue&#39;来模拟它，queue的数字属性(0..n)模拟了队列下标：queue[0..n]指向二叉树结点的序列x。在初始时，它只有下标0：
  var queue = { left:0, &#39;0&#39;: x, length:1, leaf: 0 };
随后的代码逻辑上与上面的使用数组的示例是一致的。不过由于不使用shift()来移除队列左侧的结点，因此它的效率较高。
示例3说明如何列举全树，不过由于for..in的实现机制的缘故，列举是无序的。如果需要一个有序的、广度优先的、全树的列举，那么可以使用增量的for语句——但不要忘记数组的某些下标是空值。
参考：

llyang

明白人不看,看的人不明白