三种判断完全二叉树的方法的实现与分析_二叉树的度为2 - CSDN文库

完全二叉树

4星 · 超过85%的资源需积分: 21 21 浏览量更新于2023-03-16 评论收藏 37KB DOCX 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

三种判断完全二叉树的方法的实现与分析

一．概述

完全二叉树是效率很高的数据结构，堆是一种完全二叉树，所以效率

极高，像十分常用的排序算法、Dijkstra 算法、Prim 算法等都要用堆才能优

化，几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高，而平

衡性基于完全二叉树。对于一棵完全二叉树，叶子节点只可能出现在最下

层和倒数第二层，且最下层的叶子节点集中在树的最左部。

本文对实现判断完全二叉树的三种方法进行了实现，分别是最普遍的

层次遍历的方法和深度遍历的两种方法，并对三种方法进行了分析。

二．层次遍历法

1. 基本思路

由完全二叉树的通俗判断方法出发，发现当层次遍历一棵二叉树

时，当出现某节点的左孩子为空而有孩子不为空时，此树一定不是完

全二叉树；而在另外一种情况下，当出现某节点左右孩子都为空，或

者左孩子不为空而右孩子为空时，此后遍历到的节点如果含有孩子节

点，便不是完全二叉树，反之为完全二叉树。

其中，层次遍历利用队列的形式实现。为了防止队列出现假溢出

的现象，采用了循环队列的方式。

2. 实现

//CompleteBiTree.c

//创建一棵树，并判断其是不是完全二叉树

//主要用到队列的方式，并采用循环队列

剩余10页未读，继续阅读

评论1

demonpark

2014-03-11

谢谢，温习下算法

baobao44199

粉丝: 8
资源: 8

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈