在遍歷BST時遇到問題

我開始學習樹並嘗試編寫BST代碼。不幸的是，我無法顯示樹數據。我正在嘗試執行深度優先遍歷。但不知道如何實現它。下面是我的代碼在遍歷BST時遇到問題

#include<iostream> 
using namespace std; 

class node 
{ 
    public: 
    int data; 
    node *left,*right; 
}; 

class btree 
{ 
private: 
node *root; 
public: 
btree(){root=NULL;} 
void insert(int value) 
{node *temp=new node; 
    if(root == NULL) 
     { 
     temp->right=NULL; 
     temp->data=value; 
     temp->left=NULL; 
     root=temp; 
     } 
    else 
     insertHelper(root, value); 
} 

void insertHelper(node* Node, int value) 
{ 
    if(value < Node->data) 
    { 
     if(Node->left == NULL) 
      { 
       Node->left=new node; 
       Node->left->data=value; 
       Node->left->left=NULL; 
       Node->left->right=NULL; 
       } 
     else 
      insertHelper(Node->left, value); 
    } 
    else 
    { 
     if(Node->right== NULL) 
      { 
       Node->right = new node; 
       Node->right->data=value; 
       Node->right->left=NULL; 
       Node->right->right=NULL; 
       } 
     else 
      insertHelper(Node->right, value); 
    } 

} 


void disp() 
{node*tmp=root; 
if(tmp==NULL) 
    cout<<"empty"<<endl; 
else 
    { 
     cout<<tmp->data<<endl; 
     disphelper(tmp); 
    } 
} 

void disphelper(node *tmp) 
{ 


    if(tmp->left!=NULL) 
    { 
     cout<<tmp->left->data<<endl; 
     tmp=tmp->left; 
     disphelper(tmp);} 
    if(tmp->right!=NULL) 
    { 
     cout<<tmp->right->data<<endl; 
     tmp=tmp->right; 
     disphelper(tmp); 
    } 
} 
}; 

int main() 
{ 
    btree binarytree; 
    binarytree.disp(); 
    binarytree.insert(10); 
    binarytree.insert(5); 
    binarytree.insert(30); 
    binarytree.disp(); 
}

輸出

empty 
10 
5

誰能告訴我爲什麼不顯示30？

來源

2013-01-11 curious_coder

使用調試器逐行執行代碼。它會幫助你更快地找到問題，而不是問這裏。 –

修改代碼以

void disphelper(node *tmp) 
{ 
    if(tmp == NULL) 
     return; 
    cout<<tmp->data<<endl; // print data for current node 

    if(tmp->left!=NULL) // traverse left branch 
    { 
     //cout<<tmp->left->data<<endl; 
     //tmp=tmp->left; 
     disphelper(tmp->left);} 
    if(tmp->right!=NULL) // traverse right branch 
    { 
     //cout<<tmp->right->data<<endl; 
     //tmp=tmp->right; 
     disphelper(tmp->right); 
    } 
}

，它應該工作。

void disp() 
{node*tmp=root; 
if(tmp==NULL) 
    cout<<"empty"<<endl; 
else 
    { 
     disphelper(tmp); 
    } 
}

來源

2013-01-11 14:47:53 hmatar

Thanks.It工作。 :)現在我明白了代碼。 –

的原因你沒有得到這裏的任何輸出是在disphelper()您首先檢查左節點是否NULL，然後改變當你遞歸到它。當你遞歸到正確的節點時也是如此。

void disphelper(node *tmp) 
    { 
     if(tmp->left!=NULL) 
     { 
      cout<<tmp->left->data<<endl; 
      //tmp=tmp->left; // Get rid of this. 
      disphelper(tmp->left); // Use this. 
     } 
     if(tmp->right!=NULL) 
     { 
      cout<<tmp->right->data<<endl; 
      //tmp=tmp->right; // Get rid of this 
      disphelper(tmp->right); // Use this. 
     } 
    }

而是改變溫度值，這應該是兩個比較相同的，只是通過左或右節點。

兩個其他的事情。首先，你在這裏像瘋了一樣泄漏內存：在你的insert()中，你每次都會創建一個新對象，但只能在第一次使用它時，每隔一次泄漏它。你的node類應該通過具有刪除兩個節點的析構函數來照顧內存。其次，在你發佈代碼之前，你能不厭其煩地將其格式化以使縮進一致嗎？這不是用來做這件事的痛苦 - 很多編輯會爲你做，或者你可以使用優秀的Astyle。我知道這是一個小問題，但是對於那些閱讀你的代碼的人來說，這很刺激 - 包括，大概是那個會標記你做家庭作業的人！感謝:-)

來源

2013-01-11 14:39:01

謝謝。以前我用while循環，然後切換到遞歸。所以完全忘了刪除'tmp = tmp-> left'和'tmp = tmp-> right'。感謝您也指出了內存泄漏。:) –

在遍歷BST時遇到問題

回答

相關問題