二叉搜索樹C++實現（動態內存問題）

Question

我目前正在學習如何實現二叉搜索樹，但使用更基本的C方法（請不要「現在使用類」）。但是，動態內存自身刪除存在很大的問題。頭值得到正確更新，但是，其他每一點都會被刪除。誰能幫我？另外，如果你會提供一些技巧來強化我的樹的實現，那將是很好的。該程序的基本概要：您輸入一個字符，然後運行其中一個樹的功能。但是請注意，這個實現是一個純粹的BST，所以沒有平衡。謝謝。

#include <iostream> 

struct point{ 
    point* parent, *left, *right; 

    int val = -1; 
}; 

point* biggest; 
point empty; 

point search(int pos, bool near, point* loc = biggest){ 
    if(loc->val == pos){ 
     return *loc; 
    } else if(loc->left->val != -1 and loc->val > pos){ 
     return search(pos, near, loc->left); 
    } else if(loc->right->val != -1){ 
     return search(pos, near, loc->right); 
    } 

    if(near){ 
     return *loc; 
    } else{ 
     point fail; 
     return fail; 
    } 
} 

void insert(int pos, point* res){ 
    point loc = search(pos, true); 
    res->val = pos, res->left = &empty, res->right = &empty, res->parent = &loc; 
    if(loc.val < res->val){ 
     loc.left = res; 
    } else{ 
     loc.right = res; 
    } 

} 

void remove(int pos){ 

} 

int pred(int pos){ 
    point res = search(pos, false); 
    if(res.val == -1){ 
     return -1; 
    } 

} 

int succ(int pos){ 
    point res = search(pos, false); 
    if(res.val == -1){ 
     return -1; 
    } 

} 

void inorder(point* pos = biggest){ 
    if(pos->left->val != -1){ 
     inorder(pos->left); 
    } 
    std::cout << pos->val << " "; 
    if(pos->right->val != -1){ 
     inorder(pos->right); 
    } 
} 

int main() { 
    point start; 
    start.parent = &empty, start.left = &empty, start.right = &empty; 
    biggest = &start; 
    char c; 
    int pos; 
    do{ 
     std::cin >> c >> pos; 

     switch (c){ 
      case 'S': 
       std::cout << search(pos, false).val << std::endl; 
       break; 
      case 'I': 
       if(biggest->val == -1){ 
        start.val = pos; 
       } else{ 
        point* res = new point; 
        insert(pos, res); 
       } 
       break; 
      case 'R': 
       remove(pos); 
       break; 
      case 'P': 
       std::cout << pred(pos) << std::endl; 
       break; 
      case 'N': 
       std::cout << succ(pos) << std::endl; 
       break; 
      case 'O': 
       inorder(); 
       std::cout << std::endl; 
       break; 
     } 
    } while(c != '0'); 
    return 0; 
} 

Answer 1

除了在你的代碼更古怪我想說的是這裏：

void insert(int pos, point* res){ 
    point loc = search(pos, true); 
    res->val = pos, res->left = &empty, res->right = ∅ 
    res->parent = &loc; // <=== here 

修改res->parent在一個局部變量loc點。在insert()函數返回point loc之後不再存在。

另外你是已經在使用類;除了默認的成員可見性，C++結構和類幾乎完全相同。