数组和二叉树的构造函数

我正在使用STD向量制作二叉树。我显著削减下来，但低于总体思路是：数组和二叉树的构造函数

template <class DataType> 
class ArrayNode 
{ 
protected: 
    DataType* _info; 
    int _left; //index position of left node 
    int _right;//index position of right node 

public: 
    ArrayNode(const DataType& info, int left, int right); 
    virtual ~ArrayNode(); 
    DataType& getInfo(); 
} 

template <class DataType> 
class ArrayBinaryTree 
{ 
protected: 
    vector<ArrayNode<DataType>* >* theBinaryTree; 
    int _root; 
    int _numOfNodes; 
    int _size; 
    //etc. 
public: 
    ArrayBinaryTree(DataType info); 
    virtual ~ArrayBinaryTree(); 
}

你会如何创建一个构造函数，让你可以与getInfo()访问节点？我的想法是这样：

std::vector<ArrayNode<DataType>*> binaryTree(1); 

ArrayBTNode<DataType>* element = new ArrayNode<DataType>(info, -1, -1); //some generic data 
binaryTree.insert(binaryTree.begin(), 1, element); 
theBinaryTree = &binaryTree;

然后用类似(*theBinaryTree->at(0)).getInfo()访问。但是，使用这种类型的构造函数，getInfo()返回null。什么是建立访问构造函数的更好方法？

来源

2017-04-11 quil

您正在使用在函数结束时被销毁的向量的地址。 –

这么多的指针。为什么这么多指针？（我有一种可怕的感觉，ArrayNode :: ArrayNode'也说'_info = &info;'） – molbdnilo

所有'*'让我头晕 – user463035818

让我稍微改变一下界面，因为我没有看到将矢量保存为指针的要点。这同样适用于存储在向量数据以及用于在节点数据：

template <class DataType> 
class ArrayNode 
{ 
protected: 
    DataType _info; 
    // ... rest of ArrayNode interface 
} 

template <class DataType> 
class ArrayBinaryTree { 
protected: 
    vector<ArrayNode<DataType> > theBinaryTree; // not pointers anymore 
    int _root = -1; // something that tells you no values are present 
    // You need size and numOfNodes attributes 
    // You get both of these things by calling size() method of std::vector 
    // etc. 
public: 
    ArrayBinaryTree(DataType info); 
    virtual ~ArrayBinaryTree(); 
}

构造器可以例如实现像这样的（假设它初始化根节点）：

ArrayBinaryTree(DataType info) { 
    theBinaryTree.push_back(ArrayNode<DataType>(info, -1, -1)); 
    _root = 0; 
}

甚至更好，你可以使用初始化列表：

ArrayBinaryTree(DataType info) 
     : theBinaryTree({ ArrayNode<DataType>(info, -1, -1) }), 
     _root(0) {}

我不知道你是否有过载体，或者如果它实现它只是你的设计选择。如果这只是您的设计选择，我会建议重新设计它。假设这个简化的接口：

template< typename T > 
struct Node { 
    T _value; 
    std::unique_ptr<Node> _left; 
    std::unique_ptr<Node> _right; 

    Node(const T& val) : _value(val) {} 
}; 

template < typename T > 
class BinTree { 
    std::unique_ptr<Node<T>> _root; 
public: 
    // methods 
};

我觉得这样的设计对树结构好得多。如果你有兴趣，我可以写更多。注意：std :: unique_ptr是在C++ 11中引入的，所以如果你在老版本的标准原始指针中写入，将不得不做（=更多的工作）。

来源

2017-04-11 16:18:22

数组和二叉树的构造函数

回答

相关问题