在完整树的深度优先和广度优先遍历之间进行转换的函数

Question

问题:考虑一个具有l级的完整k-ary树,其节点在广度优先遍历中按其等级标记.按照深度优先遍历中遍历的顺序计算标签列表.

例如,对于具有3个级别的二叉树,所需列表为:[0 1 3 7 8 4 9 10 2 5 11 12 6 13 14]

实现此目的的一种方法是实际构建树结构并遍历它两次; 第一次遍历是广度优先,标记节点0,1,2,..当你去.第二次遍历是深度优先,报告标签0,1,3,7,..当你去.

我对避免在内存中构建树的方法感兴趣.我意识到这种树的大小与输出的大小相当,但我希望解决方案允许"流"输出(即不需要完全存储在内存中).

我也对伴侣问题感兴趣; 从根据深度优先遍历标记的树开始,并生成广度优先遍历的标签.我想在某种意义上,这个问题的解决方案将是第一个问题的双重解决方案.

Answer 1

这里有一些 javascript 似乎可以解决这个问题。

var arity = 2;
var depth = 3;

function look(rowstart, pos, dep) {
  var number = rowstart + pos;  
  console.log(number);  
  if (dep < depth-1) {
    var rowlen = Math.pow(arity, dep);
    var newRowstart = rowstart + rowlen;
    for (var i = 0; i < arity; i++) {
      look(newRowstart, pos*arity + i, dep+1);
    }    
  }  
}

look(0, 0, 0);

这是一种深度优先搜索，会计算下行过程中每个节点的 BFS 标签。

dep它使用当前深度、当前行中的水平位置 ( pos) 以及该行中第一个节点的标签 ( )来计算节点的标签rowstart。