深圳幻海软件技术有限公司 欢迎您!

数据结构:完全二叉树开胃菜小练习

2023-03-14

目录一.前言二.完全二叉树的重要结构特点三.完全二叉树开胃菜小练习1.一个重要的数学结论2.简单的小练习一.前言关于树及完全二叉树的基础概念(及树结点编号规则)参见:http://t.csdn.cn/imdrahttp://t.csdn.cn/imdra完全二叉树是一种非常重要的数据结构:n个结点的

目录

一.前言

二.完全二叉树的重要结构特点

三.完全二叉树开胃菜小练习

1.一个重要的数学结论

2.简单的小练习


一.前言

关于树及完全二叉树的基础概念(及树结点编号规则)参见:http://t.csdn.cn/imdrahttp://t.csdn.cn/imdra

完全二叉树是一种非常重要的数据结构:

n个结点的完全二叉树结点编号是从0~(n-1)连续排列的(假设根结点的编号为0),因此将完全二叉树映射到内存中线性存储结构中内存利用效率十分的高(数组下标和树结点编号建立绝对映射关系).

最经典的完全二叉树线性存储结构就是大小根堆(堆排序的数据结构基础)

二.完全二叉树的重要结构特点

  • 假设一个结点总数为n完全二叉树T的高度为k,为了满足各结点编号是0~(n-1)连续排列的结构定义,完全二叉树1~(k-1)层所有结点构成的子结构是一颗满二叉树(也就意味着完全二叉树的所有叶结点分布在树的最后一层(第k层)):
  • 假设一个结点总数为n完全二叉树T的高度为k,为了满足各结点编号是0~(n-1)连续排列的结构定义,完全二叉树的第k层(最后一层)的叶节点必须是连续排列的(也就是意味着结点总数为奇数的完全二叉树不存在出度为1的分枝结点,结点总数为偶数的完全二叉树有且仅有一个出度为1的分枝结点)

三.完全二叉树开胃菜小练习

1.一个重要的数学结论

  • 对任何一棵二叉树, 如果出度为0其叶结点个数为N0出度为2的分枝结点个数为N2(包括根) ,则有 N0= N2+1

该结论具体证明参见小青菜的博客 :http://t.csdn.cn/imdrahttp://t.csdn.cn/imdra

2.简单的小练习

  • 现有一颗具有 2n 个结点的完全二叉树T,求其叶结点的个数

求解:

设T出度为0的结点个数为N0(即叶结点的个数),

出度为1的结点个数为N1,

出度为2的结点个数为N2。

根据本篇第二章中的结构分析可知,N1要么为1,要么为0

  1. N1 = 0,根据关系式N0 = N2 + 1,可得:2n = N0 + N1 + N2,化简可得N0 = (2n+1)/2,N0不为整数,因此该种情况排除
  2. N1 =1,根据关系式N0 = N2 + 1,可得:2n = N0 + N1 + N2,化简可得N0 = n,满足题意

因此T叶节点个数为n

  • 一棵完全二叉树的结点总数为531个,求这棵树的高度

求解:

设该树的高度为k

根据本篇第二章中的结构分析可知,该树前k-1层构成一颗满树(根据等比数列求和公式满树总结点个数为2^(k-1)-1)

2^9 = 512<531<2^10 = 1024,因此k-1 = 9,可以求得该二叉树的高度为10

  • 现有一颗具有767个结点的完全二树T,求其叶子结点个数

求解:

设T出度为0的结点个数为N0(即叶结点的个数),

出度为1的结点个数为N1,

出度为2的结点个数为N2。

根据本篇第二章中的结构分析可知,N1要么为1,要么为0

  1. N1 = 0,根据关系式N0 = N2 + 1,可得:767 = N0 + N1 + N2,化简可得N0 = 384,满足题意
  2. N1 =1,根据关系式N0 = N2 + 1,可得:767 = N0 + N1 + N2,化简可得N0 = 767/2,N0不为整数,因此该种情况排除

因此T叶节点个数为384

 

 

 

文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树首页概览40346 人正在系统学习中