首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#13201

是不是堆 二叉堆可以用一棵完全二叉树来实现,但完全二叉树不一定满足堆的性质。本题就请你判断一棵给定的完全二叉树是不是堆。 时间限制:1000 内存限制:6553…

是不是堆

二叉堆可以用一棵完全二叉树来实现,但完全二叉树不一定满足堆的性质。本题就请你判断一棵给定的完全二叉树是不是堆。

时间限制:1000

内存限制:65536

输入

输入在一行中给出两个正整数:m(≤ 100)是将要测试的完全二叉树的数量;n(1 < n ≤ 1000)是完全二叉树中的结点数。 随后 m 行,每行给出 n 个互不相同的键值(均在整型范围内),为完全二叉树的层序遍历序列。

输出

对输入的每棵完全二叉树,如果它是最大堆(大顶堆),就在一行中输出 `Max Heap`;如果是最小堆(小顶堆),则输出 `Min Heap`;如果根本不是堆,则输出 `Not Heap`。然后在下一行输出这棵树的后序遍历序列。同行数字间以 1 个空格分隔,行首尾不得有多余空格。


样例输入

3 8
98 72 86 60 65 12 23 50
8 38 25 58 52 82 70 60
10 28 15 12 34 9 8 56

样例输出

Max Heap
50 60 65 72 12 23 86 98
Min Heap
60 58 52 38 82 70 25 8
Not Heap
56 12 34 28 9 8 15 10
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include &lt;iostream&gt; #include &lt;vector&gt; using namespace std;   string checkHeap(const vector&lt;int&gt;&amp; tree) {     int n = tree.size();      for (int i = 0; i &lt; n; ++i) {         int l = 2 * i + 1, r = 2 * i + 2;         if (l &lt; n &amp;&amp; tree[i] &gt; tree[l]) return "Min Heap";         if (r &lt; n &amp;&amp; tree[i] &gt; tree[r]) return "Min Heap";         if (l &lt; n &amp;&amp; tree[i] &lt; tree[l]) return "Max Heap";         if (r &lt; n &amp;&amp; tree[i] &lt; tree[r]) return "Max Heap";     }     return "Not Heap"; }   void printPostOrder(const vector&lt;int&gt;&amp; tree, int i, vector&lt;int&gt;&amp; res) {     if (i &gt;= tree.size())  return;     printPostOrder(tree, 2 * i + 1, res);     printPostOrder(tree, 2 * i + 2, res);     res.push_back(tree[i]);  }   int main() {     int m, n;     cin &gt;&gt; m &gt;&gt; n;     while (m--) {         vector&lt;int&gt; tree(n);         for (int &amp;x : tree) cin &gt;&gt; x;         cout &lt;&lt; checkHeap(tree) &lt;&lt; endl;         vector&lt;int&gt; res;         printPostOrder(tree, 0, res);         for (int i = 0; i &lt; res.size();  ++i) cout &lt;&lt; res[i] &lt;&lt; (i == res.size()  - 1 ? '\n' : ' ');     } }</pre><p><br/></p><pre class="brush:cpp;toolbar:false">//参考代码2 #include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; void postOrder(int index, const vector&lt;int&gt;&amp; arr, vector&lt;int&gt;&amp; res) { if (index &gt;= arr.size()) return; postOrder(2 * index + 1, arr, res); postOrder(2 * index + 2, arr, res); res.push_back(arr[index]); } int main() { int m, n; cin &gt;&gt; m &gt;&gt; n; vector&lt;vector&lt;int&gt;&gt; testCases(m, vector&lt;int&gt;(n)); for (int i = 0; i &lt; m; ++i) { for (int j = 0; j &lt; n; ++j) { cin &gt;&gt; testCases[i][j]; } } for (const auto&amp; arr : testCases) { bool is_max = true, is_min = true; int size = arr.size(); for (int i = 0; i &lt; size; ++i) { int left = 2 * i + 1; int right = 2 * i + 2; if (left &lt; size) { if (arr[i] &lt; arr[left]) is_max = false; if (arr[i] &gt; arr[left]) is_min = false; } if (right &lt; size) { if (arr[i] &lt; arr[right]) is_max = false; if (arr[i] &gt; arr[right]) is_min = false; } if (!is_max &amp;&amp; !is_min) break; } if (is_max) cout &lt;&lt; "Max Heap\n"; else if (is_min) cout &lt;&lt; "Min Heap\n"; else cout &lt;&lt; "Not Heap\n"; vector&lt;int&gt; post; postOrder(0, arr, post); for (int i = 0; i &lt; post.size(); ++i) { if (i) cout &lt;&lt; ' '; cout &lt;&lt; post[i]; } cout &lt;&lt; endl; } return 0; }</pre><p></p>
这道题暂未补解析。