преобразовать дерево двоичного поиска в списки

Question

Я попытался отладить этот вопрос: преобразование двоичного дерева поиска в связанные списки всех узлов на каждом уровне. Но я столкнулся с ошибкой времени выполнения. В коде я в основном запускаю 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 

Answer 1

Это удар в темноте.

оборванных указатель представляет собой указатель, который указывает на местоположение в памяти, которая не адрес законного объекта ожидаемого типа. Возможно, адрес утерянного объекта больше не находится под защитой диспетчера памяти или место в середине какого-либо несвязанного объекта или место в нераспределенной памяти или даже за пределами реальной памяти. На практике он может содержать любой старый случайный мусор и пытаться разыменовать его (т. Е. Использовать его, как если бы он был законным объектом) вызывает неопределенное поведение (т. Е. Что-то может произойти, и оно может потерпеть неудачу особыми способами).

Функция должна возвращать значение типа, указанного его подписью. Ваша функция BSTNode<Key, Value>* min_height(...) должна вернуть указатель на BSTNode. Но как написано, он делает это только if(left<=right), иначе он просто заканчивается; Я не уверен, что происходит в этом случае, но я думаю, что возможно, что, по крайней мере, под некоторыми компиляторами он вернет неопределенный указатель - случайный, а не в хорошем смысле. Хороший компилятор предупредит вас об этом. (По-моему, хороший указатель должен отказаться от его компиляции, но это еще один напыщенный вопрос.)

Так исправить функцию; min_height(...) верните правильное значение, если условие не выполнено. Если это не исправить ошибку, дайте нам знать, и мы попробуем что-то еще. (Спойлер:. ןן ню Ši ǝn ןɐʌ ɔıɟıɔǝds ʇɔǝɹɹoɔ ǝɥʇ)