c++ - 我的 min 方法(二叉搜索树)有什么问题？

Question

这是一个二叉搜索树实现，我不明白为什么我的 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;
}
};

Answer 1

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

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);
}