多叉树存储的方式：
采用链表的方式维护子节点，每个结点的child指针指向子节点链表的首节点。通过next指针即可遍历子节点链表。
采用迭代器模式的设计思路，封装了多叉树dfs遍历接口：iterator_node以及bfs遍历接口：iterator_leval_node。
iterator_node的实现思路：
从head节点开始遍历多叉树。通过tree.begin()获取迭代器。重载++运算符，可以通过以下方式遍历多叉树：
for (auto it = tree.begin(); !it.empty(); it++){ //do somthing it->xxx; }
其中重载++运算符调用了iterator_node的私有成员函数next()，next的实现思路如下：
按照以下顺序遍历：
1. 如果child指针不为空，将iterator_node存储的point指针变为this_>child，直接return。
2. 如果next指针不为空，将iterator_node存储的point指针变为this_>next，直接return。
3. child和next都为空时，表明无法继续向下遍历，只能向上回滚，调用next_up函数。
next_up函数的逻辑为：
1. 有兄弟节点则将point设为兄弟节点
2. 没有兄弟节点，如果父节点不为空继续向上查找，调用next_up();
3. 父亲节点和兄弟节点都为空，遍历结束，返回nullptr。
iterator_leval_node的实现思路：
在迭代器内部维护一个队列，每次++操作都将节点的子节点入队，取出队首的节点，当队列为长度为0时，表明遍历结束返回nullptr。
#include <iostream> #include <vector> #include <queue> using namespace std; class Data { public: int num; Data(int mnum) : num(mnum) {} }; // 定义节点 template <typename T> class Node { public: T* data; Node* parent; Node* child; Node* next; Node(T* mdata) : data(mdata), parent(nullptr), next(nullptr), child(nullptr) {} }; template <typename T> class iterator_node { protected: Node<T>* point; private: // 向上遍历获取下一个迭代器 iterator_node<T> next_up() const { // 有兄弟节点返回兄弟节点 if (point->next != nullptr) { return iterator_node<T>(point->next); } // 没有兄弟节点继续向上查找 if (point->parent != nullptr) { return iterator_node<T>(point->parent).next_up(); } // 父亲节点为空返回空 return iterator_node<T>(nullptr); } // 获取下一个迭代器 iterator_node<T> next() const { // 有子节点返回子节点 if (point->child != nullptr) { return iterator_node<T>(point->child); } // 有兄弟节点返回兄弟节点 if (point->next != nullptr) { return iterator_node<T>(point->next); } // 没有子节点和兄弟节点执行next_up向上查找 if (point->parent != nullptr) { return iterator_node<T>(point->parent).next_up(); } } // 获取data T* get_date() const { return point == nullptr ? nullptr : point->data; } public: iterator_node() : point(nullptr) {} iterator_node(Node<T>* n) : point(n) {} // 是否为空 bool empty() const { return point == nullptr; } // 获取父节点 iterator_node<T> father() const { return iterator_node<T>(point->parent); } // 获取子节点列表 vector<iterator_node<T>> children() const { vector<iterator_node<T>> res; Node<T>* p = point->child; while (p != nullptr) { res.push_back(iterator_node<T>(p)); p = p->next; } return res; } // 获取兄弟节点列表 vector<iterator_node<T>> brothers() const { return father().children(); } // 重载*运算符 T operator*() const { if (point == nullptr) throw "get iterator's data without init"; return point->data; } // 重载++运算符 iterator_node<T> operator++() { if (point == nullptr) throw "get iterator's point without init"; auto tmp = point; point = this->next().point; return iterator_node<T>(tmp); } iterator_node<T>& operator++(int) { if (point == nullptr) throw "get iterator's point without init"; point = this->next().point; return *this; } // 重载->运算符 T* operator->() const { return get_date(); } template <class T> friend class PolyTree; }; template <typename T> class iterstor_leval_node : public iterator_node<T> { private: queue<Node<T>*> tmp_queue; bool push_child_in_queue() { if (iterator_node<T>::point == nullptr) return false; if (iterator_node<T>::point->child != nullptr) { auto tmp = iterator_node<T>::point->child; while (tmp != nullptr) { tmp_queue.push(tmp); tmp = tmp->next; } return true; } return false; } void get_next() { if (iterator_node<T>::point == nullptr) throw "get iterator's point without init"; if (iterator_node<T>::point->child != nullptr) { push_child_in_queue(); iterator_node<T>::point = tmp_queue.front(); tmp_queue.pop(); } else if (tmp_queue.empty()){ iterator_node<T>::point = nullptr; } else { iterator_node<T>::point = tmp_queue.front(); tmp_queue.pop(); } } public: // 构造函数 iterstor_leval_node<T>(Node<T> * n) //: iterator_node::point(n) { //iterator_node<T>::iterator_node(n); iterator_node<T>::point = n; //cout << "iterstor_leval_node<T>(Node<T> * n) " << n << endl; } iterstor_leval_node<T>(iterstor_leval_node<T> * tmp) : iterator_node<T>::point(tmp->point), tmp_queue(tmp->tmp_queue) {} // 重载++运算符 iterstor_leval_node<T> operator++() { auto tmp = *this; get_next(); return tmp; } iterstor_leval_node<T>& operator++(int) { get_next(); return *this; } template <class T> friend class PolyTree; }; template <typename T> class PolyTree { private: Node<T>* head; public: PolyTree() : head(nullptr) {} iterator_node<T> begin() { return iterator_node<T>(head); } iterstor_leval_node<T> leval_begin() { return iterstor_leval_node<T>(head); } // 插入节点 void add(iterator_node<T> parent, T* t) { if (parent.empty()) { throw "iterator is empty."; } if (parent.children().size() == 0) { parent.point->child = new Node<T>(t); parent.point->child->parent = parent.point; } else { Node<T>* p = parent.point->child; while (p->next != nullptr) { p = p->next; } p->next = new Node<T>(t); p->next->parent = parent.point; } } // 添加根节点 void add(T* t) { if (head == nullptr) { head = new Node<T>(t); } } //移除节点 void earse(iterator_node<T> it) { auto p = it.point; if (this->head == p) { this->head = nullptr; } if (p->parent->child == p) { p->parent->child = p->next; } else { auto p1 = p->parent->child; while (p1->next != p) { p1 = p1->next; } p1->next = p->next; } } }; int main() { PolyTree<Data> tree; tree.add(new Data(1)); tree.add(tree.begin(), new Data(2)); tree.add(tree.begin(), new Data(3)); tree.add(tree.begin(), new Data(4)); tree.add(++tree.begin(), new Data(5)); tree.add(tree.begin().children()[0], new Data(6)); tree.earse(tree.begin().children()[0]); cout << "dfs:" << endl; for (auto it = tree.begin(); !it.empty(); it++) { cout << it->num << " father: " << (it.father().empty() ? 0 : it.father()->num) << endl; } cout << "bfs:" << endl; for (auto it = tree.leval_begin(); !it.empty(); it++) { cout << it->num << "father: " << (it.father().empty() ? 0 : it.father()->num) << endl; } int x; cin >> x; return 0; }