C++模板中的二叉樹

我嘗試在C++模板中編寫一個簡單的二叉樹。在main（）的第二行，我要聲明C++模板中的二叉樹

Node<string,Node,int>

第二個節點是錯誤的，因爲它是一個類模板，必須實例化爲

Node<string,Node<string,int,int>,int>

但是，隨着樹的生長，式增長。我怎樣才能使用第一個聲明？謝謝！

我的C++編譯器是g ++ 4.8.1，支持C++ 11。

#include <iostream> 
#include <string> 

using namespace std; 

template<typename T, typename Tl, typename Tr> 
struct Node { 
    // tree node 
    T top; 
    Tl left; 
    Tr right; 
    Node (const T& t=T(),const Tl& tl=Tl(),const Tr& tr=Tr()): 
    top(t), left(tl), right(tr){} 

}; 

int main() { 
    Node <string,int,int> n1 (string("+"), 1, 2); 
    // !!!wrong , should be Node<string,Node<string,int,int>,int> 
    Node<string,Node,int> n2 (string("*"), n1, 4); 
}

UPDATE：

我添加指針結構。如何讓它變得更好？謝謝！

#include <iostream> 
#include <string> 

using namespace std; 

template<typename T=string, typename Tl=int, typename Tr=int> 
struct Node { 
    // tree node 
    struct Node<T,Tl,Tr>* p_left; 
    struct Node<T,Tl,Tr>* p_right; 
    T top; 
    Tl left; 
    Tr right; 
    Node (struct Node<T,Tl,Tr>* pl=nullptr, struct Node<T,Tl,Tr>* pr=nullptr, 
     const T& t=T(),const Tl& tl=Tl(),const Tr& tr=Tr()): 
    p_left(pl), p_right(pr), top(t), left(tl), right(tr){} 
}; 

using tnode = struct Node<>; 

int main() { 
    tnode n1 (nullptr,nullptr,string("+"), 1, 2); 
    tnode n2 (&n1, nullptr,string("*"), 0,0); 
}

更新2，加上智能指針。

#include <iostream> 
#include <string> 
#include <memory> 

using namespace std; 

template<typename T=string, typename Tc=int> 
class Node { 
public: 
    Node (shared_ptr<Node> pl=nullptr, 
     shared_ptr<Node> pr=nullptr, 
     const T& t=T(), 
     const Tc& tl=Tc(), 
     const Tc& tr=Tc()): 
    p_left(pl), p_right(pr), v_top(t), v_left(tl), v_right(tr){} 

    ~Node() { 
    cout<<"Calling destructor"<<endl; 
    } 
private: 
    shared_ptr<Node> p_left; 
    shared_ptr<Node> p_right; 
    T v_top; 
    Tc v_left,v_right; 
}; 

using tNode = Node<>; 
using spNode = shared_ptr<tNode>; 

spNode create_tree() { 
    spNode n0 = make_shared<tNode>(nullptr,nullptr,string("*"), 7, 3); 
    spNode n1 = make_shared<tNode>(nullptr,n0,string("+"), 5, 6); 
    spNode n2 = make_shared<tNode>(n1, nullptr,string("+"), 3,4); 
    return n2;  
} 

int main() { 
    spNode n2 = create_tree(); 
}

來源

2013-06-26 davy

這看起來太奇怪了。是否有某些東西阻止你使用'template struct Node'並且僅僅爲分支保留2個指針到'Node '？ –

我只是試着寫它沒有指針。 – davy

樹木在某種指針或位置上工作得最好。你可以使用數組，鏈接字段將是數組索引。主要原因是在編譯期間，您不知道要使用多少個節點。因此在運行時使用動態內存。動態內存分配需要指針。 –

以一個template<typename>class NodeMaker，通過它的父Node型，兩個孩子PARAMS。

寫template<typename T>using Same=T;和模板結構固定{templateusing type = X;}`。

現在，

Node<string, Same, fixed<int>::template type>

讓你想要的類型。

作爲一個問題，這種類型的大小是無限的：你需要Node內Node消失的方式。使用std::unique_ptr<>來保持你的左右兒童？

來源

2013-06-26 23:51:48 Yakk

C++模板中的二叉樹

回答

相關問題