binario recorrido del árbol de búsqueda que compara dos punteros para la igualdad

Question

estoy leyendo el libro algoritmos Cormen (binario capítulo árbol de búsqueda) y se dice que hay dos maneras de recorrer el árbol sin recursividad:

usando pila y una solución más complicada pero elegante que no usa la pila, pero asume que dos punteros pueden ser probados por la igualdad

he implementado la primera opción (con pila), pero no saben cómo implementar nt el último. Esto no es una tarea, solo leer para educarme.

¿Alguna pista sobre cómo implementar la segunda en C#?

Answer 1

Cosa segura. No dijiste qué tipo de recorrido querías, pero aquí está el pseudocódigo para un recorrido en orden.

t = tree.Root; 
while (true) { 
    while (t.Left != t.Right) { 
    while (t.Left != null) { // Block one. 
     t = t.Left; 
     Visit(t); 
    } 
    if (t.Right != null) {  // Block two. 
     t = t.Right; 
     Visit(t); 
    } 
    } 

    while (t != tree.Root && (t.Parent.Right == t || t.Parent.Right == null)) { 
    t = t.Parent; 
    } 
    if (t != tree.Root) {  // Block three. 
    t = t.Parent.Right; 
    Visit(t); 
    } else { 
    break; 
    } 
} 

Para realizar un pedido previo o posterior, reorganiza el orden de los bloques.

Answer 2

Suponiendo que los nodos en el árbol son referencias y los valores son referencias, siempre puede llamar al ReferenceEquals method on the Object class estático para comparar si las referencias de dos nodos/valores son iguales.