Imprimer des nœuds feuille dans un arbre binaire de droite à gauche?

Question

Je cherche une réponse à cela:

Trouver le pseudo code d'impression des nœuds feuilles dans un arbre binaire, de droite à gauche.

Je serais ravi d'entendre quelques idées. Un indice (pas une solution complète, bien sûr) ou un lien vers un sujet connexe qui pourrait m'aider à comprendre ce problème serait utile.

Answer 1

Vous devrez utiliser une méthode récursive en commençant par passer la méthode au nœud de niveau supérieur d'un arbre binaire. Dans le pseudo-code, je suppose que chaque nœud est défini avec des membres "droit" et "gauche" qui sont eux-mêmes des nœuds et une propriété "nom", pour imprimer quelque chose sur le nœud. La méthode pourrait ressembler à ceci, en aucune langue particulière puisque vous avez dit pseudocode:

function processNode(parent) { 
    if(parent.right = null AND parent.left = null) 
     print parent.name 
    if(parent.right <> null) 
     processNode(parent.right) 
    if(parent.left <> null) 
     processNode(parent.left) 
} 

Ensuite, vous commencez par:

processNode(topNode) 

Answer 2

Effectuer une première profondeur traversal de l'arbre, la manipulation du droit sous-arbres en premier et en imprimant seulement les nœuds feuilles.

La manière la plus simple d'implémenter ceci est avec une fonction récursive.

void printLeafNodes(BinaryTreeNode* treePtr) { 
    if(treePtr.leftChild == null && treePtr.rightChild == null) { 
    //This is a leaf node; print its value 
    } else { 
    //Recurse on right subtree 
    if(treePtr.rightChild != null) { 
     printLeafNodes(treePtr.rightChild); 
    } 
    //Recurse on left subtree 
    if(treePtr.leftChild != null) { 
     printLeafNodes(treePtr.leftChild); 
    } 
    } 
} 

Cette page est assez utile pour visualiser la solution: Tree Traversal.

Answer 3

Je sais que je suis ressuscitant un vieux fil, mais je pense qu'il peut aider les autres visualisation ce fil. Si vous parlez d'une question d'entrevue, je pense que la réponse récursive n'est qu'une petite partie de la réponse et l'intervieweur aimerait aussi entendre l'approche itérative. La traversée du droit à la gauche (impression) n'est pas une traversée pré/post/inorder régulière décrite dans le wiki. L'idée principale ici est que vous devez aller droit aussi longtemps que vous le pouvez et commencer à imprimer à partir du nœud le plus à droite en premier, puis son parent et seulement ensuite le sous-arbre gauche.

récursive:

printRightToLeft(Node root){ 
    if (root == null) 
    return; 

    // You can check root.right and root.left for null before calling the 
    // printRightToLeft function to avoid pushing unneeded data to recursion 
    // call stack. 

    printRightToLeft(root.right); 
    if (root.right == null && root.left == null) 
    print(root); 
    printRightToLeft(root.left); 
} 

itératifs:

printRightToLeft(Node root){ 
    if (root == null) 
    return; 

    Stack s = new Stack(); 
    s.push(root); 

    while(!s.isEmpty()){ 
    Node n = s.top(); 

    if (n.right != null && !n.visited){ 
     s.push(n.right); 
     n.visited = true; 
    } else { 
     s.pop(); 

     if (n.right == null && n.left == null) 
     print(n); 

     if (n.left != null) 
     s.push(n.left); 
    } 
} 

Answer 4

1. Effectuer dans l'ordre et ajouter que traversal nœuds feuilles à la liste des noeuds visités.
2. Rétablir la liste.

Ou

En fait, lors de la création de la liste à l'étape un donjon nœud ajoutant à la tête et laissez-le pointer vers le noeud précédent (plutôt que nœud précédent pointant vers un nouveau noeud).

Answer 5

nœuds feuilles d'impression tout en faisant l'ordre de niveau traversal dans l'ordre inverse à l'exclusion des noeuds qui ne sont pas des feuilles.

Answer 6

Do Inoder/Précommande/postorder Mais pour l'enfant d'abord Ensuite, allez à gauche Enfant

void postOrder(Node* root) 
{ 
if(root==NULL) 
return; 
postOrder(root->right); 
postOrder(root->left); 
if(root->left==NULL && root->right==NULL) 
cout << root->data <<" "; 
} 

Answer 7

void in(node* root){ 
if(root) 
    { 
     if(!root->left && !root->right) 
       cout<<root->data<<endl; 
     in(root->left); 
     in(root->right); 
    } } 

Vous pouvez faire quelque chose comme ça (code en C++).

L'idée derrière ce code est, faire inorder traversal/traverse traversée & vérifier si les enfants droits & gauche sont NULL ou non. Si c'est Null, cela signifie que c'est un nœud feuille.

Answer 8

Vous savez probablement comment parcourir une arborescence binaire dans l'ordre en utilisant la récursivité.

void visit(Node node) { 
    if(node.hasLeft()) { 
     visit(node.getLeft()); 
    } 
    handleValue(node.value); // print or whatever 
    if(node.hasRight()) { 
     visit(node.getRight()); 
    } 
} 

Vous remarquerez que lorsque vous faites cela, vous manipulez les feuilles déjà en ordre de gauche à droite, en plus de traiter les nœuds non-feuille.

Pour aller de droite à gauche, il suffit d'inverser l'ordre des instructions - alors visitez la droite, puis gérez la valeur, puis visitez la gauche.

Pour imprimer uniquement les nœuds feuille, vous devez simplement mettre une instruction if autour de handleValue, en lui indiquant de ne sortir que si le nœud est une feuille. Un noeud est une feuille s'il n'a ni noeud enfant gauche ni noeud droit.