Level Order Traversal eines Binärbaums

Question

void traverse(Node* root) 
{ 
    queue<Node*> q; 

    Node* temp_node= root; 

    while(temp_node) 
    { 
     cout<<temp_node->value<<endl; 

     if(temp_node->left) 
      q.push(temp_node->left); 

     if(temp_node->right) 
      q.push(temp_node->right); 

     if(!q.empty()) 
     { 
      temp_node = q.front(); 
      q.pop(); 
     } 
     else 
      temp_node = NULL; 
    } 
} 

Der oben angegebene Code ist mein Level Order Traversal Code. Dieser Code funktioniert gut für mich, aber eine Sache, die ich nicht mag, ist, dass ich explizit temp_node = NULL initialisiere oder ich benutze Pause. Aber es scheint mir kein guter Code zu sein.

Gibt es eine nette Implementierung als diese oder wie kann ich diesen Code besser machen?

Answer 1

void traverse(Node* root) 
{ 
    queue<Node*> q; 

    if (root) { 
     q.push(root); 
    } 
    while (!q.empty()) 
    { 
     const Node * const temp_node = q.front(); 
     q.pop(); 
     cout<<temp_node->value<<"\n"; 

     if (temp_node->left) { 
      q.push(temp_node->left); 
     } 
     if (temp_node->right) { 
      q.push(temp_node->right); 
     } 
    } 
} 

Dort gibt es keinen Spezialfall mehr. Und der Eindruck wird aufgeräumt, damit er leichter verstanden werden kann.

Alternativ:

als for Schleife getan. Persönlich mag ich die zusätzliche Variable. Der Variablenname ist eine schönere Abkürzung als "q.front()" die ganze Zeit zu sagen.

Answer 2

Versuchen:

void traverse(Node* root) 
{ 
    queue<Node*> q; 
    q.push(root); 

    while(!q.empty()) 
    { 
     Node* temp_node = q.front(); 
     q.pop(); 
     if (temp_node == NULL) 
     { continue; 
     } 

     cout << temp_node->value << endl; 

     q.push(temp_node->left); 
     q.push(temp_node->right); 
    } 
} 

Answer 3

Ein ernstes Problem mit Ihrem vorhandenen Code ist es stürzt ab, wenn es auf einem leeren Baum (root = NULL) genannt wird.

Sie müssen entscheiden, ob Sie NULL Zeiger in der Warteschlange haben wollen oder nicht.

Wenn nicht, können Sie nur Nicht-NULL Werte in die Warteschlange einreihen.

void traverse(Node* root) { 
    queue<Node*> q; 

    // no tree no level order. 
    if(root == NULL) { 
     return; 
    } 

    // push the root to start with as we know it is not NULL. 
    q.push(root); 

    // loop till there are nodes in the queue. 
    while(!q.empty()) { 
     // dequeue the front node. 
     Node *tmpNode = q.front(); 
     q.pop(); 

     // print it..we are sure it is not NULL. 
     cout<<tmpNode->value<<" "; 

     // enqueue left child if it exists. 
     if(tmpNode->left) { 
      q.push(tmpNode->left); 
     } 
     // enqueue right child if it exists. 
     if(tmpNode->right) { 
      q.push(tmpNode->right); 
     } 
    } 
} 

Alternativ, wenn Sie entscheiden NULL in der Warteschlange haben Sie tun können:

void traverse(Node* root) { 
    queue<Node*> q; 

    // push the root..even if it is NULL. 
    q.push(root); 

    // loop till the queue is not empty. 
    while(!q.empty()) { 
     // dequeue the front node. 
     Node *tmpNode = q.front(); 
     q.pop(); 

     // the dequeued pointer can be NULL or can point to a node. 
     // process the node only if it is not NULL.  
     if(tmpNode) {  
      cout<<tmpNode->value<<" "; 
      q.push(tmpNode->left); 
      q.push(tmpNode->right); 
     } 
    } 
} 

Die erste Methode als einen großen Baum bevorzugt wird, hat viel NULL Kinder (Kinder von Blattknoten), und es Es macht keinen Sinn, sie in die Warteschlange einzureihen, wenn wir sie später einfach nicht verarbeiten.

Answer 4

Sie auf diese Weise versuchen:

struct Node 
{ 
    char data; 
    Node* left; 
    Node* right; 
}; 
void LevelOrder(Node* root) 
{ 
    if(root == NULL) return; 
    queue<Node*> Q; 
    Q.push(root); 
    while(!Q.empty()) 
    { 
     Node* current = Q.front(); 
     cout<< current->data << " "; 
     if(current->left != NULL) Q.push(current->left); 
     if(current->right != NULL) Q.push(current->right); 
     Q.pop(); 
    } 
} 

Answer 5

Ich denke, über Code-Schnipsel erlaubt das Niveau um Traversal in Array-Format zu drucken. Dieser Code kann helfen, die Lösung in Form einer Ebenenreihenfolge zu schreiben.

vector<vector<int>> levelOrder(TreeNode* root) { 
    vector<vector<int>> a ; 
    vector<int> b; 
    if (root == NULL) return a; 
    std::queue<TreeNode *> q; 
    q.push(root); 
    int nodeCount ; 
    TreeNode* temp; 
    while(true){ 
     nodeCount = q.size(); 
     if (nodeCount == 0) break; 
     while(!nodeCount){ 
      temp = q.front(); 
      b.push_back(temp->val); 
      q.pop(); 
      if(temp->left != NULL) q.push(temp->left); 
      if(temp->right!= NULL) q.push(temp->right); 
      nodeCount-- ; 
     } 
     a.push_back(b); 
     b.resize(0); 
    } 
    return a; 
} 

Ausgang:

[ [1], 
    [2,3], 
    [4,5] 
] 

Answer 6

Meine Java-Lösung mit Queue Datenstruktur und BFS-Algorithmus:

void levelOrder(Node root) { 
     //LinkedList is class of Queue interface 
     Queue<Node> queue=new LinkedList<>(); 
     queue.add(root); 

     //Using BFS algorithm and queue used in BFS solution 
     while(!queue.isEmpty()) { 
       Node node=queue.poll(); 
       System.out.print(node.data+" "); 
       if(node.left!=null) 
       queue.add(node.left); 
       if(node.right!=null) 
       queue.add(node.right); 
       } 
    }