Questo modello di dati è un elenco o un albero?

4

Utilizzando la sintassi python con il seguente diagramma di ambiente, l'insegnante ci ha insegnato che ci sono 11 alberi (contorno arancione) in questo diagramma, inclusa la foglia.

Èstatoinsegnato qui ,

Gli elenchi sono rappresentati come una fila di caselle adiacenti etichettate con l'indice, una per elemento. Ogni casella contiene un valore primitivo o punta a un valore composto. Ad esempio:

nested_list = [   [1, 2],    [],     [[3, False, None],[4, lambda : 5]]   ]

albero è un singolo valore chiamato foglia o una sequenza di alberi . In genere alcune restrizioni di tipo sono posizionate sulle foglie. E. un albero di numeri. Ad esempio:

tree = [     [1, [2], 3, []],      [[4], [5,6]],       7    ]

La mia domanda:

In generale, un albero può avere dati di tipo eterogenei? per esempio: posso dire, abc = [1, 2, 3, 4, lamda: 5] un albero con 5 foglie?

Nota: l'intenzione è capire se l'albero può avere dati di tipo eterogeneo

    
posta overexchange 16.07.2015 - 07:49
fonte

2 risposte

8

Questo dipende strongmente dalla definizione di elenco e albero .

Matematicamente elenco non significa nulla e albero è solo un sottoinsieme speciale di un grafico .

Escludendo dalla tua domanda, la definizione dell'insegnante albero è elenchi annidati . In tal caso, l'elenco della profondità di nidificazione di 0 è ancora un albero. Quindi

abc = [1, 2, 3, 4]

È un albero.

In questo caso, list è sottoinsieme di tree . Ogni lista è un albero, ma non tutti gli alberi sono una lista. Se hai operazioni che funzionano solo in elenco, solo le istanze che sono elenchi possono essere utilizzate come parametri, ma non quando sono solo albero.

Almeno è così che funzionerebbe in matematica. Nel caso di questo "pseudoesempio" di pitone non c'è davvero molta differenza tra albero e lista. Credo che tu ti stia confondendo, perché il tuo insegnante usa solo le strutture Python come definizioni e non definisce i termini in termini matematici non ambigui.

    
risposta data 16.07.2015 - 09:07
fonte
1

Penso che tu stia confondendo il problema usando espressioni lambda nella struttura. L'espressione lambda:5 non è né una lista né un numero. È una funzione Quindi la struttura dei dati nel tuo esempio non è un albero di numeri, poiché una delle foglie è una funzione piuttosto che un numero.

Ma ignorando il lambda, l'espressione [1, 2, 3, 4] è una lista, e anche un albero secondo la definizione dell'albero che fornisci (perché è una sequenza di alberi, dove ogni albero è una foglia). Questa non è una contraddizione, poiché secondo la definizione che fornisci, qualsiasi lista sarà anche un albero.

    
risposta data 20.07.2015 - 16:29
fonte

Leggi altre domande sui tag