二叉搜索树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++结构和类几乎完全相同。