इनऑर्डर ट्रैवर्सल

Question

से सभी बाइनरी पेड़ प्रिंट करना एक साक्षात्कार में इस प्रश्न में आया। बाइनरी पेड़ के विकृत ट्रैवर्सल को देखते हुए। इससे सभी संभावित बाइनरी पेड़ प्रिंट करें।

प्रारंभिक सोचा:

तो कहते हैं कि हम सरणी में केवल 2 तत्वों की है। 2,1 कहो फिर दो संभव पेड़

   2 
       \ 
       1  
    1 
/
    2 

तो 3 तत्वों कहो, 2,1,4 हैं। तब हमारे पास 5 संभव पेड़ हैं।

2    1   4   2   4 
    \   /\  /   \  /
    1   2 4  1    4  2 
    \     /   /  \ 
    4     2    1   1 

तो, मूल रूप से यदि हमारे पास एन तत्व हैं, तो हमारे पास एन -1 शाखाएं (बच्चे,/या) हैं। हम इन एन -1 शाखाओं को किसी भी क्रम में व्यवस्थित कर सकते हैं। एन = 3, एन -1 = 2. के लिए, तो, हमारे पास 2 शाखाएं हैं। हम इन तरीकों से 2 शाखाओं की व्यवस्था कर सकते हैं:

/ \   \   /  /\ 
/  \  /   \ 

प्रारंभिक प्रयास:

struct node *findTree(int *A,int l,int h) 
{ 
    node *root = NULL; 
    if(h < l) 
      return NULL; 
    for(int i=l;i<h;i++) 
    { 
      root = newNode(A[i]); 
      root->left = findTree(A,l,i-1); 
      root->right = findTree(A,i+1,h); 
      printTree(root); 
      cout<<endl; 
    } 

} 

Answer 1

मैं उन्हें मुद्रण के लिए पेड़ के निर्माण के लिए एक समारोह और एक अन्य लिखना चाहते हैं।

पेड़ों की निर्माण इस प्रकार है:

#include <vector> 
#include <iostream> 
#include <boost/foreach.hpp> 

struct Tree { 
    int value; 
    Tree* left; 
    Tree* right; 

    Tree(int value, Tree* left, Tree* right) : 
     value(value), left(left), right(right) {} 
}; 

typedef std::vector<Tree*> Seq; 

Seq all_trees(const std::vector<int>& xs, int from, int to) 
{ 
    Seq result; 
    if (from >= to) result.push_back(0); 
    else { 
     for (int i = from; i < to; i++) { 
      const Seq left = all_trees(xs, from, i); 
      const Seq right = all_trees(xs, i + 1, to); 
      BOOST_FOREACH(Tree* tl, left) { 
       BOOST_FOREACH(Tree* tr, right) { 
        result.push_back(new Tree(xs[i], tl, tr)); 
       } 
      } 
     } 
    } 
    return result; 
} 

Seq all_trees(const std::vector<int>& xs) 
{ 
    return all_trees(xs, 0, (int)xs.size()); 
} 

गौर करें कि जड़ मूल्य के लिए एक से अधिक पेड़ कि छोड़ दिया और जड़ मूल्य के अधिकार के लिए मूल्यों से निर्माण किया जा रहे हैं। इन बाएं और दाएं पेड़ों के सभी संयोजन शामिल हैं।

सुंदर-प्रिंटर लेखन एक व्यायाम (एक उबाऊ एक) के रूप में छोड़ दिया जाता है, लेकिन वह समारोह वास्तव में पेड़ों की अपेक्षित संख्या में निर्माण करती है हम परीक्षण कर सकते हैं: subproblems में काफी अच्छी तरह से

int main() 
{ 
    const std::vector<int> xs(3, 0); // 3 values gives 5 trees. 
    const Seq result = all_trees(xs); 
    std::cout << "Number of trees: " << result.size() << "\n"; 
} 

Answer 2

यह समस्या टूट जाती है । रूट को चुनने के बाद, एक इनऑर्डर ट्रैवर्सल को देखते हुए हम जानते हैं कि इससे पहले सबकुछ बाएं सबट्री है और सही सबट्री (या तो संभवतः खाली है) के बाद कुछ भी है।

तो सभी संभव पेड़ की गणना करने में, हम बस रूट के लिए सभी संभव मूल्यों कोशिश करते हैं और रिकर्सिवली छोड़ दिया & सही subtrees के लिए हल (जैसे पेड़ों की संख्या हालांकि काफी तेजी से बढ़ता है!)

antonakos प्रदान की कोड है कि पता चलता है यह कैसे करें, हालांकि वह समाधान वांछनीय से अधिक स्मृति का उपयोग कर सकता है। इसे रिकर्सन में अधिक राज्य जोड़कर संबोधित किया जा सकता है, इसलिए इसे बाईं ओर & के उत्तर के सूचियों को सहेजने की ज़रूरत नहीं है और अंत में उन्हें गठबंधन करें; इसके बजाय इन प्रक्रियाओं को घोंसला, और प्रत्येक पेड़ को यह पाया जाता है।