我最小法（二叉搜索树）有什么问题？

这是一个二叉搜索树的实现，我不知道为什么我的最小方法（用于查找树中的最小元素）没有返回正确的答案，而是一个任意的内存地址。我正在通过这个构造函数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; 
} 
};

来源

2012-07-25 Jignesh

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

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-25 17:13:37

谢谢你做了这么一个愚蠢的错误...我如何删除dis问题？ – Jignesh 2012-07-25 17:17:04

@ user1343868我认为我的代码比较干净，但这取决于你。 – 2012-07-25 17:18:19

@ user1343868检查[this]（http://meta.stackexchange.com/questions/25088/how-can-i-delete-my-post-on-stack-overflow）是否希望删除您的帖子。 – Deqing 2012-07-26 08:33:34

如果p->left != NULL，你不回任何东西。

来源

2012-07-25 17:13:51 jrad

我最小法（二叉搜索树）有什么问题？

回答

相关问题