E 'questa la strategia giusta per convertire un albero binario di ordini di livello in una lista doppiamente collegata?

Question

E 'questa la strategia giusta per convertire un albero binario di ordini di livello in una lista doppiamente collegata?

#1 da (1 voti)
#2 da (0 voti)

4

Quindi di recente mi sono imbattuto in questa domanda: creare una funzione che converta un albero binario di ordine in corso in una lista doppiamente collegata. Apparentemente, è una domanda di intervista comune.

Questa è la strategia che ho avuto - Basta fare un traversamento pre-ordine dell'albero, e invece di restituire un nodo, restituire un elenco di nodi, nell'ordine in cui li attraversi. restituire una lista e aggiungere il nodo corrente all'elenco in ogni punto. Per il caso base, restituisci il nodo stesso quando sei su una foglia.

quindi diresti

left = recursive_function(node.left)
right = recursive_function(node.right)
return(left.append(node.data)).append(right);'

È questo l'approccio giusto?

recursion algorithms list binary-tree

posta Ankit Soni 20.09.2011 - 09:26

fonte

2 risposte

Leggi altre domande sui tag recursion algorithms list binary-tree

Analizzatore di richieste / risposte HTTP per Android Creazione di un modello di prestazioni per un prodotto legacy

score 1 · Answer 1

Risulta essere:

MODIFICA: caso base semplificato

Ho implementato il codice in Java, sembra questo:

public DLLNode treeToList(TreeNode node, DLLNode list)
{   
    if (node.isLeaf())
      return new DLLNode(node.data);

    DLLNode left = treeToList(node.left, list);
    DLLNode right = treeToList(node.right, list);

    DLLNode ret = new DLLNode();

    ret.prev = left;
    ret.next = right;
    ret.data = node.data;

    return ret;
}

DLLNode è semplicemente definito con attributi pubblici DLLNode prev, DLLNode next, int data e TreeNode è definito con attributi pubblici TreeNode left, TreeNode right, int data . I costruttori che ho definito e la funzione isLeaf() sono ovvi.

Note: il codice esegue un attraversamento postorder, non preordinato come pensavo.

score 0 · Answer 2

Inizio e coda con un tag script

// load as html page.
// this will write "c1 b1 c2 a1 c3 b2 c4" to the browser

// test data
var c1 = {data: "c1"};
var c2 = {data: "c2"};
var c3 = {data: "c3"};
var c4 = {data: "c4"};
var b1 = {data: "b1", left: c1, right: c2};
var b2 = {data: "b2", left: c3, right: c4};
var a1 = {data: "a1", left: b1, right: b2};

// production function
var llist = function walktree(node)     
{   
    var l, r, head, tail;
    if ( node.left !== undefined)
    {
        l = walktree(node.left );
        node.prev = l.tail;
        l.tail.next = node;
        head = l.head;
    }
    else
    {
        head = node;
    }
    if ( node.right !== undefined)
    {
        r = walktree(node.right );
        node.next = r.head;
        r.head.prev = node;
        tail = r.tail;
    }
    else
    {
        tail = node;
    }
    return { head: head, tail: tail};
}(a1);


// test harness
var llnode = llist.head;
while ( llnode !== undefined)
{
    document.writeln( llnode.data );
    llnode = llnode.next;
}