Tüm ikili ağaçların inorder geçişinden yazdırılması

Question

Bu soruya bir röportajda rastladım. Bir ikili ağacın geçişi sırasına göre verilmiştir. Olası tüm ikili ağaçları ondan yazdır.

İlk düşünce:

biz dizideki sadece 2 unsurları var derseniz. 2,1 de. Daha sonra iki olası ağaç

   2 
       \ 
       1  
    1 
/
    2 

3 elemanları ki halinde

, 2,1,4 bulunmaktadır. Sonra 5 olası ağaç var.

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

Demek ki n unsurlar var temelde, o zaman n-1 şubeleri var (oğul,/veya). Bu n-1 şubelerini herhangi bir sırada düzenleyebiliriz. n = 3 için, n-1 = 2. Yani, 2 şubemiz var. Biz bu yolla 2 şube sağlayabilir:

/ \   \   /  /\ 
/  \  /   \ 

İlk girişimi:

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

Onları baskı için bir ağaç oluşturmak için fonksiyonu ve başka yazardım. Ağaçların

inşaat şöyledir:

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

kök değeri için sol ve kök değeri sağındaki değerlerinden inşa edilecek birden ağaçlar olduğunu gözlemleyin. Bu sol ve sağ ağaçların tüm kombinasyonları dahildir. Oldukça-yazıcıyı Yazma

bir egzersiz (sıkıcı bir) olarak bırakılır, ancak işlevi aslında ağaçların beklenen sayısını oluşturur biz test edebilirsiniz: alt problemlerden içine oldukça güzel

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

Bu sorun yıkar . Bir inorder geçişi göz önüne alındığında, bir kök seçtikten sonra, bundan önceki her şeyin sol alt ağaç ve her şeyin sağ alt ağacı olduğunu biliyoruz (ya muhtemelen boş).

Yani hemen root için tüm olası değerleri denemek ve yinelemeli sol & sağ alt ağaçlar için çözmek (örneğin ağaç sayısı gerçi çok çabuk büyür!)

Antonakos o gösterileri verilen kod olası tüm ağaçları numaralandırılamıyor Bunun nasıl yapılacağı, çözümün arzu edilenden daha fazla bellek kullanabilmesine rağmen. Bu, özete daha fazla durum ekleyerek ele alınabilir, böylece soldaki & için cevapların listelerini kaydetmek zorunda kalmaz ve sonunda birleştirir; bunun yerine bu işlemleri iç içe geçirir ve her ağacı bulunduğundan yazdırır.