c++ - 二叉树到堆树的转换 - 陷入无限循环
问题描述
在解决问题时,我尝试了以下解决方案。不知何故,我的输出陷入了无限循环,而不是打印结果或更新的堆树。
给定一棵树,其中左右子树是最小堆,但根节点不保持最小堆属性。您的代码应修改以 Node* n 为根的树,使其成为最小堆。(这意味着你需要满足最小堆属性:一个节点的值可以等于它的一个或两个子节点,但节点的值不能大于它的任何一个子节点。你不必尝试平衡树或使其成为完整的树。)
#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
如果它在循环体之外,则可能导致无限循环。
推荐阅读
- r - 按字符加入 dplyr 中的数据帧
- python - 如何创建叶图
- android - 在 Android 中有没有办法查看/更改电池输出功率和频率
- c# - 自动签署所有编译的输出文件
- angular - 使用角度服务在多个组件中设置超时
- java - 如何从层次结构中至少删除两个级别的任何内容中隐藏 java 包
- postgresql - 如何将 Postgres 数据库从已安装的磁盘复制到实时 Postgres 服务器
- azure-cosmosdb - 当用户容器将 userId 作为分区键时需要唯一的用户名
- for-loop - R Shiny - 使用 for 循环提取矩阵中的对角线元素
- php - 使用 Laravel 5.6 上传多张图片