2022计算机考研专业课知识点:树的基本术语

2021-03-20 15:56:01 文章来源:专业课透明计划

当今计算机专业竞争日益激烈,题目形式多种多样,涵盖的内容较多,对于报考计算机专业的同学来说,复习是个难点,2022考研计算机的考生要尽早开始准备。学长整理了“2022计算机考研专业课知识点:树的基本术语”希望能帮助大家成功上岸!

下面结合图中的树来说明一些基本术语和概念。

树的树形表示
  ①考虑结点K。根A到结点K的唯 一路径上的任意结点,称为结点K的祖先。如结点B是结点K的祖先,而结点K是结点B的子孙。路径上较接近结点K的结点E称为K的双亲,而K为结点E的孩子。根A是树中唯 一没有双亲的结点。有相同双亲的结点称为兄弟,如结点K和结点L有相同的双亲E,即K和L为兄弟。

  ②树中一个结点的孩子个数称为该结点的度,树中结点的最大度数称为树的度。如结点B的度为2,结点D的度为3,树的度为3。

  ③度大于0的结点称为分支结点(又称非终端结点);度为0(没有子女结点)的结点称为叶子结点(又称终端结点)。在分支结点中,每个结点的分支数就是该结点的度。

  ④结点的深度、高度和层次。

  结点的层次从树根开始定义,根结点为第1层,它的子结点为第2层,以此类推。双亲在同一层的结点互为堂兄弟,图5.1 中结点G与E,E,H,I,J互为堂兄弟。

  结点的深度是从根结点开始自项向下逐层累加的。

  结点的高度是从叶结点开始自底向上逐层累加的。

  树的高度(或深度)是树中结点的较大层数。图5.1中树的高度为4。

  ⑤有序树和无序树。树中结点的各子树从左到右是有次序的,不能互换,称该树为有序树,否则称为无序树。假设图5.1为有序树,若将子结点位置互换,则变成一棵不同的树。

  ⑥路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的边的个数。

  注意:由于树中的分支是有向的,即从双亲指向孩子,所以树中的路径是从上向下的,同一双亲的两个孩子之间不存在路径。

  ⑦森林。森林是m(m≥0)棵互不相交的树的集合。森林的概念与树的概念十分相近,因为只要把树的根结点删去就成了森林。反之,只要给m棵独立的树加上一个结点,并把这m棵树作为该结点的子树,则森林就变成了树。

在考研复习的中遇到了自己不会解决的问题的话,还可以参加专业课透明计划课程,直系学长学姐一对一答疑,备考更科学合理,复习更加踏实有效。还能送很多专业课复习用得上的资料,省了一笔买资料的钱。

以上就是“2022计算机考研专业课知识点:树的基本术语”的所有内容,

希望能帮到正在考研的你。