C++学习——树（一）

文章目录

前言
一、树的模板代码

前言

本文为《C++学习》的第6篇文章，今天学习树。

一、树的模板代码

#include<iostream>
#include<stdexcept>using namespace std;/*------------------------------------------* 链表节点模板类* @tparam T 节点数据类型* @成员 data - 存储数据* @成员 next - 指向下一个节点的指针------------------------------------------*/
template<typename T>
struct ListNode{T data;ListNode *next;ListNode(T d) : data(d), next(NULL) {}  // 初始化构造函数
};/*------------------------------------------* 树节点模板类* @tparam T 节点数据类型* @成员 data - 节点存储的数据* @成员 childrenHead - 子节点链表头指针* @方法 AddChild - 添加子节点------------------------------------------*/
template<typename T>
struct TreeNode{T data;ListNode<TreeNode<T>*> *childrenHead;  // 子节点链表TreeNode(){childrenHead = NULL;  // 初始化空子节点列表}/// 添加子节点到链表头部/// @param node 要添加的子节点指针void AddChild(TreeNode<T> *node){ListNode<TreeNode<T>*> *childNode = new ListNode<TreeNode<T>*> (node);if(childrenHead == NULL){childrenHead = childNode;  // 空链表直接赋值}else{childNode->next = childrenHead;  // 新节点插入链表头部childrenHead = childNode;}}
};/*------------------------------------------* 树结构模板类* @tparam T 节点数据类型* @成员 nodes - 预分配的节点数组* @成员 root - 根节点指针* @成员 maxNodes - 最大节点容量* @方法详见各函数注释------------------------------------------*/
template<typename T>
class Tree{
private:TreeNode<T> *nodes;    // 节点存储数组TreeNode<T> *root;     // 根节点指针int maxNodes;          // 最大节点数public:Tree();                // 默认构造（容量100001）Tree(int maxNodes);    // 指定容量构造~Tree();               // 析构函数/// 获取指定ID的树节点/// @param id 节点ID（数组索引）/// @throw out_of_range 非法ID时抛出异常TreeNode<T> *GetTreeNode(int id);void SetRoot(int rootId);      // 设置根节点void AddChild(int parentId, int sonId);  // 添加父子关系void AssignData(int nodeId, T data);     // 设置节点数据/// 递归打印树结构（前序遍历）/// @param node 当前打印节点，默认从根开始void print(TreeNode<T> *node = NULL);
};/*---------------- 类方法实现 ----------------*/// 默认构造函数（预分配100001节点）
template<typename T>
Tree<T>::Tree() : maxNodes(100001) {nodes = new TreeNode<T>[maxNodes];  // 批量初始化节点
}// 指定容量构造函数
template<typename T>
Tree<T>::Tree(int maxNodes) : maxNodes(maxNodes) {nodes = new TreeNode<T>[maxNodes];
}// 析构函数（释放所有动态内存）
template<typename T>
Tree<T>::~Tree(){// 释放所有子节点链表for(int i = 0; i < maxNodes; ++i){ListNode<TreeNode<T>*> *curr = nodes[i].childrenHead;while(curr){ListNode<TreeNode<T>*> *next = curr->next;delete curr;  // 释放链表节点curr = next;}}delete[] nodes;  // 释放节点数组
}// 获取节点实现（含边界检查）
template<typename T>
TreeNode<T> *Tree<T>::GetTreeNode(int id){if(id < 0 || id >= maxNodes){throw out_of_range("Invalid node ID");} return &nodes[id];  // 返回数组元素地址
}// 设置根节点
template<typename T>
void Tree<T>::SetRoot(int rootId){root = GetTreeNode(rootId);  // 通过ID查找节点
}// 建立父子关系
template<typename T>
void Tree<T>::AddChild(int parentId, int sonId){TreeNode<T> *parentNode = GetTreeNode(parentId);TreeNode<T> *sonNode = GetTreeNode(sonId);parentNode->AddChild(sonNode);  // 调用节点添加方法
}// 设置节点数据
template<typename T>
void Tree<T>::AssignData(int nodeId, T data){GetTreeNode(nodeId)->data = data;  // 直接赋值节点数据域
}// 递归打印实现（深度优先遍历）
template<typename T>
void Tree<T>::print(TreeNode<T> *node){if(node == NULL){node = root;  // 默认从根节点开始遍历}cout << node->data;  // 先输出当前节点// 递归遍历所有子节点ListNode<TreeNode<T>*> *tmp = node->childrenHead;while(tmp){print(tmp->data);  // 深度优先遍历tmp = tmp->next;}
}/*------------------------------------------* 主函数测试模块* 构建测试树结构：*        a*       / \*      b   c*     /   / \*    d   e   f*   /|\*  g h i------------------------------------------*/
int main(){Tree<char> T(9);  // 创建容量为9的树// 设置根节点并分配数据T.SetRoot(0);T.AssignData(0, 'a');T.AssignData(1, 'b');T.AssignData(2, 'c');T.AssignData(3, 'd');T.AssignData(4, 'e');T.AssignData(5, 'f');T.AssignData(6, 'g');T.AssignData(7, 'h');T.AssignData(8, 'i');// 构建树结构关系T.AddChild(0, 2);  // a->cT.AddChild(0, 1);  // a->bT.AddChild(1, 3);  // b->dT.AddChild(2, 5);  // c->fT.AddChild(2, 4);  // c->eT.AddChild(3, 8);  // d->iT.AddChild(3, 7);  // d->hT.AddChild(3, 6);  // d->gT.print();  //前序遍历）return 0;
}