数据结构--树

一、树的概念

树是由n(n≥0)个节点组成的有限集合，它满足以下条件：
 
1. 当n=0时，称为空树
2. 当n>0时，有且仅有一个特定的节点称为根节点(root)
3. 其余节点可分为m(m≥0)个互不相交的有限集合，每个集合本身又是一棵树，称为根的子树(subtree)
 
二、基本术语
 
- 节点(Node): 树的基本单位，包含数据项和指向其他节点的指针
- 边(Edge): 连接两个节点的线
- 根节点(Root): 树的最顶层节点，没有父节点
- 父节点(Parent): 一个节点的直接上层节点
- 子节点(Child): 一个节点的直接下层节点
- 叶子节点(Leaf): 没有子节点的节点
- 内部节点(Internal Node): 至少有一个子节点的节点
- 度(Degree): 一个节点拥有的子节点数目
- 树的度: 树中所有节点度的最大值
- 层次(Level): 根节点为第1层，其子节点为第2层，以此类推
- 高度/深度(Height/Depth): 树中节点的最大层次数
- 兄弟节点(Sibling): 具有相同父节点的节点
- 祖先节点(Ancestor): 从根到该节点路径上的所有节点
- 后代节点(Descendant): 某节点子树中的所有节点
 
三、树的分类
 
1. 二叉树(Binary Tree): 每个节点最多有两个子节点
- 满二叉树
- 完全二叉树
- 二叉搜索树(BST)
- 平衡二叉树(AVL树)
- 红黑树
2. 多叉树: 每个节点可以有多个子节点
- B树
- B+树
- Trie树(字典树)
3. 其他特殊树结构
- 堆(Heap)
- 哈夫曼树
- 线段树
- 树状数组
 
四、树的存储表示
 
1. 链式存储
- 每个节点包含数据域和指针域
- 指针指向子节点
2. 顺序存储
- 使用数组存储
- 对于完全二叉树特别有效
 3.树的简单实现

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;// 定义树节点类模板
template <typename T>
class TreeNode
{
public:T data;  // 节点存储的数据TreeNode* firstChild;  // 指向该节点的第一个孩子节点TreeNode* nextSibling; // 指向该节点的下一个兄弟节点// 构造函数，初始化节点数据，将孩子和兄弟指针置为空TreeNode(T val) : data(val), firstChild(nullptr), nextSibling(nullptr) {}
};// 定义树类模板
template <typename T>
class Tree
{
private:TreeNode<T>* root;  // 树的根节点// 递归清空树的辅助函数void clear(TreeNode<T>* node){if (node == nullptr) return;  // 如果节点为空，直接返回clear(node->firstChild);  // 递归清空当前节点的第一个孩子节点及其子树clear(node->nextSibling); // 递归清空当前节点的下一个兄弟节点及其子树delete node;  // 释放当前节点的内存}public:// 构造函数，初始化根节点为空Tree() : root(nullptr) {}// 析构函数，调用 clear 函数清空整棵树~Tree() { clear(root); }// 创建一个新的树节点，返回新节点的指针TreeNode<T>* createNode(T data){return new TreeNode<T>(data);}// 设置树的根节点void setRoot(TreeNode<T>* node){root = node;}// 获取树的根节点TreeNode<T>* getRoot() const{return root;}// 向指定父节点插入一个孩子节点void insertChild(TreeNode<T>* parent, TreeNode<T>* child){if (parent == nullptr) return;  // 如果父节点为空，直接返回if (parent->firstChild == nullptr){// 如果父节点没有第一个孩子节点，将该孩子节点设为第一个孩子parent->firstChild = child;}else{// 否则，找到父节点孩子链表的末尾，将该孩子节点插入到末尾TreeNode<T>* sibling = parent->firstChild;while (sibling->nextSibling != nullptr){sibling = sibling->nextSibling;}sibling->nextSibling = child;}}// 前序遍历树void preOrderTraversal(TreeNode<T>* node){if (node == nullptr) return;  // 如果节点为空，直接返回cout << node->data << " ";  // 访问当前节点的数据preOrderTraversal(node->firstChild);  // 递归前序遍历当前节点的第一个孩子节点及其子树preOrderTraversal(node->nextSibling); // 递归前序遍历当前节点的下一个兄弟节点及其子树}// 后序遍历树void postOrderTraversal(TreeNode<T>* node){if (node == nullptr) return;  // 如果节点为空，直接返回postOrderTraversal(node->firstChild);  // 递归后序遍历当前节点的第一个孩子节点及其子树cout << node->data << " ";  // 访问当前节点的数据postOrderTraversal(node->nextSibling); // 递归后序遍历当前节点的下一个兄弟节点及其子树}// 层序遍历树void levelOrderTraversal(){if (root == nullptr) return;  // 如果根节点为空，直接返回queue<TreeNode<T>*> q;  // 定义一个队列用于层序遍历q.push(root);  // 将根节点入队while (!q.empty()){TreeNode<T>* current = q.front();  // 获取队首节点q.pop();  // 队首节点出队cout << current->data << " ";  // 访问当前节点的数据// 将当前节点的所有孩子节点依次入队TreeNode<T>* child = current->firstChild;while (child != nullptr){q.push(child);child = child->nextSibling;}}}// 获取树的高度int getHeight(TreeNode<T>* node){if (node == nullptr) return 0;  // 如果节点为空，高度为 0int maxHeight = 0;  // 初始化最大子树高度为 0TreeNode<T>* child = node->firstChild;while (child != nullptr){// 递归计算每个子树的高度，并更新最大子树高度maxHeight = max(maxHeight, getHeight(child));child = child->nextSibling;}return maxHeight + 1;  // 当前节点的高度为最大子树高度加 1}// 计算树中节点的总数int countNodes(TreeNode<T>* node){if (node == nullptr) return 0;  // 如果节点为空，节点数为 0// 当前节点及其子树的节点总数为当前节点加上其第一个孩子节点及其子树的节点数，再加上其兄弟节点及其子树的节点数return 1 + countNodes(node->firstChild) + countNodes(node->nextSibling);}// 在树中查找值为 value 的节点TreeNode<T>* findNode(TreeNode<T>* node, T value){if (node == nullptr) return nullptr;  // 如果节点为空，返回空指针if (node->data == value) return node;  // 如果当前节点的值等于要查找的值，返回当前节点的指针// 先在当前节点的第一个孩子节点及其子树中查找TreeNode<T>* found = findNode(node->firstChild, value);if (found != nullptr) return found;// 若未找到，再在当前节点的下一个兄弟节点及其子树中查找return findNode(node->nextSibling, value);}// 打印树的结构，level 表示当前节点的层级void printTree(TreeNode<T>* node, int level = 0){if (node == nullptr) return;  // 如果节点为空，直接返回// 根据当前节点的层级打印相应数量的空格for (int i = 0; i < level; ++i){cout << "  ";}cout << node->data << endl;  // 打印当前节点的数据// 递归打印当前节点的第一个孩子节点及其子树，层级加 1printTree(node->firstChild, level + 1);// 递归打印当前节点的下一个兄弟节点及其子树，层级不变printTree(node->nextSibling, level);}
};int main()
{Tree<char> tree;  // 创建一个存储字符类型数据的树对象// 创建树的各个节点TreeNode<char>* A = tree.createNode('A');TreeNode<char>* B = tree.createNode('B');TreeNode<char>* C = tree.createNode('C');TreeNode<char>* D = tree.createNode('D');TreeNode<char>* E = tree.createNode('E');TreeNode<char>* F = tree.createNode('F');TreeNode<char>* G = tree.createNode('G');// 构建树的结构tree.setRoot(A);  // 设置 A 为根节点tree.insertChild(A, B);  // 将 B 插入为 A 的孩子节点tree.insertChild(A, C);  // 将 C 插入为 A 的孩子节点tree.insertChild(A, D);  // 将 D 插入为 A 的孩子节点tree.insertChild(B, E);  // 将 E 插入为 B 的孩子节点tree.insertChild(B, F);  // 将 F 插入为 B 的孩子节点tree.insertChild(D, G);  // 将 G 插入为 D 的孩子节点// 打印树的结构cout << "Tree structure:" << endl;tree.printTree(tree.getRoot());cout << endl;// 进行各种遍历测试cout << "Pre-order traversal: ";tree.preOrderTraversal(tree.getRoot());cout << endl;cout << "Post-order traversal: ";tree.postOrderTraversal(tree.getRoot());cout << endl;cout << "Level-order traversal: ";tree.levelOrderTraversal();cout << endl;// 测试其他功能cout << "Tree height: " << tree.getHeight(tree.getRoot()) << endl;cout << "Total nodes: " << tree.countNodes(tree.getRoot()) << endl;// 测试查找节点功能char searchValue = 'F';TreeNode<char>* found = tree.findNode(tree.getRoot(), searchValue);if (found){cout << "Found node: " << found->data << endl;}else{cout << "Node " << searchValue << " not found" << endl;}return 0;
}

五、树的应用
 
- 文件系统目录结构
- 数据库索引
- 网络路由算法
- 决策树(机器学习)
- XML/HTML文档对象模型(DOM)
- 组织结构图
- 游戏中的场景图
 
树结构因其高效的查找、插入和删除操作(O(log n)时间复杂度)而被广泛应用于各种算法和系统中。