目 录CONTENT

文章目录

【数据结构】---树与二叉树

geekrabbit
2022-09-26 / 0 评论 / 0 点赞 / 49 阅读 / 543 字 / 正在检测是否收录...
温馨提示:
创作不易,转载请注明出处
广告 广告

考研期间学树,因为赶进度,导致这一章学的不好,一直在反功,再次总结树这一章节的学习笔记

常用公式

(1)非空二叉树叶子结点数 = 度为2的结点数 + 1 即,N0=N2+1

(2)非空二叉树上第K层至多有2k−1 个结点(K≥1)

(3)高度为H的二叉树至多有2H−1 个结点(H≥1)

(4)具有N个(N>0)结点的完全二叉树的高度为 ⌈log2(N+1)⌉ 或 ⌊log2N⌋+1

(5)对完全二叉树按从上到下、从左到右的顺序依次编号1,2,...,N,则有以下关系:

① 当 i>1 时,结点 i 的双亲结点编号为 ⌊i/2⌋ ,即当 i 为偶数时,其双亲结点的编号为 i/2 ,它是双亲结点的左孩子;当 i 为奇数时,其双亲结点的编号为 (i−1)/2 ,它是双亲结点的右孩子。

② 当 2i≤N 时,结点i的左孩子编号为 2i ,否则无左孩子。

③ 当 2i+1≤N 时,结点i的右孩子编号为 2i+1 ,否则无右孩子。

④ 结点 i 所在层次(深度)为 ⌊log2i⌋+1 。(设根结点为第1层)

408考研-2011-4  若一棵完全二叉树有768个结点,则二叉树中叶结点的个数是_____。
A.257            B.258            C.384            D.385

解:

根据完全二叉树的性质,最后一个分支结点的序号为 ⌊n/2⌋=⌊768/2⌋=384 ,故叶子结点的个数为 768−384=384

image.png

0
广告 广告

评论区