J'essaie la traversée en zigzag d'un arbre binaire. Ce n'est pas l'impression 5 de la dernière branche, quelqu'un peut-il me dire pourquoi?

Question

Il n'y a pas de problème de retrait dans le code

class Node: 
     def __init__(self,key): 
     self.data=key 
     self.left=None 
     self.right=None 
    def zig_zag(root): 
    if not root: 
     return 
    s=[] 
    l=1 
    s.append(root) 

    while s: 
     q=[] 
     if l%2==1: 
      for i in reversed(s): 
       print(i.data,end=' ') 
       if i.left:q.append(i.left) 
       if i.right:q.append(i.right) 

     else: 
      for i in s: 
       print(i.data,end=' ') 
       if i.left:q.append(i.left) 
       if i.right:q.append(i.right) 
     print(q)  
     s=q 
     l+=1 
root=Node(1) 
root.left=Node(2) 
root.right=Node(3) 
root.left.left=Node(7) 
root.left.right=Node(6) 
root.right.left=Node(5) 
root.right.left=Node(4) 
zig_zag(root) 

La sortie je reçois est [1,2,3,4,6,7] au lieu de [1,2,3,4,5,6 , 7]. N'importe qui peut expliquer pourquoi il n'apporte pas 5 de la dernière branche de l'arbre

Answer 1

L'algorithme lui-même est bon.
Mais vous avez fait une erreur dans votre "noeud ajoutant code"
Vous définissez root.right.left deux fois

changement

root.right.left=Node(5) 
root.right.left=Node(4) 

à

root.right.left=Node(5) 
root.right.right=Node(4)