Noeuds non frontières dans un arbre binaire - algorithme, structures de données, arbre binaire

J'ai un arbre binaire, je veux imprimer tous les nœuds non-frontières. Noeuds limites: - Tous les noeuds feuille + tous les noeuds situés sur le chemin de la racine au noeud le plus à gauche + tous les noeuds de la racine au noeud le plus à droite.

Je l'ai fait en utilisant un booléen supplémentaire dans l'arbrestructure pour identifier s’il s’agit ou non d’un nœud de délimitation puis faire une traversée et une impression sinon des nœuds de délimitation. Quelqu'un peut-il proposer une meilleure approche, car il utilise un espace supplémentaire (bien que très réduit)

Réponses:

Une observation qui pourrait vous être utile est qu’unUn nœud non limitatif dans un arbre binaire est un nœud qui (a) n’est pas une feuille et (b) est un nœud où, le long du chemin d’accès au nœud, vous faites un pas à gauche et un pas à droite. Par conséquent, une option serait de faire une traversée normale de l’arbre en vérifiant si vous êtes allé à gauche ou à droite en cours de route. Voici un pseudocode:

function printNonBoundaryNodesRec(root, goneLeft, goneRight) {
if (root == null or root is a leaf) return;

if (goneLeft and goneRight) print root.value
printNonBoundaryNodesRec(root.left, true, goneRight);
printNonBoundaryNodesRec(root.right, goneLeft, true);
}

function printNonBoundaryNodes(root) {
printNonBoundaryNodesRec(root, false, false);
}

J'espère que cela t'aides!