C arbre binary, Comment faire la liste des feuilles de l’arbre

J’ai besoin de construire une liste de toutes les feuilles de l’arbre
Par exemple, j’ai l’arbre suivant:

6 / \ 4 3 /\ /\ 1 2 5 7 

treeNode typedef

 typedef struct treeNode { int data; struct treeNode* parent; struct treeNode* left; struct treeNode* right; } TreeNode; 

ma liste devrait être 1-> 2-> 5-> 7

liste typedef

 typedef struct list { ListNode* head; ListNode* tail; } List; 

listNode typedef

  typedef struct listNode { int data; struct listNode* next; } ListNode; 

Listnode-> data = TreeNode-> data; (les données de structure listnode)

La fonction doit être générique, j’ai fatigué plusieurs fonctions de récursion mais aucune n’a fonctionné

Des idées? Merci d’avance.

L’idée de base serait de parcourir l’arborescence dans l’ordre et de placer chaque nœud feuille rencontré dans la liste. Quelque chose comme ce qui suit:

 populateList(node) if(node == null) return populateList(node->left) if (node->left == null && node->right == null) pushToList(node) return populateList(node->right) 

Cela peut être fait avec la récursivité, comme vous l’avez essayé. Ce que vous devez faire est d’abord vérifier si vous avez atteint un nœud feuille, c’est-à-dire. si les pointeurs gauche et droit sont NULL , vous devez alors append le nœud à la liste. Le pseudo-code ressemble à ceci:

 getLeavesList(root) { if root is NULL: return if root is leaf_node: add_to_leaves_list(root) getLeavesList(root -> left) getLeavesList(root -> right) } 

Vous pouvez adapter ce code à n’importe quel langage de programmation. Donc, si la racine est NULL, si la fonction n’a reçu aucun pointeur valide, retournez un message d’erreur. Si la racine est une feuille, si les deux nœuds enfants gauche et droit sont NULL, vous devez l’append à la liste des nœuds feuilles. Ensuite, vous appelez la fonction de manière récursive avec les nœuds enfants gauche et droit.