【数据结构与算法】 树

树数据结构里的“家族”和层级管理利器当你第一次接触数据结构老师提到“树”你可能会疑惑“树不是植物吗怎么和程序有关”其实树在程序里非常生活化它的作用是组织信息把复杂的数据关系变得清晰有序。掌握树你就掌握了处理层级结构和递归问题的钥匙。树的概念什么是树树是一种非线性结构与链表、数组不同它没有单一的线性顺序而是分层次组织数据。树有几个关键特点根节点root树的最顶层节点唯一节点node树的元素每个节点可以有若干子节点子节点和父节点节点的上下层关系叶子节点leaf没有子节点的节点无环树中的路径不会回到自己生活中的例子电脑文件夹、公司组织架构、游戏技能树都可以抽象成树。父节点、子节点、兄弟节点树的基本关系树的层次关系类似家族关系父节点上一级节点子节点下一级节点兄弟节点同一级的其他节点例如A / \ B C / \ D EA 是 B 和 C 的父节点D 和 E 是兄弟节点C 是 D 和 E 的父节点把它想成家族树你就很容易理解这些关系。节点的度和树的高度理解树的形态节点的度一个节点有多少子节点树的度整棵树中最大节点度树的高度从根节点到最深叶子节点的层数在上例中A 的度是 2B 的度是 0树的高度是 3理解度和高度有助于分析树的性能和复杂度。树的分类常见树结构树有多种类型每种有不同应用普通树节点子节点数量不限二叉树每个节点最多两个孩子左、右完全二叉树除最后一层外每层节点都满最后一层从左到右排列满二叉树所有叶子在同一层每个非叶子节点有两个孩子二叉搜索树BST左子树 根节点 右子树平衡二叉树高度平衡保证查找效率树与森林森林是多棵互不相交的树树可以看作单棵树的森林理解这些分类可以在算法和实际应用中选择合适的树结构。遍历树访问节点的策略遍历树是操作树的基础核心问题是访问节点顺序前序遍历先访问自己再左子树再右子树中序遍历先左子树再访问自己再右子树后序遍历先左子树再右子树最后访问自己层序遍历按层从上到下从左到右访问节点队列实现例子A / \ B C前序A B C中序B A C后序B C A层序A B C掌握遍历你就能实现很多算法例如计算叶子节点数量、树的深度、路径求和等。树的存储方式代码实现思路树常用链式存储方式用结构体指针表示父子关系。C语言示例typedef struct TreeNode { int data; struct TreeNode* left; struct TreeNode* right; } TreeNode;对于普通多叉树可以用“孩子-兄弟表示法”左指针指向第一个孩子右指针指向下一个兄弟这种表示法可以把任意树转换为二叉树便于算法统一处理。树的应用实际场景举例树的应用几乎无处不在文件系统目录结构HTML / DOM 树游戏技能树数据库索引B树、B树编译器语法树AST网络分层结构、组织架构掌握树你就能理解和操作这些层级结构。树与递归为什么树离不开递归树的自然层级关系非常适合用递归操作遍历树前序、中序、后序求树高、叶子节点数二叉搜索树插入、删除树的深度优先搜索、回溯问题树结构和递归是天然搭档理解递归才能轻松掌握树的算法。总结树是一种从上到下分层、无环、方便组织数据的结构。理解树不是记死定义而是能在生活和编程中识别层级、关系和递归模式。掌握树之后很多复杂算法和数据结构问题都会迎刃而解。