0

以下是我在 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。

中断继续忽略

4

2 回答 2

4

@whozcraig 在克制自己方面做得很好。我的自控力较差，所以我要谈谈你的代码中你还没有注意到（甚至没有看到症状）的一些问题。

首先，您通常不应该malloc在 C++ 代码中使用（struct xxx就此而言，也不应该定义结构的实例）。

其次，您在两者中都有代码，main并且insert正在做真正应该由nodector 处理的工作（例如，将节点的子指针设置为 NULL）。

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

我会首先重写node看起来像这样：

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

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

这样，节点的 ctor 将其子指针初始化为 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) 它属于当前节点的右边。该代码直接反映了三向决策过程。

相当多的代码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<<那个等等）

于 2013-09-03T08:53:39.660 回答
3

第二个插入函数是按值传递节点指针；不是通过引用或地址。因此，对它的修改不会超出功能范围。

改变这个：

int insert(struct node * leaf,int data)

对此：

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

在原型和实现中。

保留所有关于malloc()在 C++ 程序中使用的注释。尽管它很糟糕，但它与您的问题无关。

于 2013-09-03T08:11:13.100 回答