बाइनरी पेड़ स्तर ऑर्डर ट्रैवर्सल

Question

तीन प्रकार के वृक्ष ट्रैवर्स इनऑर्डर, प्रीऑर्डर और पोस्ट ऑर्डर हैं।

एक चौथा, कम अक्सर इस्तेमाल किया जाता है, ट्रैवर्सल लेवल-ऑर्डर ट्रैवर्सल होता है। लेवल-ऑर्डर ट्रैवर्सल में, गहराई से "डी" पर सभी नोड्स गहराई से डी + 1 पर किसी भी नोड से पहले संसाधित होते हैं। लेवल-ऑर्डर ट्रैवर्सल अन्य ट्रैवर्सल से अलग होता है जिसमें यह पुनरावर्ती नहीं किया जाता है; एक कतार का उपयोग किया जाता है, रिकर्सन के अंतर्निहित ढेर के बजाय।

ऊपर पाठ टुकड़ा पर मेरे सवालों का

1. क्यों स्तरीय आदेश traversals रिकर्सिवली नहीं किया जाता है कर रहे हैं?
2. स्तर आदेश ट्रैवर्सल में कतार का उपयोग कैसे किया जाता है? छद्म कोड के साथ स्पष्टीकरण अनुरोध सहायक होगा।

धन्यवाद!

Answer 1

Level order traversal वास्तव में BFS है, जो प्रकृति द्वारा पुनरावर्ती नहीं है। यह Stack के बजाय Queue का उपयोग करता है ताकि अगले शिखर को खोला जाना चाहिए। इसके लिए कारण यह ट्रेवर्सल में है, तो आप एक FIFO क्रम में नोड्स खोलना चाहते हैं, एक LIFO आदेश, प्रत्यावर्तन

के रूप में मैं उल्लेख द्वारा प्राप्त करने के बजाय, स्तर आदेश वास्तव में एक BFS है, और उसके [BFS] छद्म कोड [विकिपीडिया से लिया] है:

1 procedure BFS(Graph,source): 
2  create a queue Q 
3  enqueue source onto Q 
4  mark source 
5  while Q is not empty: 
6   dequeue an item from Q into v 
7   for each edge e incident on v in Graph: 
8    let w be the other end of e 
9    if w is not marked: 
10     mark w 
11     enqueue w onto Q 

(*) एक पेड़ में, कोने अंकन, की जरूरत नहीं है, क्योंकि आप 2 अलग अलग रास्तों में एक ही नोड के लिए नहीं मिल सकता है।

Answer 2

आपको कोड स्निपेट के साथ भी Wikipedia में एक अच्छा अवलोकन मिलेगा।

Answer 3

void levelorder(Node *n) 
{ queue < Node * >q; 

    q.push(n); 


    while(!q.empty()) 
    { 
      Node *node = q.front(); 
      cout<<node->value; 
      q.pop(); 
      if(node->left != NULL) 
      q.push(node->left); 
      if (node->right != NULL) 
      q.push(node->right); 

    } 

} 

Answer 4

एक कतार के बजाय, मैंने इसे हल करने के लिए एक मानचित्र का उपयोग किया। यदि आप रुचि रखते हैं, तो एक नज़र डालें। मैं एक क्रंमोत्तर चंक्रमण कर के रूप में, मैं गहराई, जिस पर प्रत्येक नोड तैनात और एक ही स्तर

class Solution { public: map<int, vector<int> > levelValues; void recursivePrint(TreeNode *root, int depth){ if(root == NULL) return; if(levelValues.count(root->val) == 0) levelValues.insert(make_pair(depth, vector<int>())); levelValues[depth].push_back(root->val); recursivePrint(root->left, depth+1); recursivePrint(root->right, depth+1); } vector<vector<int> > levelOrder(TreeNode *root) { recursivePrint(root, 1); vector<vector<int> > result; for(map<int,vector<int> >::iterator it = levelValues.begin(); it!= levelValues.end(); ++it){ result.push_back(it->second); } return result; } };

पूरे समाधान यहां पाया जा सकता में मान एकत्र करने के एक नक्शे में महत्वपूर्ण के रूप में इस गहराई का उपयोग कर रहा है बनाए रखने के - http://ideone.com/zFMGKU समाधान प्रत्येक आंतरिक वेक्टर के साथ वेक्टरों का एक वेक्टर देता है जिसमें पेड़ में तत्व सही क्रम में होते हैं।

आप इसे यहां से सुलझाने की कोशिश कर सकते हैं - https://oj.leetcode.com/problems/binary-tree-level-order-traversal/

और, जैसा कि आप देख सकते हैं, हम भी इस रिकर्सिवली एक ही समय और कतार समाधान के रूप में अंतरिक्ष जटिलता में कर सकते हैं!

Answer 5

https://github.com/arun2pratap/data-structure/blob/master/src/main/java/com/ds/tree/binarytree/BinaryTree.java

पूरा के लिए ऊपर के लिंक के लिए बाहर देख सकते हैं।

public void levelOrderTreeTraversal(List<Node<T>> nodes){ 
    if(nodes == null || nodes.isEmpty()){ 
     return; 
    } 
    List<Node<T>> levelNodes = new ArrayList<>(); 
    nodes.stream().forEach(node -> { 
     if(node != null) { 
      System.out.print(" " + node.value); 
      levelNodes.add(node.left); 
      levelNodes.add(node.right); 
     } 
    }); 
    System.out.println(""); 
    levelOrderTreeTraversal(levelNodes); 
} 

इसके अलावा http://www.geeksforgeeks.org/

यहाँ

आप लगभग सभी डेटा संरचना से संबंधित जवाब मिल जाएगा देख सकते हैं।