m-ary树结构的遍历方法
Traversal method for a m-ary Tree structure
我有一个 Node class 和一个 Tree class (带模板),我想为我的树 class 写一个 遍历方法 打印出我的结构中的每个节点。但我只得到根的 children,之后没有任何打印。
这是我的代码。它有点太长了,但有问题的方法名为 traverse() 并且它位于 main 函数之前。
#include <iostream>
#include <cstddef>
#define N 5
template <typename V>
class Node {
private:
V _data;
unsigned short _size;
Node<V>* _children;
template <typename U>
friend std::ostream& operator<< (std::ostream&, const Node<U>&);
public:
Node();
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();
V getData() const;
unsigned short getSize() const;
Node<V>* getChildren();
void setChild(unsigned short, Node<V>);
};
template <typename V>
Node<V>::Node()
: _data(0), _size(0), _children(nullptr) {}
template <typename V>
Node<V>::Node(V data, unsigned short size)
: _data(data), _size(size), _children(new Node<V>[_size]) {
}
template <typename V>
Node<V>::Node (const Node& other)
: _size(other._size), _data(other._data) {
_children = new Node<V>[_size];
for (unsigned short i = 0; i < _size; i++)
_children[i] = other._children[i];
}
template <typename V>
Node<V>& Node<V>::operator= (Node& n){
if (&n != this) {
delete[] _children;
_data = n._data; _children = n._children; _size = n._size;
n._data = 0; n._size = 0; n._children = nullptr;
}
return *this;
}
template <typename V>
Node<V>::Node (Node&& n){
_data = n._data; _size = n._size; _children = n._children;
n._data = 0; n._size = 0; n._children = nullptr;
}
template <typename V>
Node<V>& Node<V>::operator= (Node&& n){
if (&n != this) {
delete[] _children;
_data = n._data; _children = n._children; _size = n._size;
n._data = 0; n._size = 0; n._children = nullptr;
}
return *this;
}
template <typename V>
Node<V>::~Node() { delete[] _children; }
template <typename V> // TO DO : move this to class scope ???
V Node<V>::getData() const {return _data;}
template <typename V>
unsigned short Node<V>::getSize() const {return _size;}
template <typename V>
Node<V>* Node<V>::getChildren() {return _children;}
template <typename V>
void Node<V>::setChild(unsigned short index, Node<V> childNode){
this->_children[index] = childNode;
}
template <typename V>
std::ostream& operator<< (std::ostream& o, const Node<V>& node){
if (node._data) o << node._data ;
return o;
}
template <typename V>
class Tree {
private:
Node<V>* _info;
public:
Tree();
Tree(Node<V>*);
Tree(V, unsigned short);
~Tree() = default;
Node<V>* info();
void traverse();
void traverse_process(Node<V>*, unsigned short);
};
template <typename V>
Tree<V>::Tree()
: _info(nullptr) {}
template <typename V>
Tree<V>::Tree(Node<V>* newNode)
: _info(newNode) {}
template <typename V>
Tree<V>::Tree(V data, unsigned short size) {
Node<V>* node = new Node<V>(data, size);
_info = node;
}
template <typename V>
Node<V>* Tree<V>::info() { return _info;}
template <typename V>
void Tree<V>::traverse() {
traverse_process(this->_info, _info->getSize());
}
template <typename V>
void Tree<V>::traverse_process(Node<V>* node, unsigned short size) {
if (node){
for (unsigned short i = 0; i < size; i++) {
if (node->getChildren()[i].getData()){
std::cout << node->getChildren()[i] << std::endl;
traverse_process(node->getChildren()[i], size);
}
}
}
}
int main(int argc, char const *argv[]) {
Node<char> n1('A', N); // root
Node<char> n1_1('B',N); // child of n1
Node<char> n1_2('C', N); // child of n1
Node<char> n1_3('D', N); // child of n1
Node<char> n1_4('E', N); // child of n1
Node<char> n1_1_1('F', N); // child of n1_1
Node<char> n1_1_2('G', N); // child of n1_1
Node<char> n1_1_3('H', N); // child of n1_1
Node<char> n1_2_1('I', N); // child of n1_2
Node<char> n1_2_2('J', N); // child of n1_2
Node<char> n1_1_1_1('K', N); // child of n1_1_1
n1.setChild(0,n1_1);
n1.setChild(1,n1_2);
n1.setChild(2,n1_3);
n1.setChild(4,n1_4);
n1_1.setChild(1, n1_1_1);
n1_1.setChild(2, n1_1_2);
n1_1.setChild(3, n1_1_3);
n1_2.setChild(2, n1_2_1);
n1_2.setChild(4, n1_2_2);
n1_1_1.setChild(0, n1_1_1_1);
Tree<char> t(&n1);
t.traverse();
return 0;
}
提前感谢您的帮助
您的节点有两个副本:
- 您在此处的堆栈上分配它们:
Node<char> n1('A', N);
- 他们在这里制作自己的 children:
_children = new Node<V>[_size];
当您调用 setChild() 时,它会执行以下操作:
this->_children[index] = childNode
复制整个节点,从你的栈上的节点到节点拥有的节点
因此,当您将孙子添加到堆栈中的那个时,traverse_process
不会看到任何东西,因为它使用了不同的副本。这就是为什么第一层遍历有效,但更深层次的遍历无效的原因。
要修复它,您需要为 Node-owned children 添加访问器,然后在 那里 调用 setChild。或者,您需要更改 _children 的工作方式,以便从 stack-allocated 节点向它提供指针。
我有一个 Node class 和一个 Tree class (带模板),我想为我的树 class 写一个 遍历方法 打印出我的结构中的每个节点。但我只得到根的 children,之后没有任何打印。
这是我的代码。它有点太长了,但有问题的方法名为 traverse() 并且它位于 main 函数之前。
#include <iostream>
#include <cstddef>
#define N 5
template <typename V>
class Node {
private:
V _data;
unsigned short _size;
Node<V>* _children;
template <typename U>
friend std::ostream& operator<< (std::ostream&, const Node<U>&);
public:
Node();
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();
V getData() const;
unsigned short getSize() const;
Node<V>* getChildren();
void setChild(unsigned short, Node<V>);
};
template <typename V>
Node<V>::Node()
: _data(0), _size(0), _children(nullptr) {}
template <typename V>
Node<V>::Node(V data, unsigned short size)
: _data(data), _size(size), _children(new Node<V>[_size]) {
}
template <typename V>
Node<V>::Node (const Node& other)
: _size(other._size), _data(other._data) {
_children = new Node<V>[_size];
for (unsigned short i = 0; i < _size; i++)
_children[i] = other._children[i];
}
template <typename V>
Node<V>& Node<V>::operator= (Node& n){
if (&n != this) {
delete[] _children;
_data = n._data; _children = n._children; _size = n._size;
n._data = 0; n._size = 0; n._children = nullptr;
}
return *this;
}
template <typename V>
Node<V>::Node (Node&& n){
_data = n._data; _size = n._size; _children = n._children;
n._data = 0; n._size = 0; n._children = nullptr;
}
template <typename V>
Node<V>& Node<V>::operator= (Node&& n){
if (&n != this) {
delete[] _children;
_data = n._data; _children = n._children; _size = n._size;
n._data = 0; n._size = 0; n._children = nullptr;
}
return *this;
}
template <typename V>
Node<V>::~Node() { delete[] _children; }
template <typename V> // TO DO : move this to class scope ???
V Node<V>::getData() const {return _data;}
template <typename V>
unsigned short Node<V>::getSize() const {return _size;}
template <typename V>
Node<V>* Node<V>::getChildren() {return _children;}
template <typename V>
void Node<V>::setChild(unsigned short index, Node<V> childNode){
this->_children[index] = childNode;
}
template <typename V>
std::ostream& operator<< (std::ostream& o, const Node<V>& node){
if (node._data) o << node._data ;
return o;
}
template <typename V>
class Tree {
private:
Node<V>* _info;
public:
Tree();
Tree(Node<V>*);
Tree(V, unsigned short);
~Tree() = default;
Node<V>* info();
void traverse();
void traverse_process(Node<V>*, unsigned short);
};
template <typename V>
Tree<V>::Tree()
: _info(nullptr) {}
template <typename V>
Tree<V>::Tree(Node<V>* newNode)
: _info(newNode) {}
template <typename V>
Tree<V>::Tree(V data, unsigned short size) {
Node<V>* node = new Node<V>(data, size);
_info = node;
}
template <typename V>
Node<V>* Tree<V>::info() { return _info;}
template <typename V>
void Tree<V>::traverse() {
traverse_process(this->_info, _info->getSize());
}
template <typename V>
void Tree<V>::traverse_process(Node<V>* node, unsigned short size) {
if (node){
for (unsigned short i = 0; i < size; i++) {
if (node->getChildren()[i].getData()){
std::cout << node->getChildren()[i] << std::endl;
traverse_process(node->getChildren()[i], size);
}
}
}
}
int main(int argc, char const *argv[]) {
Node<char> n1('A', N); // root
Node<char> n1_1('B',N); // child of n1
Node<char> n1_2('C', N); // child of n1
Node<char> n1_3('D', N); // child of n1
Node<char> n1_4('E', N); // child of n1
Node<char> n1_1_1('F', N); // child of n1_1
Node<char> n1_1_2('G', N); // child of n1_1
Node<char> n1_1_3('H', N); // child of n1_1
Node<char> n1_2_1('I', N); // child of n1_2
Node<char> n1_2_2('J', N); // child of n1_2
Node<char> n1_1_1_1('K', N); // child of n1_1_1
n1.setChild(0,n1_1);
n1.setChild(1,n1_2);
n1.setChild(2,n1_3);
n1.setChild(4,n1_4);
n1_1.setChild(1, n1_1_1);
n1_1.setChild(2, n1_1_2);
n1_1.setChild(3, n1_1_3);
n1_2.setChild(2, n1_2_1);
n1_2.setChild(4, n1_2_2);
n1_1_1.setChild(0, n1_1_1_1);
Tree<char> t(&n1);
t.traverse();
return 0;
}
提前感谢您的帮助
您的节点有两个副本:
- 您在此处的堆栈上分配它们:
Node<char> n1('A', N);
- 他们在这里制作自己的 children:
_children = new Node<V>[_size];
当您调用 setChild() 时,它会执行以下操作:
this->_children[index] = childNode
复制整个节点,从你的栈上的节点到节点拥有的节点
因此,当您将孙子添加到堆栈中的那个时,traverse_process
不会看到任何东西,因为它使用了不同的副本。这就是为什么第一层遍历有效,但更深层次的遍历无效的原因。
要修复它,您需要为 Node-owned children 添加访问器,然后在 那里 调用 setChild。或者,您需要更改 _children 的工作方式,以便从 stack-allocated 节点向它提供指针。