堆的后序遍历(DS排序)

2023-07-30 13:52:35 浏览数 (2)

题目描述

给定一个整数序列, 把它建成最小堆,输出堆的后序遍历

假定序列无重复数字

输入

只有一行,先输入n表示序列包含n个整数,接着输入n个整数

输出

序列转变成最小堆后,输出堆的后序遍历

输入样例1

7 49 38 65 97 76 13 27

输出样例1

97 76 38 65 49 27 13 

AC代码

代码语言:javascript复制
#include<iostream>

using namespace std;

class minHeap{
    int data[256],n;
public:
    void adjust(int i,int last){
        int temp=data[i];
        for(int j=2*i 1;j<=last;j=2*j 1){
            if(j<last&&data[j]>data[j 1])
                j  ;
            if(data[j]>=temp)
                break;
            data[i]=data[j];
            i=j;
        }
        data[i]=temp;
    }
    minHeap(){
        cin>>n;
        for(int i=0;i<n;i  )
            cin>>data[i];
        for(int i=n/2;i>=0;i--)
            adjust(i,n-1);
        postorder(0);
    }
    void postorder(int i){
        if(i>=n)
            return;
        postorder(2*i 1);
        postorder(2*i 2);
        cout<<data[i]<<' ';
    }
};

int main() {
    minHeap test;
}

0 人点赞