0

我尝试在 C++ 模板中编写一个简单的二叉树。在 main() 的第二行，我要声明

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

更新：

我添加了指向结构的指针。如何让它变得更好？谢谢！

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

1 回答 1

0

取 a template<typename>class NodeMaker，将其传递给父Node类型，用于两个子参数。

编写template<typename T>using Same=T;和模板结构修复{templateusing type=X;}`。

现在，

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

制作你想要的类型。

作为一个问题，这种类型的大小是无限的：你需要一种方法让Node内部Node消失。用来抱std::unique_ptr<>左右孩子？

于 2013-06-26T23:51:48.420 回答