哈夫曼树的创建造成死循环？

Question

class HufTree
{
public:
    HufTree(int val)
    {
        this->data = val;
        this->left = nullptr;
        this->right = nullptr;
    }
    /*HufTree(const HufTree& T)
    {
        this->data = T.data;
        this->left = T.left;
        this->right = T.right;
    }*/
    int data;
    HufTree* left;
    HufTree* right;
};
bool Mysort(HufTree A, HufTree B)
{
    return A.data < B.data;
}
void printHuf(HufTree* T)
{
    if (T == nullptr)
    {
        /*cout << "null" << endl;*/
        return;
    }
    cout << T->data << " ";
    printHuf(T->left);
    printHuf(T->right);
    return;
}
int main()
{
    


    int temp[7] = { 13,7,8,3,29,6,1 };
    list<HufTree>s;
    for (auto x : temp)
    {
        HufTree Huf(x);
        s.push_back(Huf);
    }
    s.sort(Mysort);
    while (s.size() > 1)
    {
        auto it = s.begin();
        HufTree A(*it)；
        it++;
        HufTree B(*it);
        HufTree T(A.data + B.data);
        T.left = &A;
        T.right = &B;
        s.pop_front();
        s.pop_front();
        s.push_back(T);
        s.sort(Mysort);
    }
    HufTree* root = &s.front();
    printHuf(root);
    system("pause");
    return 0;
}

Answer 1

函数栈空间是固定大小的，局部变量离开作用域后就无效了，空间会被回收利用，例如 while 中的 A、B，每次循环其地址（&A、&B）都是固定的，自然所有 left 指针都指向同一块栈空间，right 同理，存的内容也不一定是一个 HufTree 对象

这里给个使用 new 分配内存创建对象的写法参考，当然也不是一定要动态分配内存，只要保证不被自动释放内存即可，比如可以把对象存到一个数组里，不要删除就可以保证一直存活，然后 left 和 right 指针指向数组中元素的地址即可

class HufTree {
public:

  HufTree(int val) {
    this->data = val;
    this->left = nullptr;
    this->right = nullptr;
  }
  /*HufTree(const HufTree& T)
  {
      this->data = T.data;
      this->left = T.left;
      this->right = T.right;
  }*/
  // 1 析构函数
  ~HufTree() {
    delete left;
    delete right;
  }
  int data;
  HufTree *left;
  HufTree *right;
};
bool Mysort(HufTree *A, HufTree *B) { // 2 改为指针
  return A->data < B->data;
}
void printHuf(HufTree *T) {

  if (T == nullptr) {
    /*cout << "null" << endl;*/
    return;
  }
  cout << T->data << " ";
  printHuf(T->left);
  printHuf(T->right);
  return;
}
int main() {
  int temp[7] = { 13,7,8,3,29,6,1 };
  list<HufTree *>s; // 3 改为指针
  for (auto x : temp) {
    HufTree *Huf = new HufTree(x); // 4 new 分配内存
    s.push_back(Huf);
  }
  s.sort(Mysort);
  while (s.size() > 1) {
    auto it = s.begin();
    it++;
    HufTree *A = s.front(); // 5 改为指针
    HufTree *B = *it; // 6 改为指针
    HufTree *T = new HufTree(A->data + B->data); // 7 改为指针
    T->left = A; // 8 指针直接赋值
    T->right = B; // 9 指针直接赋值
    s.pop_front();
    s.pop_front();
    s.push_back(T);
    s.sort(Mysort);
  }
  HufTree *root = s.front(); // 10 指针直接赋值
  printHuf(root); // 输出 67 29 38 15 7 8 23 10 4 1 3 6 13
  delete root; // 11 delete 释放内存
  return 0;
}