2011年计算机二级公共基础知识考点串讲(6)

文章作者 100test 发表时间 2011:07:06 05:46:25
来源 100Test.Com百考试题网


  1. 6树与二叉树

  1.6.1树的基本概念 (P26—P28)

  在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称为树的根。

  在树结构中,每一个结点可以有多个后件,它们都称为该结点的子结点。没有后件的结点称为叶子结点。

  在树结构中,一个结点所拥有的后件个数称为该结点的度

  在树中,所有结点中的最大的度称为树的度。

  根结点在第1层。

  树的最大层次称为树的深度。

  1.6.2二叉树及其基本性质 (P28—P31)

  1. 什么是二叉树

  二叉树具有以下两个特点:

  ① 非空二叉树只有一个根结点;

  ② 每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。

  2. 二叉树的基本性质

  性质1在二叉树的第K层上,最多有2K-1(K≥1)个结点。

  性质2深度为m的二叉树最多有2m-1个结点。

  性质3在任意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个。

  3. 满二叉树与完全二叉树

  (1)满二叉树

  所谓满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点,这就是说,在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第K层上有2K-1个结点,且深度为m的满二叉树有2m-1个结点。

  (2)完全二叉树

  所谓完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边若干结点。

  满二叉树也是完全二叉树,而完全二叉树一般不是满二叉树。

  性质6设完全二叉树共有n个结点。从根结点开始,按层序用自然数1,2,…,n给结点进行编号,则对于编号为k(k=1,2,…,n)的结点有以下结论:

  ① 若k=1,则该结点为根结点,它没有父结点;若k


相关文章


2011年计算机二级公共基础知识教程汇总
2011年计算机二级公共基础知识考点串讲(9)
2011年计算机二级公共基础知识考点串讲(8)
2011年计算机二级公共基础知识考点串讲(7)
2011年计算机二级公共基础知识考点串讲(6)
2011年计算机二级考试科目
2011年计算机二级C语言上机操作题及答案(24)
2011年计算机二级C语言上机操作题及答案(23)
2011年计算机二级C语言上机操作题及答案(22)
澳大利亚华人论坛
考好网
日本华人论坛
华人移民留学论坛
英国华人论坛