树(Tree)

xiaohai 2021-07-24 16:15:25 241人围观 标签: 算法 
简介树是计算机中非常重要的一种数据结构,使用树这种数据结构可以描述显示生活中很多事物,例如家谱图、单位的组织架构等等

4.7.1、树的定义

树是计算机中非常重要的一种数据结构,使用树这种数据结构可以描述显示生活中很多事物,例如家谱图、单位的组织架构等等

树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。把它叫做树是因为它开起来想一个倒挂的树,也就是它的根朝上,而叶朝下。

图片alt

特点

  • 每个结点有零个或多个子节点
  • 没有父结点的节点称为根节点
  • 每一个非根节点只有一个父结点
  • 每个结点及其后代结点整体上可以看做一棵树,称为当前结点的父结点的一个子树

4.7.2、树的相关概念

  • 结点的度:一个结点含有的子树个数称为该结点的度
  • 叶结点:度为0的结点称为叶结点,也可以叫做终端结点
  • 分支结点:度不为0的结点称为分支结点,也可以叫做非终端结点
  • 结点的层次:从根节点开始,根节点的层次为1,根节点的后继层次为2,以此类推
  • 结点的层序编号:将树中的节点按照从上往下,同一层从左到右的次序排成一个线性的序列,把它们编成连续的自然数
  • 树的度:树中所有结点的度的最大值
  • 树的高度(深度):树中结点的最大层次
  • 森林:m(m>=0)个不相交的树的集合,将一颗非空树的根节点删除,树就变成了一个森林,给森林添加一个统一的根节点,森林就变成一棵树
  • 孩子结点:一个结点的直接后继结点称为该结点的孩子结点
  • 双亲结点(父结点):一个结点的直接前驱称为该结点的双亲结点
  • 兄弟结点:同一双亲结点的孩子结点互称为兄弟结点