請大大幫我解決一下c++的一些問題

1.將下列的二元樹調整唯一棵Heap

15

/ \

23 10

/ \

40 30

2.將下列的資料20,30,10,50,60,40,45,5建立成一棵

Heap。當然您必須將他建立成一棵完整二元樹,之後再依據

Heap的特性調整之。

3.承 2,在已建立完成的Heap中,刪除3060這兩個鍵值。

4.將下列的資料20,30,10,50,60,40,45,5建立成一棵

Min-Heap。

1 Answer

Rating
  • ?
    Lv 5
    1 decade ago
    Favorite Answer

    #include <iostream>

    #include <iomanip>

    using namespace std;

    #define Comp(M,A,B) ((M)?(A<B):(A>B))

    const int Max = 32;

    int heap[Max+1];

    int Hsize=0;

    // 上升

    int Hup(int i, bool min)

    {

    int y = heap[i];

    for (int c=i/2; c>0 && Comp(min,y,heap[c]); c/=2)

    {

    heap[i] = heap[c];

    i = c;

    }

    heap[i] = y;

    return i;

    }

    // 下降

    int Hdown(int i, bool min)

    {

    int y = heap[i];

    for (int c = 2*i; c <= Hsize; c*=2)

    {

    if (c < Hsize && Comp(min,heap[c+1],heap[c])) c++;

    if (Comp(min,y,heap[c])) break;

    heap[i] = heap[c];

    i = c;

    }

    heap[i] = y;

    return i;

    }

    // 插入

    int H_insert(int d, bool min)

    {

    if (Hsize == Max) return 0;

    heap[++Hsize]=d;

    return Hup(Hsize, min);

    }

    // 刪除

    int H_delete(int d, bool min)

    {

    for(int i=1; i<=Hsize; i++)

    if ( heap[i]==d )

    {

    heap[i] = heap[Hsize--];

    if (i==Hup(i, min)) Hdown(i, min);

    return i;

    }

    return -1;

    }

    // 調整為 Heap

    void H_init(bool min)

    {

    for (int i = Hsize/2; i >= 1; i--)

    Hdown(i, min);

    }

    // 以樹狀顯示

    void Show(char *t)

    {

    int p=1;

    while(p<=Hsize) p*=2;

    cout << t << endl << setw(--p);

    for(int i=1, n=1; i<=Hsize; i++, n=p*2-1)

    {

    cout << " " << heap[i] << setw(n);

    if (!(i&(i+1))) cout << endl << setw(p=(p-1)/2);

    }

    cout << endl;

    }

    // 主程式 ===

    int main()

    {

    int i, n;

    int d[] = { 15, 23, 10, 40, 30 };

    n = sizeof(d)/sizeof(int);

    for(i=0, Hsize=n; i<n; i++) heap[i+1]=d[i];

    Show("\n\n(1) 顯示調整前 二元樹:");

    H_init(false);

    Show("\n 顯示調整後 MaxHeap:");

    int a[] = { 20, 30, 10, 50, 60, 40, 45, 5 };

    n = sizeof(a)/sizeof(int);

    for(i=0, Hsize=n; i<n; i++) heap[i+1]=a[i];

    Show("\n\n(2) 顯示調整前 二元樹:");

    H_init(false);

    Show("\n 顯示調整後 MaxHeap:");

    H_delete(30,false);

    H_delete(60,false);

    Show("\n\n(3) 刪除了 30 60 後 MaxHeap:");

    for(i=0, Hsize=0; i<n; i++) H_insert(a[i],true);

    Show("\n\n(4) 由資料所建立的 MinHeap :");

    system("pause");

    return 0;

    }

Still have questions? Get your answers by asking now.