0

我试图调试这个问题：将二叉搜索树转换为每个级别的所有节点的链表。但是我遇到了运行时错误。在代码中，我基本上运行二叉搜索树的 BFS 并跟踪每个级别，如果新级别命中，我创建一个新的链表来存储新级别的节点。我使用 STL 的链表来存储节点。在此之前，我使用函数 min_height 创建了一个二叉搜索树。我用输入向量 = {1, 2, 3, 4, 5, 6} 测试这些方法。这棵树如下图所示。它在某些节点上运行良好，但在节点 2 处停止。我不知道原因，有人可以帮助我吗？谢谢 ！在此处输入图像描述

#include <iostream>
#include<string>
#include<vector>
#include<queue>
#include<list>
using namespace std;

template<typename Key, typename Value>
struct BSTNode{
 Key key;
 Value value;
 BSTNode * left;
 BSTNode * right;
 BSTNode(Key k, Value v, BSTNode *l=NULL, BSTNode *r=NULL): key(k), value(v), left(l), right(r) {}
 };


template<typename Key, typename Value>
vector< list<BSTNode<Key, Value>*> > creat_lists(BSTNode<Key, Value>* root){
 vector< list<BSTNode<Key, Value>*> > v;
 if(root==NULL) return v; 
 queue<BSTNode<Key, Value>*> q;   queue<int> level;  int prev;
 q.push(root);   level.push(0);   prev=-1;
 while(!q.empty()){
  BSTNode<Key, Value>* cur=q.front();    int cur_level=level.front();
  cout<<"cur->key: "<<cur->key<<" cur_level: "<<cur_level<<endl;

  if(prev!=cur_level){
    list<BSTNode<Key, Value>*> l;
    l.push_back(cur);
    v.push_back(l);
  }
  else  {cout<<"got in"<<endl;  v.back().push_back(cur);}

  if(cur->left )cout<<"cur->left: "<<cur->left->key<<endl;
  if(cur->right )cout<<"cur->right: "<<cur->right->key<<endl;

  prev=cur_level;
  if(cur->left) {q.push(cur->left);  level.push(cur_level+1); }
  if(cur->right) {q.push(cur->right);  level.push(cur_level+1);}



  q.pop();    level.pop();


 }
return v;
}


template<typename Key, typename Value>
BSTNode<Key, Value>* min_height(vector<int> &v, int left, int right ){// here is different from my paper code
  if(left<=right){
    int mid=left+ (right-left)/2;
    BSTNode<Key, Value>* node=new BSTNode<Key, Value>(v[mid], v[mid]);
    node->left=min_height<Key, Value>(v, left, mid-1 );
    node->right=min_height<Key, Value>(v, mid+1, right );
    return node;
    }
}


int main(){
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  v.push_back(5);
  v.push_back(6);  
  BSTNode<int, int>* root=min_height<int, int>(v, 0, 5);
 vector<list<BSTNode<int, int>*> > newv=creat_lists(root);
 //for(int i=0; i<newv.size(); i++)  cout<<(v[i].front())->key<<endl;
}



complier result:
Run Status: Runtime Error

cur->key: 3 cur_level: 0
cur->left: 1
cur->right: 5
cur->key: 1 cur_level: 1
cur->right: 2
cur->key: 5 cur_level: 1
got in
cur->left: 4
cur->right: 6
cur->key: 2 cur_level: 2
4

1 回答 1

0

这是在黑暗中刺伤。

悬空指针是指向内存中某个位置的指针，该位置不是预期类型的​​合法对象的地址。它可能是不再受内存管理器保护的已失效对象的地址，或者是某个不相关对象中间的位置，或者是未分配内存中的一个点，甚至是实际内存边界之外的位置。在实践中，它可以包含任何旧的随机垃圾，并且试图取消引用它（即像使用它是合法对象一样使用它）会导致未定义的行为（即任何事情都可能发生，并且它可能以特殊的方式失败）。

函数应返回其签名所指示的类型的值。你的函数BSTNode<Key, Value>* min_height(...)应该返回一个指向 a 的指针BSTNode。但正如所写的那样，它只这样做if(left<=right)，否则它只会终止；我不确定在这种情况下到底会发生什么，但我认为至少在某些编译器下它可能会返回一个未定义的指针——随机的，而且不是很好的方式。一个好的编译器会警告你这一点。（在我看来，一个好的指针应该拒绝编译它，但这是另一个咆哮。）

所以修复函数；min_height(...)如果条件不满足，则返回正确的特定值。如果这不能修复错误，请告诉我们，我们将尝试其他方法。（剧透： ןןnu sıǝnןɐʌ ɔıɟıɔǝds ʇɔǝɹɹoɔ ǝɥʇ。）

于 2013-03-13T13:59:32.060 回答