在解决问题时,我尝试了以下解决方案。不知何故,我的输出陷入了无限循环,无法打印结果或更新的堆树。
给出一棵树,其中左和右子树是最小堆,但是根节点不保留最小堆属性。您的代码应修改以Node * n为根的树,因此它是最小堆。 (这意味着您需要满足min heap属性:节点的值等于其一个或两个子节点是可以的,但该节点的值不得大于其两个子节点中的一个。您不必尝试平衡树或使其成为完整的树。)
#include <iostream>
#include <string>
You have the following class Node already defined.
You cannot change this class definition, so it is
shown here in a comment for your reference only:
class Node {
public:
int value;
Node *left, *right;
Node(int val = 0) { value = val; left = right = nullptr; }
~Node() {
delete left;
left = nullptr;
delete right;
right = nullptr;
}
};
This function has also previously been defined for you:
void printTreeVertical(const Node* n);
You can use it to print a verbose, vertical diagram of
a tree rooted at n. In this vertical format, a left child
is shown above a right child in the same column. If no
child exists, [null] is displayed.
*/
void downHeap(Node *n) {
Node *curr = new Node();
Node *mino = new Node();
if (n == nullptr ){
return;
} else if (n->left->value > n->value & n->right->value > n->value){
return;
// } else if (n->left== nullptr & n->right== nullptr) {
// return;
// }
} else {
// node* curr = new Node(n)
// n = new Node((std::min(n->left->value, n->right->value));
// if (n->left->value)
while(n->left!= nullptr & n->right!= nullptr){
if (n->left == nullptr){
mino = n->right;
} else if (n->right == nullptr) {
mino = n->left;
} else {
mino = (std::min(n->left, n->right));
}
std::cout << n->value << std::endl;
std::cout << mino->value << std::endl;
if(n->value > mino-> value){
curr->value = n->value;
n->value = mino->value;
mino->value = curr->value;
std::cout << n->value << std::endl;
std::cout << mino->value << std::endl;
downHeap(mino);
}
}
return;
}
}
// Implement downHeap() here.
// You can also use this compact printing function for debugging.
void printTree(Node *n) {
if (!n) return;
std::cout << n->value << "(";
printTree(n->left);
std::cout << ")(";
printTree(n->right);
std::cout << ")";
}
int main() {
Node *n = new Node(100);
n->left = new Node(1);
n->left->left = new Node(3);
n->right = new Node(2);
n->right->left = new Node(3);
n->right->right = new Node(4);
n->right->right->right = new Node(5);
std::cout << std::endl << "BEFORE - Vertical printout:" << std::endl;
printTreeVertical(n);
downHeap(n);
std::cout << "Compact printout:" << std::endl;
printTree(n);
std::cout << std::endl << " AFTER Vertical printout:" << std::endl;
printTreeVertical(n);
delete n;
n = nullptr;
return 0;
}
请提示我所缺少的。我觉得我太复杂了。另外,我没有其他诸如交换功能,可以将二叉树转换为堆最小值。我也没有使用数组或向量。因此,如果您能为我提供简单的解决方案,我将不胜感激。
您的主要问题是以下代码行:
mino = (std::min(n->left, n->right));
这里,当您确实要比较要引用的两个对象中的值,并返回指向值较小的对象的指针时,您正在比较两个指针。那是:
mino = (n->left->value < n->right->value) ? n->left : n->right;
也在此代码行中:
} else if (n->left->value > n->value & n->right->value > n->value){
您可能需要&&
(逻辑与),而不是&
(按位与)。参见https://www.geeksforgeeks.org/what-are-the-differences-between-bitwise-and-logical-and-operators-in-cc/。
最后,您的代码格式略有偏离,因此很难说出来,但是看起来return
语句在while
函数中的downHeap
循环之外。如果它在循环主体之外,则可能导致无限循环。