algorithm - preorden - Funciones para convertir entre profundidad primero y ancho primeros cruces de un árbol completo

recorrido de un arbol matematicas discretas

Question

Problema: Considere un árbol k-ary completo con l niveles, con nodos etiquetados por su rango en un primer cruce transversal. Calcule la lista de etiquetas en el orden en que se atraviesan en el primer recorrido de profundidad.

Por ejemplo, para un árbol binario con 3 niveles, la lista requerida es: [0 1 3 7 8 4 9 10 2 5 11 12 6 13 14]

Una forma de hacerlo es construir realmente una estructura de árbol y atravesarla dos veces; El primer cruce es ancho primero, etiquetando los nodos 0,1,2, mientras avanzas. El segundo recorrido es primero la profundidad, informando las etiquetas 0,1,3,7, mientras avanzas.

Me interesa un método que evite construir un árbol en la memoria. Me doy cuenta de que el tamaño de dicho árbol es comparable al tamaño de la salida, pero espero que la solución permita una salida de "transmisión" (es decir, una que no necesita almacenarse por completo en la memoria).

También estoy interesado en el problema compañero; comience con un árbol etiquetado de acuerdo con un primer recorrido de profundidad y genere las etiquetas de un primer cruce de ancho. Imagino que la solución a este problema será, en cierto sentido, dual al primer problema.

Answer 1

Aquí hay algunos javascript que parecen resolver el problema.

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);

Es una búsqueda en profundidad que calcula la etiqueta BFS de cada nodo en el camino hacia abajo.

Calcula la etiqueta de un nodo utilizando la profundidad actual dep , la posición horizontal en la fila actual ( pos ) y la etiqueta del primer nodo en la fila ( rowstart ).

Answer 2

En realidad, no necesitas construir el árbol. Puede hacer el primer recorrido de profundidad utilizando solo las etiquetas BFS en lugar de punteros a los nodos reales.

Usar etiquetas de posición BFS para representar los nodos en el árbol k-ary:

• La raíz es 0
• El primer hijo de cualquier nodo n es k*n + 1
• El hermano derecho de un nodo n , si tiene uno, es n+1

en el código se ve así:

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);
    }
}

En realidad, esto se usa todo el tiempo para representar un montón binario en una matriz: los nodos son los elementos de la matriz en orden BFS, y el árbol se recorre realizando estas operaciones en los índices.

Answer 3

Puede utilizar los algoritmos estándar DFS y BFS, pero en lugar de obtener los nodos secundarios de un nodo particular a partir de una estructura de árbol preconstruida, puede calcularlos según sea necesario.

Para un árbol de altura H , numerado en BFS, completo, el i -ésimo hijo de un nodo N en la profundidad D es:

K*N + 1 + i

Aquí se proporciona una derivación de esta fórmula cuando i = 0 (primer hijo).

Para un árbol de altura H completo H -numerado con DFS, el i -ésimo hijo de un nodo N en la profundidad D está dado por una fórmula mucho más fea:

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

Aquí hay una explicación aproximada de esta fórmula:

Para un nodo N en la profundidad D en un árbol Kary de altura H , numerado en DFS, su primer hijo es simplemente N + 1 porque es el siguiente nodo que se visitará en un recorrido de profundidad en primer lugar. El segundo hijo de N se visitará directamente después de visitar todo el subárbol enraizado en el primer hijo ( N + 1 ), que es en sí mismo un árbol completo Kary de altura H - (D + 1) . El tamaño de cualquier árbol Kary completo está dado por la suma de una serie geométrica finita como se explica aquí . El tamaño de dicho subárbol es la distancia entre el primero y el segundo hijo, y, de hecho, es la misma distancia entre todos los hermanos, ya que cada uno de sus subárboles tiene el mismo tamaño. Si llamamos a este step distancia, entonces:

1er niño es N + 1 2do niño es N + 1 + step 3er niño es N + 1 + step + step ... y así sucesivamente.

A continuación se muestra una implementación de Python (nota: la función dfs usa la fórmula BFS, porque está convirtiendo de DFS a BFS, y viceversa para la función 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)))

Lo anterior se imprimirá:

[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]