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

3 回答

• 2

  您实际上不需要构建树 . 您可以仅使用BFS标签而不是指向实际节点的指针来执行深度优先遍历 .

  使用BFS位置标签表示k-ary树中的节点：

  • 根是 0

  • 任何节点的第一个子节点 n 是 k*n + 1

  • 节点 n 的正确兄弟，如果有的话，是 n+1

  在代码中它看起来像这样：

  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顺序中的数组元素，并且通过对索引执行这些操作来遍历树 .

  回复于 2024-04-28T21:26:27+08:00
• 1

  您可以使用标准DFS和BFS算法，但不是从预构建的树结构获取特定节点的子节点，而是可以根据需要计算它们 .

  对于高度为H的BFS编号的完整K-ary树，深度为D的节点N的第i个子节点为：

  K*N + 1 + i
  

  提供 i = 0 （第一个孩子）here时该公式的推导 .

  对于高度为H的DFS编号的完整K-ary树，深度为D的节点N的第i个子项由更加丑陋的公式给出：

  N + 1 + i*step where step = (K^(H - D) - 1) / (K - 1)
  

  以下是对此公式的粗略解释：

  对于高度为H的DFS编号的K-ary树中的深度为D的节点N，其第一个子节点仅为N 1，因为它是在深度优先遍历中要访问的下一个节点 . 在访问以第一个孩子（N 1）为根的整个子树之后，将直接访问N的第二个孩子，该子树本身是高度为H - （D 1）的完整K-ary树 . 任何完整的K-ary树的大小由这里解释的有限几何级数的总和给出 . 所述子树的大小是第一和第二子节点之间的距离，并且实际上，所有兄弟节点之间的距离相同，因为它们的每个子树具有相同的大小 . 如果我们称这个距离为步骤，那么：第一个孩子是N 1第二个孩子是N 1步骤第3个孩子是N 1个步骤......依此类推 .

  下面是一个Python实现（注意： dfs 函数使用BFS公式，因为它正在从DFS转换为BFS，反之亦然_2977402_函数 . ）：

  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]
  

  回复于 2024-04-28T21:26:27+08:00
• 3

  这里有一些似乎可以解决问题的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 ）计算节点的标签 .

  回复于 2024-04-28T21:26:27+08:00