PAT 1147

题目 ： Heaps

分值 ： 30
难度 ： 水题
思路 ： 根据完全二叉树的特性 节点i的字节点为 2*i+1 和 2*i-1  去建树,过程中判断一下是不
       是堆 
坑点 ： 如果你动态的创建一个节点指针数组,直接对他进行赋值是会报错的,因为你建立的仅仅是节
       点指针数组,而不是节点,是没有分配过内存的,因此需要手动申请内存

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <vector>
using namespace std;
int print_flag = 0 ;
typedef struct Node
{
    int self ;
    Node* l ;
    Node* r ;
}Nodes ;
void postorder(Node* pos)
{
    if(pos)
    {
        postorder(pos->l);
        postorder(pos->r);
        if(print_flag++)
            cout <<" ";
        cout << pos->self ;
    }
}
int main() {
    int  M , N ,temp;
    cin >> M >> N ;
    for(int i = 0 ;i <M ; i++)
    {
        Node* head = NULL ;
        Node* list[N] ;
        int old = 0;  // 1 for max  2 for min
        bool flag =true ;
        print_flag = 0 ;
        for(int j = 0 ; j < N ; j++)
        {
            cin >> temp;
            //cout <<temp ;
            Node* cur =(Node*) malloc(sizeof(Node)) ;
            cur->self = temp;
            cur->l =NULL ;
            cur->r =NULL ;
            list[j] = cur ;
            if(j)
            {
                int parent = (j-1)/2 ;
                if(j%2)
                {
                    list[parent]->l = list[j] ;
                    if(flag)
                    {
                        if(list[parent]->self >= list[j]->self )
                        {
                            if(old == 0)
                                old =1 ;
                            if(old ==2 )
                                flag= false ;
                        }
                        if(list[parent]->self <= list[j]->self )
                        {
                            if(old == 0)
                                old =2 ;
                            if(old ==1 )
                                flag= false ;
                        }
                    }
                }
                else
                    list[parent]->r = list[j] ;
            }
        }
        if(!flag)
            cout <<"Not Heap"<<endl ;
        else
        {
            if(old ==1 )
                cout <<"Max Heap"<<endl ;
            else if(old ==2 )
                cout <<"Min Heap"<<endl ;
        }
        postorder(list[0]);
        cout <<endl ;
    }
}