聊城有限公司网站建设 中企动力济二分,做抛物线的网站,wordpress 改为中文,网站建设中的色彩搭配目录 树的定义
树的基本术语
树的初始起点#xff1a;我们定义为根
树的层次#xff1a;
树的定义#xff1a;
树的性质
性质1#xff1a;
性质2#xff1a;
树形结构存储的两种思路
树的遍历模板 树上信息统计方式1-自顶向下统计
树上信息统计方式2-自底向上统…目录 树的定义
树的基本术语
树的初始起点我们定义为根
树的层次
树的定义
树的性质
性质1
性质2
树形结构存储的两种思路
树的遍历模板 树上信息统计方式1-自顶向下统计
树上信息统计方式2-自底向上统计
子树的概念
总结编辑 树的定义 树Tree是nn≥0个结点的有限集。n0时称为空树。在任意一颗非空树中①有且仅有一个特定的称为根Root的结点②当n1时其余结点可分为mm0个互不相交的有限集T 1 {T}_{1}T 1 、T 2 {T}_{2}T 2 、… 、T m {T}_{m}T m 其中每一个集合本身又是一棵树并且称为根的子树Sub Tree。 树的基本术语
节点的度一个节点含有的子树的个数称为该节点的度叶节点或终端节点度为0的节点称为叶节点非终端节点或分支节点度不为0的节点双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点兄弟节点具有相同父节点的节点互称为兄弟节点树的度一棵树中最大的节点的度称为树的度节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推树的高度或深度树中节点的最大层次堂兄弟节点双亲在同一层的节点互为堂兄弟节点的祖先从根到该节点所经分支上的所有节点子孙以某节点为根的子树中任一节点都称为该节点的子孙。森林由mm0棵互不相交的树的集合称为森林 树的初始起点我们定义为根 递归树中都只能从父节点走到子节点。 我们只需要记录每个父节点有哪些子节点那么就可以遍历整个递归树。
树的层次 节点高度指从这个节点到叶子节点的距离一共经历了几个节点 节点深度指从当前节点到根节点的距离一共经历了几个节点 树的高度指所有节点高度的最大值 树的深度指所有节点深度的最大值 节点的层从根节点开始假设根节点为第1层根节点的子节点为第2层依此类推
树的定义 有n(n0)个节点且任意两个点有且仅有一条路径连通的图形。若n0此时为空树。 树的性质 性质1
n个节点保证任意两点有且仅有一条路径树中有且仅有n-1条边。 证明除第一个节点外连接一个其他节点至少增加一条边所以n个点至少要用n-1条边才能保证所有节点连通。若此时再增加一条非重边任意两点间是否还存在一条唯一路径。 性质2
树的根结点没有前驱(父节点)除根结点外的所有结点有且只有一个前驱。树中所有结点可以有零个或多个后继(子节点)。 证明同上。 树形结构存储的两种思路 1.用结构体把每个节点的信息进行封装。这样的优点在于节点信息非常独立但是所占空间稍大。2.用多个数组分别描述每个节点的对应信息。这种方式的有点在于速度稍快写起来简单。 树的遍历模板 通常来讲树的边都是双向的我们在遍历的时候不希望一个点遍历多次。 方法1.用vis数组进行标记。 方法2.dfs中记录由父亲节点(来向)这样可以阻止走回去。 树上信息统计方式1-自顶向下统计 操作方法在进入dfs之前进行信息统计。 如求链长树上两个节点必然有且仅有一条路径我们可以把该路径看成一条链。路径上的边权和为两点的链长。 树上信息统计方式2-自底向上统计 操作方法在dfs回溯之时进行信息统计。 如求树的节点个数当前树上共有多少个节点。 子树的概念 抹除当前根节点以及所有与根节点的连边后产生的树都是当前根节点的子树。 如当前根节点1的子树有以2、3、4为根的子树。 总结
