4.1 什么是树

文章目录一、树的概念二、树的性质三 、节点个数4.1 什么是树树的定义树的基本术语树的特点树的表示方法1. 图形表示法2. 嵌套集合表示法3. 凹入表示法缩进表示法4. 广义表表示法树的应用场景树的分类示例简单的树结构一、树的概念树 有层次关系NN0个节点的有限集合空树N0非空树有且仅有一个节点节点根节点、分支节点、叶子节点前驱父节点、后继子节点子树除根外可以分为m个互不相交的有限集合边、度、高度深度、层次二、树的性质节点数节点数 总度数1节点的度 节点孩子分支个数度为m的树各节点度的最大值为m任意节点的度 m至少有一个节点的度 mm叉树的区别每个节点最多有每个孩子任意节点的度 m允许所用节点的度都 m三 、节点个数4.1 什么是树树Tree是计算机科学和数据结构中一种非常重要的非线性数据结构。它模拟了现实世界中具有层次关系的数据集合如家族谱系、公司组织架构、文件系统目录等。树的定义树是 nn ≥ 0个节点的有限集合。当 n 0 时称为空树当 n 0 时树满足以下条件有且仅有一个特定的节点称为根节点Root其余节点可分为 mm ≥ 0个互不相交的有限集合 T₁, T₂, …, Tₘ其中每个集合本身又是一棵树称为根的子树树的基本术语节点Node树中的基本元素包含数据项及指向其他节点的指针根节点Root没有父节点的节点是整棵树的起点父节点Parent一个节点的直接上层节点子节点Child一个节点的直接下层节点兄弟节点Sibling具有相同父节点的节点叶子节点Leaf没有子节点的节点也称为终端节点分支节点Branch至少有一个子节点的节点度Degree一个节点拥有的子树个数即子节点个数树的度树中所有节点的度的最大值层次Level从根开始定义根为第1层根的子节点为第2层以此类推深度/高度Depth/Height节点的深度从根到该节点的路径上的边数节点的高度从该节点到最远叶子节点的路径上的边数树的高度/深度树中节点的最大层次树的特点层次结构树具有明显的层次关系每个节点除根节点外都有且仅有一个父节点递归定义树可以递归定义子树本身也是树非线性结构与线性表数组、链表不同树中节点之间存在一对多的关系无环图树是连通且无环的图树的表示方法1. 图形表示法最直观的表示方法用圆圈表示节点用连线表示节点间的关系。2. 嵌套集合表示法用集合的包含关系来描述树的结构。3. 凹入表示法缩进表示法类似书籍目录的表示方式通过缩进来表示层次关系。4. 广义表表示法用括号表示节点及其子树的关系。树的应用场景文件系统目录和文件的组织方式数据库索引B树、B树用于高效数据检索组织架构公司、部门的层次关系决策树机器学习中的分类模型语法树编译原理中表示程序语法结构DOM树网页文档对象模型游戏AI博弈树用于决策搜索树的分类根据节点的度限制和结构特点树可以分为二叉树每个节点最多有两个子节点满二叉树所有非叶子节点都有两个子节点且所有叶子节点在同一层完全二叉树除最后一层外其他层都是满的且最后一层节点尽量靠左平衡二叉树左右子树高度差不超过1B树多路平衡查找树用于磁盘存储红黑树自平衡二叉查找树AVL树高度平衡的二叉查找树示例简单的树结构A (根节点) /|\ B C D / \ \ E F G / \ H I在这棵树中根节点A叶子节点E, H, I, GB的父节点AB的子节点E, FC和D是兄弟节点节点F的度2有H和I两个子节点树的度3节点A有3个子节点树的高度3从A到H或I的路径有2条边高度为3树作为一种基础数据结构为许多高级数据结构和算法提供了基础理解树的本质是学习二叉树、堆、图等更复杂结构的前提。