排序：Java实现大顶堆和二叉树的广度优先遍历原理及代码注释详解
附有过程详细思路图解，最后有整体实现的代码
一、堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它是不稳定排序。
1.堆排序简介
堆是一个近似完全二叉树（可以简单理解为从根到最后一层，只有最后一层可以存在二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边）的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
所以堆排序可以有两种： 大顶堆：每个结点的值都大于或等于其左右孩子结点的值； 小顶堆：每个结点的值都小于或等于其左右孩子结点的值。
这里有一个动态可以看一下加强理解，如果不理解也不影响，继续看下去
2.算法思路 这里我是建造大顶堆，利用将数组放入树中，并借助队列记录左右子树的父亲节点，这样方便将数组中的数放入树中节点，可以满足完全二叉树的特点
下面结合图来举例解释 例如，我们有数组{10，8，7，6，5，4，2} （1） 将第一个10放入树中的同时，同时也让10进入队列
（2） 然后按照从左到右的顺序给10安排孩子，让8和7分别作为10的左右孩子放进树中，同时也进入队列，10可以出队了
（3） 同理给8安排孩子，分别是6和5，同时也记录到队列中，8也不需要了那就出队
（4） 利用队列的重点来了，当我们将数组中的5放入到8的右孩子后，如何将4快速定位到7的左孩子呢，这个时候我们只要去找队头的7，就解决问题了。
这样的树就是我们要构建的完全二叉树了，因为举例比较特殊，所以直接也是大顶堆了
3.代码实现
代码语言：javascript代码运行次数：0运行复制 //整体思路，将数组中的数变为堆排序，
// 借助队列记录左右子树的父亲节点，方便放入树中节点（画图解释）
public static void creatTree(int a[]) {//创建完全二叉树
LinkedList<treeNode> listNode = new LinkedList();//新建链表，链表模拟队列
treeNode root = new treeNode(a[0]);//将数组第一位记录到根节点
listNode.addFirst(root);//将根节点数值入队
int temp;//声明借助temp进行两数的交换
for(int i=1;i<a.length;i++) {//for循环遍历数组放入树中（真正的建树过程），以下注释以第一遍循环为例
treeNode thisNode = listNode.getFirst();//将队列中第一个放入树的第一个节点对象（第一次循环为根节点）
if (thisNode.getLeft() == null) { //左孩子为空的情况下
treeNode newNode = new treeNode(a[i]);//新建节点存放数组第二个值
listNode.add(newNode);//队列中增加此时的第二个值
thisNode.setLeft(newNode);//first节点连接左孩子
newNode.setParent(thisNode);//左孩子连接父亲节点
while (newNode.value>thisNode.value){//为了构建大顶堆，插入节点的值与父亲节点值进行比较，保证父亲节点值大
temp=newNode.value;
newNode.value=thisNode.value;
thisNode.value=temp;
if(thisNode==root){//根节点无父亲节点
break;
}
newNode = thisNode;//保证所有的孩子节点和父亲节点遵循大顶堆原则（父亲节点值大于孩子节点）
thisNode=thisNode.getParent();
}
}
else if(thisNode.getRight()==null){//右子树同上
treeNode newNode = new treeNode(a[i]);
listNode.add(newNode);
thisNode.setRight(newNode);
newNode.setParent(thisNode);
listNode.removeFirst();
while (newNode.value>thisNode.value){
temp=newNode.value;
newNode.value=thisNode.value;
thisNode.value=temp;
if(thisNode==root){
break;
}
newNode = thisNode;
thisNode=thisNode.getParent();
}
}
}一个大顶堆的逻辑就这么出来了，下面看看广度优先遍历
二、二叉树的广度优先遍历
1. 二叉树的广度优先遍历介绍 这是百度百科解释：广度优先遍历 我们可以将二叉树的广度优先遍历理解为：对二叉树整体进行从上到下，每层从左到右的遍历。 2.算法思路 对于二叉树的广度优先遍历的做法类似上面构建大顶堆。
利用队列记录操作的父亲，并将其左右孩子存入队列，只是这是不将父亲出队，而是利用标记来指引树的节点在队列中的索引。最后的队列输出结果就是广度优先遍历结果。 继续用图来解释： （1） 首先把根节点10放入队列，并用红色代表我们标记的索引
（2） 如果10的左孩子不为空，我们把8放入队列，右孩子也不空，7也放入队列，10的左右孩子都遍历了，但是这是我们不将10出队，只是将标记下移到8
（3） 利用队列加标记的重点在这里：下面我们该遍历8的左右孩子了，如果8的左孩子不为空，将6入队，右孩子不为空，5入队，8的左右孩子遍历完了，同样是将标记下移到7，目的也是为了方便直接定位到7的左右孩子，进行遍历
（4） 后面依次类推 3.代码实现
代码语言：javascript代码运行次数：0运行复制//通过队列按照每一层树从左到右输出
LinkedList<treeNode> queue = new LinkedList(); //链表模拟队列
int flag = 0;//用来标记树的节点在队列中的索引
queue.add(root);//根节点加入队列头
treeNode rroot ;//操作节点的父亲
while(queue.size()!=a.length){
rroot = queue.get(flag++);
if(rroot.getLeft() != null){//左孩子不空，放入队列
queue.addLast(rroot.getLeft());
}
if(rroot.getRight() !=null){//右孩子不空，放入队列
queue.addLast(rroot.getRight());
}
}
for(int i = 0;i<queue.size();i++){//队列先进先出的性质输出
System.out.print(queue.get(i).value+" ");
}三、Java实现大顶堆和二叉树的广度优先遍历全部代码及注释详解 下面就是将堆排序和广度优先遍历结合起来了直接上代码，有两个文件
Tree.java
代码语言：javascript代码运行次数：0运行复制import java.util.LinkedList;
public class Tree {
//整体思路，将数组中的数变为堆排序，
// 借助队列记录左右子树的父亲节点，方便放入树中节点（画图解释）
public static void creatTree(int a[]){//创建完全二叉树
LinkedList<treeNode> listNode = new LinkedList();//新建链表，链表模拟队列
treeNode root = new treeNode(a[0]);//将数组第一位记录到根节点
listNode.addFirst(root);//将根节点数值入队
int temp;//声明借助temp进行两数的交换
for(int i=1;i<a.length;i++) {//for循环遍历数组放入树中（真正的建树过程），以下注释以第一遍循环为例
treeNode thisNode = listNode.getFirst();//将队列中第一个放入树的第一个节点对象（第一次循环为根节点）
if (thisNode.getLeft() == null) { //左孩子为空的情况下
treeNode newNode = new treeNode(a[i]);//新建节点存放数组第二个值
listNode.add(newNode);//队列中增加此时的第二个值
thisNode.setLeft(newNode);//first节点连接左孩子
newNode.setParent(thisNode);//左孩子连接父亲节点
while (newNode.value>thisNode.value){//为了构建大顶堆，插入节点的值与父亲节点值进行比较，保证父亲节点值大
temp=newNode.value;
newNode.value=thisNode.value;
thisNode.value=temp;
if(thisNode==root){//根节点无父亲节点
break;
}
newNode = thisNode;//保证所有的孩子节点和父亲节点遵循大顶堆原则（父亲节点值大于孩子节点）
thisNode=thisNode.getParent();
}
}
else if(thisNode.getRight()==null){//右子树同上
treeNode newNode = new treeNode(a[i]);
listNode.add(newNode);
thisNode.setRight(newNode);
newNode.setParent(thisNode);
listNode.removeFirst();
while (newNode.value>thisNode.value){
temp=newNode.value;
newNode.value=thisNode.value;
thisNode.value=temp;
if(thisNode==root){
break;
}
newNode = thisNode;
thisNode=thisNode.getParent();
}
}
}
//通过队列按照每一层树从左到右输出大顶堆
LinkedList<treeNode> queue = new LinkedList(); //链表模拟队列
int flag = 0;//用来标记树的节点在队列中的索引
queue.add(root);//根节点加入队列头
treeNode rroot ;//操作节点的父亲
while(queue.size()!=a.length){
rroot = queue.get(flag++);
if(rroot.getLeft() != null){//左孩子不空，放入队列
queue.addLast(rroot.getLeft());
}
if(rroot.getRight() !=null){//右孩子不空，放入队列
queue.addLast(rroot.getRight());
}
}
for(int i = 0;i<queue.size();i++){//队列先进先出的性质输出
System.out.print(queue.get(i).value+" ");
}
}
public static void main(String[] args) {
int a[] = {11,10,4,43,34,54,6};
creatTree(a);
}
}treeNode.java
代码语言：javascript代码运行次数：0运行复制public class treeNode {
private treeNode left;
private treeNode right;
private treeNode parent;
int value;
public treeNode getLeft() {
return left;
}
public void setLeft(treeNode left) {
this.left = left;
}
public treeNode getRight() {
return right;
}
public void setRight(treeNode right) {
this.right = right;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public treeNode getParent() {
return parent;
}
public void setParent(treeNode parent) {
this.parent = parent;
}
public treeNode(int value){
this.value = value;
}
}以上就是个人理解，如果看后还不清楚，可以联系我，争取做到人人看后能明白！ 写着是排序，实际就是构造完大顶堆后对其进行取最大值就好。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-04-07，如有侵权请联系 cloudcommunity@tencent 删除排序原理java二叉树遍历发布者：admin，转转请注明出处：http://www.yc00.com/web/1747865416a4697103.html
评论列表（0条）