二叉树到堆树的转换-陷入无限循环

Question

给定一棵树，其中左和右子树是min堆，但根节点不维护min堆属性。您的代码应该修改根植于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;
}

请建议我缺少什么。我觉得我把它弄得太复杂了。此外，我没有任何其他函数，如swap将二叉树转换为堆MIN。我也没有使用数组或向量。所以，如果你能给我提供简单的解决方案，我会很感激的。

Answer 1

您的主要问题是这行代码：

    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){