用于在完整树的深度优先和广度优先遍历之间进行转换的函数
问题:考虑一个具有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，.随你去吧。
我感兴趣的是一种避免在内存中构建树的方法。我意识到这样的树的大小与输出的大小是相当的，但我希望解决方案将允许“流”输出(即不需要完全存储在内存中的输出)。
我也对伴生问题感兴趣；从根据深度优先遍历标记的树开始，并生成广度优先遍历的标签。我想这个问题的解决方案在某种意义上将是第一个问题的双重解决方案。
回答 3
Stack Overflow用户
发布于 2016-08-22 10:45:27
实际上，您并不需要构建树。您可以只使用BFS标签而不是指向实际节点的指针来执行深度优先遍历。
使用BFS位置标签来表示k-ary树中的节点：
根是任意节点的第一个子节点，如果有，则为n+1。
-
nis0 - The
k*n + 1 - The
nof a noden，isk*n + 1 - The
在代码中，它看起来像这样：
class Whatever
{
static void addSubtree(List<Integer> list, int node, int k, int levelsleft)
{
if (levelsleft < 1)
{
return;
}
list.add(node);
for (int i=0; i<k; i++)
{
addSubtree(list, node*k+i+1, k, levelsleft-1);
}
}
public static void main (String[] args) throws java.lang.Exception
{
int K = 2, LEVELS = 4;
ArrayList<Integer> list = new ArrayList<>();
addSubtree(list, 0, K, LEVELS);
System.out.println(list);
}
}这实际上一直用于表示数组中的二进制堆--节点是按BFS顺序排列的数组元素，通过对索引执行这些操作来遍历树。
Stack Overflow用户
发布于 2016-08-22 12:14:17
您可以使用标准的DFS和BFS算法，但是您可以根据需要进行计算，而不是从预先构建的树结构中获取特定节点的子节点。
对于高度为H的BFS编号的完整K元树，深度D处的节点N的第i个子节点为：
K*N + 1 + i向here提供i = 0 (第一个子项)时此公式的派生。
对于高度为H的DFS编号的完整K元树，深度D处的节点N的第i个子节点由一个丑陋得多的公式给出：
N + 1 + i*step where step = (K^(H - D) - 1) / (K - 1)下面是这个公式的大致解释：
对于深度为D的节点N，在高度为H的DFS编号的K元树中，其第一个子节点仅为N+1，因为它是深度优先遍历中要访问的下一个节点。在访问以第一个孩子为根的整个子树(N+1)之后，将直接访问N的第二个孩子，这本身就是一个高度为H - (D + 1)的完整K元树。正如here所解释的那样，任何完全的K元树的大小都是由一个有限几何级数的和给出的。所述子树的大小是第一和第二子树之间的距离，并且实际上，由于它们的每个子树的大小相同，所以所有兄弟姐妹之间的距离是相同的。如果我们称这个距离为step，那么：
第一个孩子是N + 1，第二个孩子是N + 1 + step，第三个孩子是N + 1 + step + step ...and，依此类推。
下面是一个Python实现(注意：dfs函数使用BFS公式，因为它将从DFS转换为BFS，反之亦然)。bfs函数：
def dfs(K, H):
stack = list()
push, pop = list.append, list.pop
push(stack, (0, 0))
while stack:
label, depth = pop(stack)
yield label
if depth + 1 > H: # leaf node
continue
for i in reversed(range(K)):
push(stack, (K*label + 1 + i, depth + 1))
def bfs(K, H):
from collections import deque
queue = deque()
push, pop = deque.append, deque.popleft
push(queue, (0, 0))
while queue:
label, depth = pop(queue)
yield label
if depth + 1 > H: # leaf node
continue
step = (K**(H - depth) - 1) // (K - 1)
for i in range(K):
push(queue, (label + 1 + i*step, depth + 1))
print(list(dfs(2, 3)))
print(list(bfs(2, 3)))
print(list(dfs(3, 2)))
print(list(bfs(3, 2)))上面的内容将打印出来：
[0, 1, 3, 7, 8, 4, 9, 10, 2, 5, 11, 12, 6, 13, 14]
[0, 1, 8, 2, 5, 9, 12, 3, 4, 6, 7, 10, 11, 13, 14]
[0, 1, 4, 5, 6, 2, 7, 8, 9, 3, 10, 11, 12]
[0, 1, 5, 9, 2, 3, 4, 6, 7, 8, 10, 11, 12]Stack Overflow用户
发布于 2016-08-22 10:41:14
这里有一些似乎可以解决这个问题的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)来计算节点的标签。
https://stackoverflow.com/questions/39070461
复制相似问题
腾讯云开发者
