2020年计算机二级《公共基础知识》考点突破:完全二叉树

扫码手机阅读
用圣才电子书APP或微信扫一扫,在手机上阅读本文,也可分享给你的朋友。
评论(0

  为了便于考生复习备考,圣才学习网小编精心整理了计算机二级公共基础知识常用考点,欢迎大家点击查看!更多计算机考试动态|模拟试题|历年真题请关注圣才学习网圣才计算机学习网


  2020年计算机二级《公共基础知识》考点突破:完全二叉树


  完全二叉树是特殊形态的二叉树。


  a.除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。


  b.更确切地说,如果从根结点起,对二叉树的结点自上而下、自左至右用自然数进行连续编号,则深度为m、且有n个结点的二叉树,当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应时,称之为完全二叉树。


  对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现;对于任何一个结点,若其右分支下的子孙结点的最大层次为P,则其左分支下的子孙结点的最大层次或为P,或为p+1。


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


  完全二叉树具有以下两个性质:


  a.具有n个结点的完全二叉树的深度为[1og2n] + 1。


  b.设完全二叉树共有n个结点。如果从根结点开始,按层序(每一层从左到右)用自然数1, 2,…,n给结点进行编号,则对于编号为k (k=1, 2,…,n)的结点有以下结论:


  第一,若k=1,则该结点为根结点,它没有父结点:若k>1,则该结点的父结点编号为INT (k/2)。


  第二,若2k ≤ n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(显然也没有右子结点)。


  第三,若2k+ 1 ≤ n,则编号为k的结点的右子结点编号为2k+ 1;否则该结点无右子结点。


  根据完全二叉树的这个性质,如果按从上到下、从左到右顺序存储完全二叉树的各结点,则很容易确定每一个结点的父结点、左子结点和右子结点的位置。




计算机二级考试电子书

查看全部>>

小编工资已与此挂钩!一一分钱!求打赏↓ ↓ ↓

如果你喜欢本文章,请赐赏:

已赐赏的人
最新评论(共0条)评论一句