树的概念及基本术语

树的定义

  • 树是一种非线性数据结构,它是若干结点的集合。
  • 是由唯一的和若干不相交的子树组成的。
  • 子树又是一颗树,因此树的定义是递归的。
  • 树的结点数目可为0,此时称之为空树

树的基本术语

  • 结点(结点包含数据元素和指向子树的分支)
  • 路径:一个结点和另一个经过的边和结点的序列
  • 根(根结点):一棵树的顶点
  • 结点的度:结点拥有子树和分支的个数。
  • 树的度:树中结点度的最大值。
  • 叶子结点(终端结点):度为0的结点。
  • 分支结点(非终端结点):度不为0的结点。
  • 孩子:结点的子树的根。
  • 双亲(父结点):指向该结点的结点。
  • 兄弟:拥有相同父结点的孩子互称兄弟。
  • 祖先:从根到某结点路径上的所有结点,都称为该结点的祖先。
  • 子孙:以某结点为根的子树的所有结点都为该结点的子孙。
  • 层次:从根开始,为第一层,根的孩子为第二层,根的孩子的孩子为第三层,以此类推。
  • 树的高度(树的深度):树中结点的最大层次。
  • 堂兄弟:双亲不同但双亲在同一层的结点之间互称堂兄弟。
  • 有序树:树中结点的子树从左到右是有次序的,不能交换,这样树叫有序树。
  • 无序树:树中结点的子树没有顺序
  • 丰满树(理想平衡树):除最底层外,其他层都是满的树。
  • 森林:若干棵不相交的树的集合。

对与结点深度和高度的理解

  1. 结点的深度是指根结点到该结点路径上结点的个数
  2. 从某结点往下走到终端结点可有多条路径,最长的那条路径上结点的个数为该结点在树中的高度。
  3. 根结点的高度为树的高度

树的储存结构

  • 顺序储存结构
  • 链式储存结构
    • 孩子储存结构(本质上是图的邻接表储存结构)
    • 孩子兄弟储存结构
作者

CairBin

发布于

2021-10-31

更新于

2021-10-31

许可协议

评论