按位置搜索，二叉樹C++

我一直在掙扎在二叉樹中做我的遞歸函數，我試圖做一個函數，要求一個位置，然後它返回的值是在那個位置，我花了很多次在代碼上進行更改，大部分時間都只是死掉。所以如果有人知道我做錯了什麼，我會很感激，非常感謝。按位置搜索，二叉樹C++

struct node 
{ 
    int info; 
    struct node *left; 
    struct node *right; 
}*root; 

class BST 
{ 
    public: 
     void find(int, node **, node **); 
     void insert(node *tree, node *newnode); 
     void del(int); 
     void case_a(node *,node *); 
     void case_b(node *,node *); 
     void case_c(node *,node *); 
     void preorder(node *); 
     void inorder(node *); 
     void postorder(node *); 
     void display(node *, int); 
     void recupera(int pos); 
     int countNodes(node *); 
     int busquedaPos(node *ptr,int c,int pos); 
     BST() 
     { 
      root = NULL; 
     } 
}; 


    int BST::busquedaPos(node *ptr,int c, int pos) 
{ 
    while(c != pos+1){ 
     busquedaPos(ptr->left,c+1,pos); 
     busquedaPos(ptr->right,c+1,pos); 
    } 
    return ptr->info; 
} 

void BST::recupera(int pos) 
{ 
    int y = 1; 
    if(root == NULL) 
    { 
     cout<<"\tEmpty tree."<<endl; 
    } 
    else if (pos==1){ 
     cout<<"Your position is the root, so the value is: "<<root->info<<". "<<endl; 
    } 
    else if(pos>1 && pos <= (countNodes(root))) 
    { 
     bool found = false; 
     while(y != pos && found != true){ 
       cout<<"ok"<<endl; 
      int plz = busquedaPos(root,y,pos); 
     cout<<"ok2"<<endl; 
      cout<<"Your value is: "<< plz <<endl; 
       found = true; 
      } 
    } 
    else if(pos > (countNodes(root)) or pos<0){ 
     cout<<"\tError: The position that you are trying to use is invalid."<<endl; 
     cout<<"\tThe list only have '"<<countNodes(root)<<"' elements. Try with one that is on range."<<endl; 
    } 
}

來源

2017-05-12 Abril Barrera

添加一個非常短的main（），它在硬編碼的測試數據上運行該函數。這將允許您發佈預期的和實際的輸出。這也可以讓你自己運行它，從而捕獲和修復代碼中的拼寫錯誤，所以你的文章是有效的C++ :)「或」應該是||「。 –

什麼是pos？它在向量中是有意義的，每個值都有一個特定的索引。它在樹上沒有多少意義。有一些方法可以將樹存儲在一個向量中（請參閱priority_queue），但它們會添加額外的重新平衡工作以使樹適合，並且您已經有了一個根節點，所以...樹中的位置索引可以表示什麼？ –

額外的評論：樹類不應該做IO。 recupera應該像你說的那樣返回一個int，而不是打印。只要稍後擺脫它們，就可以進行調試打印，但實際的調試器會更好。 –

首先，我會在BST類中放入一個用於存儲根的數據成員。

然後我會重新定義你的busquedaPos()方法的一些如：

void BST::busquedaPos(node * root, node *& found_node, 
        size_t & curr_pos, size_t pos) 
    { 
    if (root == nullptr) 
     return; 

    if (curr_pos == pos) // Is current root at the inorder position pos? 
     { 
     found_node = root; 
     return; 
     } 

    ++curr_pos; 
    busquedaPos(root->left, found_node, curr_pos, pos); 
    ++curr_pos; 
    busquedaPos(root->right, found_node, curr_pos, pos); 
    }

然後你的類方法將使用（我想你設計）這個靜態方法。例如，recupera()可以由此實現：

int BST::recupera(size_t pos) 
{ 
    node * found_node = nullptr; 
    size_t curr_pos = 0; 
    busquedaPos(root, found_node, curr_pos, pos); 
    if (found_node != nullptr) 
    return found_node->info; 

    throw std::out_of_range("Position " + to_string(pos) + 
       " greater or equal to number of nodes"); 
}

注意，我爲了避免驗證負位置（其將不被定義）改變int類型位置size_t。另外，recupera()的返回值是在序列位置檢索到的密鑰pos

來源

2017-05-12 17:20:15 lrleon

按位置搜索，二叉樹C++

回答

相關問題