打印所有遍歷中的二叉樹

在訪談中遇到了這個問題。給定一個二叉樹的遍歷。從中打印所有可能的二叉樹。打印所有遍歷中的二叉樹

最初的想法：

如果說我們只有2個元素在數組中。說2,1。然後兩個可能的樹木是

如果3個元素說，2,1,4。然後我們有5棵可能的樹。

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

所以，基本上如果我們有n個元素，那麼我們有n-1個分支（孩子，/或）。我們可以按任意順序排列這些n-1分支。對於n = 3，n-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; 
    } 

}

來源

2012-01-03 Deepti Jain

在你的例子中（1，2，4），最後的例子應該是從上到下的4-1-2嗎？ – 2012-01-03 23:40:24

@ChuckBlumreich數組是2,1,4。我猜這些數字是正確的.. – 2012-01-03 23:42:22

有趣的問題，但我不確定你的圖。我正在解釋'按順序'遍歷爲'訪問離開的孩子，訪問節點，訪問正確的孩子'（與預訂'訪問N，訪問L，訪問R'和訪問後'訪問L，訪問R，訪問N'）。如果這是正確的，那麼對'（2,1）'的兩棵樹就是'（root = 2，R child = 1）'和'（左邊的孩子= 2，根= 1）'，這不是你已經畫出了什麼。我對更復雜的圖表有類似的擔憂，但我可能完全誤解了一些東西。 – 2012-01-03 23:51:33

我會寫構建樹一個功能，另一個用於打印。

樹的結構是這樣的：

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

觀察到根值有一些從值向左和根值的右邊構成的多個樹。包括這些左右樹的所有組合。

寫漂亮的打印機被留作練習（一個無聊的一個），但我們可以測試該功能確實構造的樹木預期數量：

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

來源

2012-01-04 01:20:12 antonakos

這個問題分解很好地劃分爲若干子。給定一個遍歷，在選擇一個根之後，我們知道在那之前的所有東西都是左邊的子樹，並且在右邊的子樹（可能是空的）之後進行換算。

所以要列舉所有可能的樹，我們只是儘量根所有可能的值和遞歸解決左&右子樹（這種樹木的數量相當迅速的增長，但！）

antonakos提供的代碼演示如何做到這一點，雖然該解決方案可能會使用更多的內存而不是理想的。這可以通過向遞歸添加更多狀態來解決，因此它不必保存左側&右側的答案列表並在最後組合它們;而是嵌套這些進程，並在找到它時打印每個樹。

來源

2012-01-04 06:53:42

打印所有遍歷中的二叉樹

回答

相關問題