模板类和遍历的默认构造函数

问题描述 投票：0回答：1

我有一个Node类和一个Tree类，并且在我的Tree类（这是一棵三叉树）中，我有一个方法可以对我的树进行有序遍历。因此，问题在于，当我调用此方法时，我能够打印树的第一个分支，然后出现分段错误。我知道（通过调试）错误可能来自Node类的构造函数中的某些地方，或者我可能没有编写非常好的遍历方法。这是我的代码。

Node.hpp

#ifndef NODE_HPP
#define NODE_HPP

#include <iostream>
#include <cstddef> 

template <typename V, unsigned short N>
class Node {
private:
  V _data;
  Node<V, N>* _children[N];

  template <typename U, unsigned short M>
  friend std::ostream& operator<< (std::ostream&, const Node<U, M>&);

public:
  Node();
  Node(V);
  Node(V, unsigned short);
  Node(const Node&); // copy constructor
  Node& operator= (Node&); // assignement by copy constructor
  Node (Node&&); // transfer constructor
  Node& operator= (Node&&); // assignement by transfer constructor
  ~Node() = default;
  V getData() const;
  Node<V, N>* getChildren();
  void setChild(unsigned short, Node<V, N>*);
  void delChild(unsigned short);
  Node<V, N>* getChild(unsigned short); 
};

template <typename V, unsigned short N>
Node<V, N>::Node()
  : _data(0),  _children(nullptr) {}

template <typename V, unsigned short N>
Node<V, N>::Node(V data)
  : _data(data) {
  for (unsigned short i = 0; i < N; i++) 
    _children[i] = NULL;
}

template <typename V, unsigned short N>
Node<V, N>::Node(V data, unsigned short size)
  : _data(data) {
  for (unsigned short i = 0; i < size; i++) 
    _children[i] = NULL;
}

template <typename V, unsigned short N>
Node<V, N>::Node (const Node& other)
  : _data(other._data) {
  // _children = other._children;
  for (unsigned short i = 0; i < N; i++) 
    _children[i] = other._children[i];
}

template <typename V, unsigned short N>
Node<V, N>& Node<V, N>::operator= (Node& n){
  if (&n != this) {
    delete _children;
    _data = n._data; _children = n._children;
    n._data = 0; n._children = nullptr;
  }
  return *this;
}

template <typename V, unsigned short N>
Node<V, N>::Node (Node&& n){
  _data = n._data; _children = n._children;
  n._data = 0; n._children = nullptr;
}

template <typename V, unsigned short N>
Node<V, N>& Node<V, N>::operator= (Node&& n){
  if (&n != this) {
    delete _children;
    _data = n._data; _children = n._children;
    n._data = 0; n._children = nullptr;
  }
  return *this; 
}

template <typename V, unsigned short N> // TO DO : move this to class scope ???
V Node<V, N>::getData() const {return _data;}

template <typename V, unsigned short N>
Node<V, N>* Node<V, N>::getChildren() {return *_children;}

template <typename V, unsigned short N>
void Node<V, N>::setChild(unsigned short index, Node<V, N>* childNode){
  this->_children[index] = childNode;
}

template <typename V, unsigned short N>
void Node<V, N>::delChild(unsigned short index){
  this->_children[index] = NULL;
}

template <typename V, unsigned short N>
Node<V, N>* Node<V, N>::getChild(unsigned short index){
  return &this->_children[index];
}

template <typename V, unsigned short N>
std::ostream& operator<< (std::ostream& o, const Node<V, N>& node){
  if (node._data) o << node._data ;
  return o;
}

#endif

tree.hpp


#ifndef TREE_HPP
#define TREE_HPP

#include <iostream>
#include <cstddef> 
#include "node.hpp"

template <typename V, unsigned short N>
class Tree {
private:
  Node<V, N>* _info;
public:
  Tree();
  Tree(Node<V, N>*);
  Tree(V, unsigned short);
  Tree(const Tree&) = delete;  // copy constructor
  Tree& operator= (const Tree&) = delete; // assignement by copy constructor
  Tree (Tree&&); // transfer constructor
  Tree& operator= (Tree&&); // assignement by transfer constructor
  ~Tree() {delete _info;}
  Node<V, N>* info();
  bool vide();
  bool ins(unsigned short, Node<V, N>*);
  bool del(unsigned short);
  Node<V, N>* fils(unsigned short);
  void inorderTraverse(Node<V, N>*);
};

template <typename V, unsigned short N>
Tree<V, N>::Tree() 
  : _info(nullptr) {}

template <typename V, unsigned short N>
Tree<V, N>::Tree(Node<V, N>* newNode)
  : _info(newNode) {}

template <typename V, unsigned short N>
Tree<V, N>::Tree(V data, unsigned short size) {
  Node<V, N>* node = new Node<V, N>(data, size);
  _info = node;
}

template <typename V, unsigned short N>
Tree<V, N>::Tree(Tree&& t) {
  _info = t._info;
  t._info = nullptr;
}

template <typename V, unsigned short N>
Tree<V, N>& Tree<V, N>::operator= (Tree&& t) {
  if (&t != this) {delete _info; _info = t._info; t._info = nullptr;}
  return *this;
}

template <typename V, unsigned short N>
Node<V, N>* Tree<V, N>::info() { return _info;}

template <typename V, unsigned short N>
bool Tree<V, N>::vide() {
  return true ? _info : false;
}

template <typename V, unsigned short N>
bool Tree<V, N>::ins(unsigned short index, Node<V, N>* node){
  if (_info) {
    _info->setChild(index, node);
    return true;
  }
  return false;
}

template <typename V, unsigned short N>
bool Tree<V, N>::del(unsigned short index){
  if (_info) {
    _info->delChild(index);
    return true;
  }
  return false;
}

template <typename V, unsigned short N>
Node<V, N>* Tree<V, N>::fils(unsigned short index){
  return &_info->getChild(index);
}

template <typename V, unsigned short N>
void Tree<V, N>::inorderTraverse(Node<V, N>* node){
  if (node->getData()){
    std::cout << *node << "\n";
    for (unsigned short i = 0; i < N; i++) {
      if (node->getChildren()[i].getData()){
        inorderTraverse(&node->getChildren()[i]);
      }
    }
  }
}

#endif

main.cpp

#include <iostream>
#include <cstddef>
#include "tree.hpp"
#include "node.hpp"
#define SIZE 5
int main() {
  Node<char, SIZE> n1('A',SIZE);
  Node<char, SIZE> n1_1('B',SIZE);
  Node<char, SIZE> n1_2('C',SIZE);
  Node<char, SIZE> n1_3('D',SIZE);
  Node<char, SIZE> n1_1_1('E',SIZE);
  Node<char, SIZE> n1_1_2('F',SIZE);
  Node<char, SIZE> n1_1_1_1('G',SIZE);
  Node<char, SIZE> n1_2_1('H',SIZE);
  Node<char, SIZE> n1_2_1_1('I',SIZE);
  Node<char, SIZE> n1_3_1('J',SIZE);
  n1.setChild(0,&n1_1);
  n1.setChild(1,&n1_2);
  n1.setChild(2,&n1_3);
  n1_1.setChild(0,&n1_1_1);
  n1_1.setChild(1,&n1_1_2);
  n1_1_1.setChild(0,&n1_1_1_1);
  n1_2.setChild(0,&n1_2_1);
  n1_2_1.setChild(0,&n1_2_1_1);
  n1_3.setChild(0,&n1_3_1);
  Tree<char, SIZE> t(&n1);
  t.inorderTraverse(t.info());
  return 0;
}

谢谢您的帮助

c++ templates constructor tree
1个回答
0
投票

Node::getChildren()返回*_children，它是_children数组中的第一个指针。然后，您调用node->getChildren()[i]，它将i添加到此指针。当您将所有节点在堆栈上彼此并排放置时，这恰好适用于第一个节点，因此它返回正确的节点。这是未定义的行为，在带有堆分配节点的实际代码中，这将很快崩溃。 getChildren应为：

template <typename V, unsigned short N>
Node<V, N>** Node<V, N>::getChildren() { return _children; }

然后您的呼叫代码为：

if (node->getChildren()[i]->getData()) {
   inorderTraverse(node->getChildren()[i]);
}

然后，我们由于取消引用空指针而回到了崩溃的原始原因。这里的简单解决方法是只检查子项是否不为null：

auto children = node->getChildren();
if (children[i] && children[i]->getData()) {
   inorderTraverse(children[i]);
}

您的代码现在将由于Tree析构函数删除堆栈分配的节点而在退出时崩溃：

~Tree() { delete _info; }

如果要使用delete，则需要使用new而不是在main中分配堆栈的方式来创建所有节点。甚至最好使用std::unique_ptr或std::shared_ptr，并完全避免使用delete。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.