引论:
树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。 树在计算机领域中也得到广泛应用，如在编译 源程序 如下时，可用树表示源源程序如下的语法结构。 又如在 数据库系统 中，树型结构也是信息的重要组织形式之一。
家族谱 ,
企业组织架构 ,
磁盘保存的文件夹 , 计算机组成可以有若干个设备, 每个设备又挂接若干个子设备 ;
网站的首页 , 有若干个目录 , 每个目录下 ,又有若干个分支 .
计算机语言类库 , 有若干个层次 ,一对多的关系 .
当我们面临众多的一对多关系的时候 , 在程序设计中 , 我们要拿出一个同一的处理 , 我们需要去做一个抽象的 , 去除了应用里面的具体事物的具体形态 , 找到本质 .
构造 : 所以我们构造出一个树来 , 他有一个所谓的根 ,根下面有若干个分支 ,分支又有若干个节点
树 有树根 ,有树枝 , 所以我们在计算机里面可以利用图示来描述
树的形式化定义:
树 : T = {D,R}
D = { A , B , C , D ,E , F , G , H , I , J , K , L , M }
R = { r }
r = {
● D 是包含 n 个节点的有穷集合(n>=0)
• 当 n = 0 时 , 为空树
● 当 n > 0 时 , 关系 R 满足以下一对多关系
• 有且仅有一个节点 d0∈D 没有前驱节点, 节点 d0称作树的 根节点
• 除根节点d0外 , D 中的每个节点有且仅有一个前驱节点
• D中每个节点可以有零个或多个后继节点
有趣的术语:
●每个节点的后继 , 被称作该节点的 孩子节点(或子女节点) . 相应地 , 该节点被称作孩子节点的 双亲节点（或父母节点）
● 具有同一双亲的孩子节点互为 兄弟节点
● 每个节点的所有子树中的节点称为 子孙节点
●从树根节点到达节点的路径上经过的所有节点被称作该节点的 祖先节点
数的递归定义
树是由n(n>=0)个节点组成的有限集合(记为T)
● 如果 n = 0 ,它是一棵空树 , 这是树的特例;
● 如果 n>0
• 这 n 个节点中存在(有且仅存在)一个节点作为树的根节点,简称根节点(root)
• 其余节点可分为m ( m>0 )个互不相交的有限集 T1,T2,…,Tm , 其中每一颗子集本身又是一颗符合本定义的树 ,称为根root的子树
数的表示法
树的数据结构
ADT Tree
{
数据对象:
D = {ai | ai∈ElemType, i=1,2,…,n,n>=0} //ElemType为类型标识符
数据关系:
R = {
树的运算主要分为三大类:
● 第一类, 寻求满足某些特定关系的节点 , 如寻找双亲节点;
● 第二类 , 插入或删除某个节点 , 如在树的当前节点上插入一个新节点或删除当前节点的第i个孩子节点等.
● 第三类, 遍历树中的每个节点
遍历操作
● 树的遍历
• 按照一定次序访问树中的所有节点,并且每个节点仅被访问一次的过程.
• 遍历是最基本的运算 , 是树中所有其他运算的基础
● 树的三种遍历
• 先根遍历 : 若树不空,则先访问根节点,然后依次先根遍历各棵子树.
• 后根遍历 : 若树不空,则先依次后根遍历各颗子树,然后访问根节点.
• 层次遍历 : 若树不空,则自上而下自左至右访问树中的每个节点.
Original: https://blog.csdn.net/qq_57484399/article/details/127805920
Author: 黄交大彭于晏
Title: 树结构导学
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/657739/
转载文章受原作者版权保护。转载请注明原作者出处！