c++ - 树程序哪里出错了？

Question

下面是我用VS2008写的两段示例代码。第一个示例代码工作正常，而第二个(树的)给出了一些错误。

 1)
#include<iostream>
using namespace std;

struct node{
        int number;
        struct node *right;
        struct node *left;
    }nodeType;

int insert(struct node *,int);

int main(){

        struct node * root=(struct node *)malloc(sizeof(node));
        root->left=NULL;
        root->right=NULL;
        root->number=10;
        insert(root,100);
      cout<<root->right->number; //This works fine

        return 1;
    }

int insert(struct node * leaf,int data){
        leaf->left =(struct node *)malloc(sizeof(node));
        leaf->right =(struct node *)malloc(sizeof(node));
        struct node *temp = leaf;
        temp->right->number=12;
        temp->left->number=11;
        temp->right->right=NULL;
        temp->right->left=NULL;
        temp->left->left=NULL;
        temp->left->right=NULL;
        return 1;
    }





  2)

#include<iostream>
using namespace std;
struct node{
    int number;
    struct node *right;
    struct node *left;
}nodeType;

int insert(struct node *,int);

int main(){

    int data[50];
    int i;
    for(i=0;i<50;i++){
     data[i]=rand()%100;
    }

    struct node * root=(struct node *)malloc(sizeof(node));
    root->left=NULL;
    root->right=NULL;

    root->number = 36;
    for(i=0;i<50;i++){
        insert(root,data[i]);
    }
    cout<<root->right->number; //This doesn't work, and it throws some memory error. Though it assigns a value(it is 41) which goes to the right side in the insert function, the root's right side pointer is not able to point into that memory location. Similar case with root->.... also.
    return 1;
}

int insert(struct node * leaf,int data){

    if(leaf==NULL){
        leaf = (struct node *)malloc(sizeof(node));
        leaf->number=data;
        leaf->left=NULL;
        leaf->right=NULL;
    }
    else if(data>=leaf->number){
        insert(leaf->right,data);
    }
    else if (data<leaf->number){
        insert(leaf->left,data);
    }
    else
    {

    }

    return 1;
}

为什么在第二个程序中它不能指向那个位置？

编辑: 我在运行时遇到的错误是:

test.exe 中 0x004114b4 处未处理的异常:0xC0000005:访问 违规读取位置0x000000004。

中断继续忽略

Answer 1

@whozcraig 在克制自己方面做得很有男子气概。我的自制力较弱，所以我将讨论您的代码中您尚未注意到(甚至没有看到症状)的一些问题。

首先，你通常不应该使用 malloc在 C++ 代码中(也不是 struct xxx 来定义结构的实例)。

其次，您在 main 中都有代码和 insert那是真正应该由 node 处理的工作的构造函数(例如，将节点的子指针设置为 NULL)。

第三，在insert您正在测试一个永远不会为假的条件，然后添加一个空的 else永远无法执行(但无论如何什么都不做)。

我将从重写 node 开始看起来像这样:

struct node{
    int number;
    node *right;
    node *left;

    node(int n) : number(n), right(NULL), left(NULL) {}
};

这样，节点的构造函数将其子指针初始化为 NULL，并将所需的值放入节点本身。

这让我们可以大大简化其他代码。例如，insert最终看起来像这样:

void insert(node *&leaf, int data){
    if (leaf == NULL)
        leaf = new node(data);
    else if (data < leaf->number)
        insert(leaf->left, data);
    else
        insert(leaf->right, data);
}

因为这是二叉树，实际上只有三种可能性:1) 没有“当前”节点——在这种情况下，我们在“这里”插入新数据，或者 2) 新数据属于左侧当前节点的，或 3) 它属于当前节点的权利。此代码直接反射(reflect)了三向决策过程。

main 中的相当一部分代码似乎也没有必要。例如，如果我们只想向树中插入一些数字，可以很容易地将代码简化为如下所示:

node *root = NULL;

for (int i = 0; i < 50; i++)
    insert(root, rand() % 100);

不需要先将数据放入数组中——我们可以在生成每个项目时将其直接放入树中。

当然，要查看发生了什么，我们可能不仅要打印出树中的一个特定节点，而且(可能)要打印出所有数据。幸运的是，这也很容易做到:

void show(node *tree) {
    if (tree == NULL)
        return;
    show(tree->left);
    std::cout << "\t" << tree->number;
    show(tree->right);
}

这对树进行了简单的按顺序遍历，打印遍历的每个节点。为避免泄漏您为树创建的内存，您可能想要执行类似的操作来删除树中的节点。主要区别在于，为此您可能想要进行后序遍历(递归删除两个子节点，然后删除当前节点)。

还有一点是，一棵树真的应该是它自己的一个类，有insert。作为一个成员函数(并且可能还有一个 dtor 来破坏一棵树并删除它的所有内容，如果你想要类似上面的 show 的东西，可能是一个重载的 operator<< 来做到这一点，等等)