बाइनरी ट्री का स्तर ऑर्डर ट्रैवर्सल

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; 
    } 
} 

उपरोक्त पोस्ट कोड मेरा लेवल ऑर्डर ट्रैवर्सल कोड है। यह कोड मेरे लिए ठीक काम करता है लेकिन एक चीज मुझे पसंद नहीं है मैं स्पष्ट रूप से temp_node = NULL शुरू कर रहा हूं या मैं ब्रेक का उपयोग करता हूं। लेकिन यह मेरे लिए एक अच्छा कोड प्रतीत नहीं होता है।

क्या इससे कोई साफ कार्यान्वयन है या मैं इस कोड को बेहतर कैसे बना सकता हूं?

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); 
     } 
    } 
} 

वहां, कोई और विशेष मामला नहीं है। और इंडेंटेशन साफ़ हो गया है ताकि इसे और आसानी से समझा जा सके।

वैकल्पिक रूप से:

एक for पाश के रूप में हो गया। व्यक्तिगत रूप से, मुझे अतिरिक्त चर पसंद है। परिवर्तनीय नाम हर समय 'q.front()' कहने से एक अच्छा शॉर्टेंड है।

Answer 2

प्रयास करें: अपने मौजूदा कोड के साथ

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

एक गंभीर समस्या है जब वह एक खाली पेड़ (root = NULL) पर कहा जाता है यह दुर्घटनाओं है।

आपको यह तय करने की आवश्यकता है कि क्या आप कतार में NULL पॉइंटर्स चाहते हैं या नहीं।

यदि नहीं, तो आप केवल गैर-NULL मानों को लागू कर सकते हैं।

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); 
     } 
    } 
} 

वैकल्पिक रूप से आप कतार में NULL के लिए आप कर सकते हैं तय है:

(पत्र-गांठ के बच्चों)

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); 
     } 
    } 
} 

पहली विधि एक बड़े पेड़ के रूप में पसंद किया जाता NULL बच्चों के बहुत सारे है और वहाँ जब हम बाद में उन्हें संसाधित नहीं करते हैं तो उन्हें कतार में लगाए जाने का कोई मतलब नहीं है।

Answer 4

आप इस तरह की कोशिश कर सकते हैं:

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

मुझे लगता है कि इसके बाद के संस्करण कोड के टुकड़े सरणी प्रारूप में स्तर आदेश ट्रावर्सल मुद्रित करने के लिए अनुमति देते हैं। यह कोड समाधान आदेश के रूप में समाधान लिखने में मदद कर सकता है।

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; 
} 

आउटपुट:

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

Answer 6

मेरे जावा समाधान कतार डेटा संरचना और BFS कलन विधि का उपयोग: स्थिरता के लिए टैब के साथ

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); 
       } 
    }