Comment imprimer les données dans un arbre binaire, niveau par niveau, en commençant par le haut?

Question

Ceci est une question d'interview

Je pense à une solution. Il utilise la file d'attente.

public Void BFS()  
{ 
    Queue q = new Queue();  
    q.Enqueue(root);  
    Console.WriteLine(root.Value); 

    while (q.count > 0) 
    { 
     Node n = q.DeQueue(); 
     if (n.left !=null) 
     { 
      Console.Writeln(n.left); 
      q.EnQueue(n.left); 
     } 
     if (n.right !=null) 
     { 
      Console.Writeln(n.right); 
      q.EnQueue(n.right); 
     } 
    } 
}  

Peut-on penser à une meilleure solution que celle-ci, qui n'utilise pas la file d'attente?

Answer 1

La traversée de niveau par niveau est connue sous le nom de parcours transversal en largeur. L'utilisation d'une file d'attente est la bonne façon de le faire. Si vous vouliez effectuer une première traversée en profondeur, vous utiliseriez une pile.

La façon dont vous l'avez n'est pas tout à fait standard cependant. Voici comment ça devrait être.

public Void BFS()  
{  
Queue q = new Queue(); 
q.Enqueue(root);//You don't need to write the root here, it will be written in the loop 
while (q.count > 0) 
{ 
    Node n = q.DeQueue(); 
    Console.Writeln(n.Value); //Only write the value when you dequeue it 
    if (n.left !=null) 
    { 
     q.EnQueue(n.left);//enqueue the left child 
    } 
    if (n.right !=null) 
    { 
     q.EnQueue(n.right);//enque the right child 
    } 
} 
} 

Modifier

est ici l'algorithme au travail. que vous aviez un arbre comme ceci:

 1 
    /\ 
    2 3 
//\ 
4 5 6 

En premier lieu, la racine (1) serait en file d'attente. La boucle est ensuite entrée. Le premier élément de la file d'attente (1) est retiré et imprimé. Les enfants de 1 sont placés de gauche à droite, la file d'attente contient {2, 3} Retour au début de la boucle Le premier élément de la file d'attente (2) est retiré et imprimé Les enfants de 2 sont placés de gauche à droite, la file d'attente maintenant contient {3, 4} retour au début de la boucle ...

La file d'attente contient ces valeurs sur chaque boucle

1: {1}

2: {2, 3}

3: { 3, 4}

4: {4, 5, 6}

5: {5, 6}

6: {6}

7: {} // vide, boucle se termine

sortie:

Answer 2

Voyons voir des solutions Scala.Tout d'abord, je vais définir un arbre binaire très basique:

case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]]) 

Nous allons utiliser l'arbre suivant:

1 
/\ 
    2 3 
//\ 
4 5 6 

Vous définissez l'arbre comme ceci:

val myTree = Tree(1, 
        Some(Tree(2, 
          Some(Tree(4, None, None)), 
          None 
         ) 
       ), 
        Some(Tree(3, 
          Some(Tree(5, None, None)), 
          Some(Tree(6, None, None)) 
         ) 
       ) 
      ) 

Nous » ll définira une fonction breadthFirst qui traversera l'arbre en appliquant la fonction désirée à chaque élément. Avec cela, nous allons définir une fonction d'impression et l'utiliser comme ceci:

def printTree(tree: Tree[Any]) = 
    breadthFirst(tree, (t: Tree[Any]) => println(t.value)) 

printTree(myTree) 

Maintenant, la solution Scala, listes récursive, mais pas les files d'attente:

def breadthFirst[T](t: Tree[T], f: Tree[T] => Unit): Unit = { 
    def traverse(trees: List[Tree[T]]): Unit = trees match { 
    case Nil => // do nothing 
    case _ => 
     val children = for{tree <- trees 
         Some(child) <- List(tree.left, tree.right)} 
         yield child 
     trees map f 
     traverse(children) 
    } 

    traverse(List(t)) 
} 

Ensuite, la solution Scala, file d'attente, pas récursion:

def breadthFirst[T](t: Tree[T], f: Tree[T] => Unit): Unit = { 
    import scala.collection.mutable.Queue 
    val queue = new Queue[Option[Tree[T]]] 
    import queue._ 

    enqueue(Some(t)) 

    while(!isEmpty) 
    dequeue match { 
     case Some(tree) => 
     f(tree) 
     enqueue(tree.left) 
     enqueue(tree.right) 
     case None => 
    } 
} 

cette solution récursive est entièrement fonctionnelle, bien que j'ai un sentiment de malaise qu'il peut être encore simplifiée.

La version de la file d'attente n'est pas fonctionnelle, mais elle est très efficace. Le truc sur l'importation d'un objet est inhabituel dans Scala, mais mis à profit ici.

Answer 3

Pour imprimer par niveau, vous pouvez stocker les informations de niveau avec le nœud sous la forme d'un tuple à ajouter à la file d'attente. Ensuite, vous pouvez imprimer une nouvelle ligne chaque fois que le niveau est modifié. Voici un code Python pour le faire.

from collections import deque 
class BTreeNode: 
    def __init__(self, data, left=None, right=None): 
     self.data = data 
     self.left = left 
     self.right = right 

    def printLevel(self): 
     """ Breadth-first traversal, print out the data by level """ 
     level = 0 
     lastPrintedLevel = 0 
     visit = deque([]) 
     visit.append((self, level)) 
     while len(visit) != 0: 
      item = visit.popleft() 
      if item[1] != lastPrintedLevel: #New line for a new level 
       lastPrintedLevel +=1 
       print 
      print item[0].data, 
      if item[0].left != None: 
       visit.append((item[0].left, item[1] + 1)) 
      if item[0].right != None: 
       visit.append((item[0].right, item[1] + 1)) 

Answer 4

Puisque la question nécessite l'impression du niveau de l'arbre par niveau, il devrait y avoir un moyen de déterminer quand imprimer le caractère de nouvelle ligne sur la console. Voici mon code qui essaie de faire la même chose en ajoutant noeud NewLine à la file d'attente,

void PrintByLevel(Node *root) 
{ 
    Queue q; 
    Node *newline = new Node("\n"); 
    Node *v; 
    q->enque(root); 
    q->enque(newline); 

    while(!q->empty()) { 
     v = q->deque(); 
     if(v == newline) { 
     printf("\n"); 
     if(!q->empty()) 
      q->enque(newline); 
     } 
     else { 
     printf("%s", v->val); 
     if(v->Left) 
      q-enque(v->left); 
     if(v->right) 
      q->enque(v->right); 
     } 
    } 
    delete newline; 
} 

Answer 5

public class LevelOrderTraversalQueue {  

    Queue<Nodes> qe = new LinkedList<Nodes>(); 

    public void printLevelOrder(Nodes root)  
    { 
     if(root == null) return; 

     qe.add(root); 
     int count = qe.size(); 

     while(count!=0) 
     { 
      System.out.print(qe.peek().getValue()); 
      System.out.print(" "); 
      if(qe.peek().getLeft()!=null) qe.add(qe.peek().getLeft()); 
      if(qe.peek().getRight()!=null) qe.add(qe.peek().getRight()); 
      qe.remove(); count = count -1; 
      if(count == 0) 
      { 
       System.out.println(" "); 
       count = qe.size(); 
      } 
     }   
    } 

} 

Answer 6

Je peaufiné la réponse afin qu'il affiche les noeuds nuls et imprime en hauteur. Était en fait assez décent pour tester l'équilibre d'un arbre noir rouge.
peut également ajouter la couleur dans la ligne d'impression pour vérifier la hauteur du noir.

Queue<node> q = new Queue<node>(); 
    int[] arr = new int[]{1,2,4,8,16,32,64,128,256}; 
    int i =0; 
    int b = 0; 
    int keeper = 0; 
    public void BFS() 
    { 


     q.Enqueue(root); 
     while (q.Count > 0) 
     { 

      node n = q.Dequeue(); 

      if (i == arr[b]) 
      { 

       System.Diagnostics.Debug.Write("\r\n"+"("+n.id+")"); 
       b++; 
       i =0 ; 
      } 
      else { 

       System.Diagnostics.Debug.Write("(" + n.id + ")"); 

      } 
      i++; 


      if (n.id != -1) 
      { 



       if (n.left != null) 
       { 

        q.Enqueue(n.left); 
       } 
       else 
       { 
        node c = new node(); 
        c.id = -1; 
        c.color = 'b'; 
        q.Enqueue(c); 
       } 

       if (n.right != null) 
       { 

        q.Enqueue(n.right); 
       } 
       else 
       { 
        node c = new node(); 
        c.id = -1; 
        c.color = 'b'; 
        q.Enqueue(c); 

       } 
      } 

     } 
     i = 0; 
     b = 0; 
     System.Diagnostics.Debug.Write("\r\n"); 
    } 

Answer 7

Essayez celui-ci (code complet):

class HisTree 
{ 
    public static class HisNode 
    { 
     private int data; 
     private HisNode left; 
     private HisNode right; 

     public HisNode() {} 
     public HisNode(int _data , HisNode _left , HisNode _right) 
     { 
      data = _data; 
      right = _right; 
      left = _left; 
     } 
     public HisNode(int _data) 
     { 
      data = _data; 
     } 
    } 

    public static int height(HisNode root) 
    { 
     if (root == null) 
     { 
      return 0; 
     } 

     else 
     { 
      return 1 + Math.max(height(root.left), height(root.right)); 
     } 
    } 


    public static void main(String[] args) 
    { 
//   1 
//  /\ 
//  / \ 
//  2  3 
// /\ /\ 
//  4 5 6 7 
// /
// 21 

     HisNode root1 = new HisNode(3 , new HisNode(6) , new HisNode(7)); 
     HisNode root3 = new HisNode(4 , new HisNode(21) , null); 
     HisNode root2 = new HisNode(2 , root3 , new HisNode(5)); 
     HisNode root = new HisNode(1 , root2 , root1); 
     printByLevels(root); 
    } 


    private static void printByLevels(HisNode root) { 

     List<HisNode> nodes = Arrays.asList(root); 
     printByLevels(nodes); 

    } 

    private static void printByLevels(List<HisNode> nodes) 
    { 
     if (nodes == null || (nodes != null && nodes.size() <= 0)) 
     { 
      return; 
     } 
     List <HisNode> nodeList = new LinkedList<HisNode>(); 
     for (HisNode node : nodes) 
     { 
      if (node != null) 
      { 
       System.out.print(node.data); 
       System.out.print(" , "); 
       nodeList.add(node.left); 
       nodeList.add(node.right); 
      } 
     } 
     System.out.println(); 
     if (nodeList != null && !CheckIfNull(nodeList)) 
     { 
      printByLevels(nodeList);  
     } 
     else 
     { 
      return; 
     } 

    } 


    private static boolean CheckIfNull(List<HisNode> list) 
    { 
     for(HisNode elem : list) 
     { 
      if (elem != null) 
      { 
       return false; 
      } 
     } 
     return true; 
    } 
} 

Answer 8

C++:

struct node{ 
    string key; 
    struct node *left, *right; 
    }; 

    void printBFS(struct node *root){ 
    std::queue<struct node *> q; 
    q.push(root); 

    while(q.size() > 0){ 
     int levelNodes = q.size(); 
     while(levelNodes > 0){ 
     struct node *p = q.front(); 
     q.pop(); 
     cout << " " << p->key ; 
     if(p->left != NULL) q.push(p->left); 
     if(p->right != NULL) q.push(p->right); 
     levelNodes--; 
     } 
     cout << endl; 
    } 
    } 

Entrée:

arbre équilibré créé à partir de:

string a[] = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n"}; 

Sortie:

g 
c k 
a e i m 
b d f h j l n 

Algorithm:

1. Créer un ArrayList de noeuds de liste chaînée.
2. Effectuez la traversée d'ordre de niveau à l'aide de la file d'attente (première recherche étendue).
3. Pour obtenir tous les nœuds à chaque niveau, avant de sortir un nœud de la file d'attente, stockez la taille de la file d'attente dans une variable, disons que vous l'appelez levelNodes.
4. Maintenant, alors que levelNodes> 0, supprimez les noeuds et imprimez-le et ajoutez leurs enfants dans la file d'attente.
5. Après cette boucle while mettre un saut de ligne.

P.S: Je sais que l'OP a dit, pas de file d'attente. Ma réponse est juste pour montrer si quelqu'un est à la recherche d'une solution C++ en utilisant la file d'attente.

Answer 9

Bien sûr, vous n'avez pas besoin d'utiliser la file d'attente. C'est en python.

# Function to print level order traversal of tree 
def printLevelOrder(root): 
    h = height(root) 
    for i in range(1, h+1): 
     printGivenLevel(root, i) 


# Print nodes at a given level 
def printGivenLevel(root , level): 
    if root is None: 
     return 
    if level == 1: 
     print "%d" %(root.data), 
    elif level > 1 : 
     printGivenLevel(root.left , level-1) 
     printGivenLevel(root.right , level-1) 


""" Compute the height of a tree--the number of nodes 
    along the longest path from the root node down to 
    the farthest leaf node 
""" 
def height(node): 
    if node is None: 
     return 0 
    else : 
     # Compute the height of each subtree 
     lheight = height(node.left) 
     rheight = height(node.right) 
     return max(lheight, reight)