Étant donné une liste de branches, comment trouver une liste d'arbres qui sont connectés ensemble

Disons que j'ai une liste de branches, comment trouver une liste d'arbres qui sont connectés ensemble? Le diagramme ci-dessous devrait illustrer mon point. L'entrée est une liste de branches dans un seul arbre, comme étiqueté, à savoir. 1, 2, 3 et ainsi de suiteÉtant donné une liste de branches, comment trouver une liste d'arbres qui sont connectés ensemble

Source

2010-04-22 Graviton

L'entrée ou la sortie? La question semble être la liste de gauche ... mais si c'est l'entrée, c'est quelque chose que vous avez déjà. – cHao

@ CHao, L'entrée est une liste d'arbres, '1',' 2', '3' et ainsi de suite – Graviton

... k, l'entrée n'a pas beaucoup de sens pour moi. Dois-je supposer que tous les «arbres» sont réellement connectés (et font donc partie du même arbre)? Et si oui, pourquoi les transmettez-vous comme une liste de nœuds, plutôt que comme un seul arbre? – cHao

Le processus est le suivant:

Créer une fonction qui accepte un nœud de l'arbre en tant que paramètre
Si le nœud n'a pas d'enfant, imprime la valeur du noeud courant et retourne.
Si le nœud a deux enfants, mettre fin à la liste actuelle des valeurs de nœud unique, récursif puis dans le noeud gauche, puis le nœud droit
Si le nœud a un enfant, l'ajouter à la liste des valeurs contenues dans la arbre, puis recurse dans ce noeud.
Continuer.

Source

2010-04-22 07:00:25

@Qu'est-ce qu'un nœud a plus de deux enfants? – Graviton

@Ngu - Il ne devrait pas cependant? Désolé, je suppose par votre image que c'est un arbre binaire? –

ce n'est pas binaire; comme le montre l'arbre '5',' 6', '7',' 8' – Graviton

Selon l'image, il existe une solution très simple. Faisons une liste, avec des éléments, qui sont des listes du même type. La procédure s'appellera tree_lists (liste, arborescence). Tout ce que vous devez faire est:

Regarder commune actuelle, vous ont le pointeur de la liste sur le premier élément de la liste.
S'il y a plus d'un enfant dans le nœud actuel: itérer chaque sous-arbre , incrémenter pointeur de la liste et appelant
tree_lists (liste [i], current_subtree) où i est le pointeur de liste et current_subtree est Sous-arbre actuel =)
Si un seul enfant existe, ajoutez simplement ce joint à l'élément de liste actuel et passez à suivant.
Bien sûr, les valeurs de liste et de pointeur de liste doivent être globales et modifiées en recurrence.

Source

2010-04-22 07:19:18 Anton

Étant donné une liste de branches, comment trouver une liste d'arbres qui sont connectés ensemble

Répondre

Questions connexes