该树以左孩子或兄弟表示法存储。
#ifndef _ROOTED_TREE_H_#define _ROOTED_TREE_H_/*****************************************************************算法导论：10.4-4对一个含n个结点的随意有根树，写出一个O(n)时间的过程，输出其全部keyword。
该树以左孩子或兄弟表示法存储。 ******************************************************************/ #include <iostream> template <class T> class RootedTree { public: class Node{ public: friend class RootedTree < T > ; Node *getLeftChild()const { return _leftChild; } Node *getRightSibiling()const{ return _rightSibiling; } T value; private: Node() :_parent(nullptr), _leftChild(nullptr), _rightSibiling(nullptr){} Node(const T& v) :_parent(nullptr), _leftChild(nullptr), _rightSibiling(nullptr), value(v){} Node* _parent; // 指向本结点的父结点 Node* _leftChild; // 指向本结点的第一个子结点，假设没有子结点，则为 null Node* _rightSibiling; // 指向本结点的下一个兄弟结点。假设之后没有兄弟结点，则为 null }; RootedTree() :_root(nullptr){ } RootedTree(const T& v){ _root = new Node(v); } ~RootedTree(); // 向指定的根结点中添加子结点，返回第一个子结点的指针。 Node* addChilds(Node*, const T*, size_t); inline Node* getRoot() const { return _root; } void print() const; private: // 二叉树的根结点 Node* _root; void freeNodes(const Node* root); void print(const Node*) const; }; template <class T> RootedTree<T>::~RootedTree(){ // 释放全部结点所占空间 if (_root) freeNodes(_root); } template <class T> void RootedTree<T>::freeNodes(const Node* root){ // 释放左孩子结点 if (root->_leftChild) freeNodes(root->_leftChild); // 释放右兄弟结点 if (root->_rightSibiling) freeNodes(root->_rightSibiling); // 释放本结点 delete root; } template <class T> typename RootedTree<T>::Node* RootedTree<T>::addChilds(Node* root, const T* elements, size_t size){ if (size > 0){ // 创建根结点的第一个子结点 auto firstNode = new Node(elements[0]); firstNode->_parent = root; root->_leftChild = firstNode; Node* node = nullptr; for (size_t i = size - 1; i > 0; --i){ auto sibiling = new Node(elements[i]); sibiling->_parent = root; sibiling->_rightSibiling = node; node = sibiling; } firstNode->_rightSibiling = node; return firstNode; } return nullptr; } template <class T> void RootedTree<T>::print() const{ if (_root) { print(_root); } } template <class T> void RootedTree<T>::print(const Node* root) const{ if (root){ 输出它的父结点 //if (root->_parent) // std::cout << " [" << root->_parent->value << "] "; std::cout << root->value << " "; // 打印它之后的兄弟 print(root->_rightSibiling); // 打印第一个子结点 print(root->_leftChild); } } #endif
測试例程：using namespace std;int main(){ int ia1[] = { 10, 20, 30, 40, 50, 60 }; int ia2[] = {300, 310, 320}; int ia3[] = {3000, 3100, 3200}; int ia4[] = { 200, 210, 230, 240 }; RootedTree tree(0); auto child1 = tree.addChilds(tree.getRoot(), ia1, 6); auto child2 = tree.addChilds(child1->getRightSibiling()->getRightSibiling(), ia2, 3); auto child3 = tree.addChilds(child2, ia3, 3); tree.addChilds(child1->getRightSibiling(), ia4, 4); tree.print();}