0

这是一个二叉搜索树的实现，我不知道为什么我的 min 方法（用于查找树中的最小元素）没有返回正确的答案，而是一个任意的内存地址。我正在通过这个构造函数 BST(3); 创建一棵树，现在我运行 min()，它正确返回 3，但是在插入 1(insert(1) 方法)后，min() 返回一些十六进制地址。

class node{
    public:
    int key;
    node *left;
    node *right;
    node *parent;
};
class BST{
    node *root;
    public:
    BST(){}
    BST(int a){
        root=new node();
        root->left=NULL;
        root->right=NULL;
        root->parent=NULL;
        root->key=a;
    }
    void insert(int n)
    {
       if(search(n))return;
       node *p=root;
       node *m=new node;
       m->key=n;
       m->left=NULL;
       m->right=NULL;

    while(1)
    {
        if(p->key > n)
        {
            //look left
            if(p->left==NULL)
            {
                p->left=m;
                m->parent=p;
                return;
            }
            else
                p=p->left;



        }
        else
        {
            //look right
            if(p->right==NULL)
            {
                p->right=m;
                m->parent=p;
                return;
            }
            else
                p=p->right;

        }
    }
}
bool search(int n)
{
    node *p=root;
    while(1)
    {
        if(p->key > n)
        {
            //look left
            if(p->left==NULL)
                return false;

            else
                p=p->left;



        }
        else if(p->key==n)return true;
        else
        {
            //look right
            if(p->right==NULL)
                return false;

            else
                p=p->right;

        }
    }

}
int min()
{
    node *p=root;
    if(p->left == NULL)
    return (p->key);
    p=p->left;
}
};
4

2 回答 2

2

因为您通过不返回所有控制路径而遇到未定义的行为：

int min()
{
    node *p=root;
    if(p->left == NULL)
        return (p->key);
    p=p->left;
    //no return here
}

这意味着如果p->left不是NULL，任何事情都可能发生。任何事物！

看起来你想要一个循环：

int min()
{
    node *p=root;
    while (p->left != NULL)
        p=p->left;
    return (p->key);
}
于 2012-07-25T17:13:37.023 回答
0

如果p->left != NULL，则不返回任何内容。

于 2012-07-25T17:13:51.773 回答