一、树的概念
树是由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; // 如果节点为空，高度为 0
int maxHeight = 0; // 初始化最大子树高度为 0
TreeNode<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; // 打印当前节点的数据
// 递归打印当前节点的第一个孩子节点及其子树，层级加 1
printTree(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)时间复杂度)而被广泛应用于各种算法和系统中。