Pseudocodice per confrontare due alberi

Question

Questo è un problema che ho riscontrato alcune volte e non sono stato convinto di aver utilizzato la logica più efficiente.

Ad esempio, suppongo di avere due alberi: uno è una struttura di cartelle, l'altro è un "modello" in memoria di tale struttura di cartelle. Desidero confrontare i due alberi e produrre un elenco di nodi che sono presenti in un albero e non nell'altro - e viceversa.

Esiste un algoritmo accettato per gestirlo?

Answer 1

Sembra che tu voglia solo fare un traversal pre-ordine, in sostanza. Dove "visitare" un nodo significa controllare i bambini che sono in una versione ma non nell'altra.

Più precisamente: iniziare dalla radice. In ogni nodo, ottieni un set di elementi in ciascuna delle due versioni del nodo. La differenza simmetrica dei due set contiene gli elementi in uno ma non nell'altro. Stampa/stampa quelli. L'intersezione contiene gli elementi comuni a entrambi. Per ogni elemento nell'intersezione (presumo che non si guardi più avanti negli elementi mancanti da un albero), chiamare "visita" in modo ricorsivo su quel nodo per controllarne il contenuto. È un'operazione O (n), con un piccolo overhead ricorsivo.

Answer 2

public boolean compareTrees(TreeNode root1, TreeNode root2) { 
    if ((root1 == null && root2 != null) || 
     (root1 != null && root2 == null)) { 
    return false; 
    } 

    if (root1 == null && root2 == null) { 
    return true; 
    } 

    if (root1.data != root2.data) { 
    return false; 
    } 

    return compareTrees(root1.left, root2.left) && 
    compareTrees(root1.right, root2.right); 
} 

Answer 3

Un semplice codice di esempio in python.

class Node(object): 
    def __init__(self, val): 
    self.val = val 
    self.child = {} 

    def get_left(self): 
    #if left is not in the child dictionary that means the element does not have a left child 
    if 'left' in self.child: 
     return self.child['left'] 
    else: 
     return None 

    def get_right(self): 
    #if right is not in the child dictionary that means the element does not have a rigth child 
    if 'right' in self.child: 
     return self.child['right'] 
    else: 
     return None 


def traverse_tree(a): 
    if a is not None: 
    print 'current_node : %s' % a.val 
    if 'left' in a.child: 
     traverse_tree(a.child['left']) 

    if 'right' in a.child: 
     traverse_tree(a.child['right']) 



def compare_tree(a, b): 
    if (a is not None and b is None) or (a is None and b is not None): 
    return 0 
    elif a is not None and b is not None: 
    print a.val, b.val 
    #print 'currently comparing a : %s, b : %s, left : %s, %s , right : %s, %s' % (a.val, b.val, a.child['left'].val, b.child['left'].val, a.child['right'].val, b.child['right'].val) 
    if a.val==b.val and compare_tree(a.get_left(), b.get_left()) and compare_tree(a.get_right(), b.get_right()): 
     return 1 
    else: 
     return 0 
    else: 
    return 1 

#Example 
a = Node(1) 
b = Node(0) 
a.child['left'] = Node(2) 
a.child['right'] = Node(3) 
a.child['left'].child['left'] = Node(4) 
a.child['left'].child['right'] = Node(5) 
a.child['right'].child['left'] = Node(6) 
a.child['right'].child['right'] = Node(7) 
b.child['left'] = Node(2) 
b.child['right'] = Node(3) 
b.child['left'].child['left'] = Node(4) 
#b.child['left'].child['right'] = Node(5) 
b.child['right'].child['left'] = Node(6) 
b.child['right'].child['right'] = Node(7) 
if compare_tree(a, b): 
    print 'trees are equal' 
else: 
    print 'trees are unequal' 
#DFS traversal 
traverse_tree(a) 

Inoltre, è stato incollato un esempio che è possibile eseguire.

Answer 4

Se si utilizza un albero di ordinamento, come un albero AVL, è anche possibile attraversare l'albero in modo efficiente in ordine. Ciò restituirà i percorsi in ordine ordinato da "basso" a "alto". Quindi è possibile ordinare l'array di directory (ad esempio utilizzando quicksort) utilizzando lo stesso metodo di confronto utilizzato nell'algoritmo dell'albero.

Quindi iniziare a confrontare i due affiancati, avanzando all'elemento successivo spostando l'albero in ordine e controllando l'elemento successivo nell'array di directory ordinato.

Questo dovrebbe essere più efficace nella pratica, ma solo il benchmarking può dirlo.