我最小法（二叉搜索樹）有什麼問題？

這是一個二叉搜索樹的實現，我不知道爲什麼我的最小方法（用於查找樹中的最小元素）沒有返回正確的答案，而是一個任意的內存地址。我正在通過這個構造函數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

我最小法（二叉搜索樹）有什麼問題？

回答

相關問題