製作二進制搜索樹到模板中

所以，我製作了一個二叉搜索樹，但現在我被卡住了，因爲我必須將它製作成模板，但我對模板的瞭解卻相當有限，如果有人可以，我會很感激，如果他們能夠「勺送」我如何將樹轉換成可用於任何數值數據的樹，請提前致謝！製作二進制搜索樹到模板中

Main.cpp的

#include <iostream> 
#include "bst.h" 

using namespace std; 


int main() 
{ 
    BST tree; 
    tree.insert(8); 
    tree.insert(25); 
    tree.insert(99); 
    tree.insert(20); 
    tree.insert(25); 
    tree.insert(20); 
    tree.insert(2); 
    tree.insert(89); 
    tree.insert(15); 
    tree.insert(10); 
    tree.insert(30); 
    tree.insert(50); 
    tree.displayorder(); 



    int number; 

    int Inputnumber; 
    while (true){ 
     cout << "Choose what you want to do: " << endl << "1# Insert" << endl << "2# Display Orders" << endl << "3# Search" << endl << "4# Delete" << endl << endl << endl; 
     cin >> Inputnumber; 
     if (Inputnumber==1){ 
      cout << endl << "Enter the number you want inserted: "; 
      cin >> number; 
      tree.insert(number); 
      cout << endl << endl << endl; 
     } 
     if (Inputnumber==2){ 
      cout<<"Display Orders: " << endl; 
      tree.displayorder(); 
      cout << endl << endl << endl; 
     } 

     if (Inputnumber==3){ 
      cout<<"Enter the number you want to search for: "; 
      cin >> number; 
      tree.search(number); 
      cout << endl << endl << endl; 
     } 
     if (Inputnumber==4){ 
      cout << "Enter the number you want to remove: "; 
      cin >> number; 
      tree.remove(number); 
      cout << endl << endl << endl; 
     } 
    } 
}

Bst.cpp

#include <iostream> 
#include "bst.h" 

using namespace std; 

BST::node* BST::makeEmpty(node* tree) 
{ 
    if(tree == NULL) 
     return NULL; 
    { 
     makeEmpty(tree->left); 
     makeEmpty(tree->right); 
     delete tree; 
    } 
    return NULL; 
} 

BST::node* BST::insert(int x, node* tree) 
{ 
    if(tree == NULL) 
    { 
     tree = new node; 
     tree->data = x; 
     tree->left = tree->right = NULL; 
    } 
    else if(x < tree->data) 
     tree->left = insert(x, tree->left); 
    else if(x >= tree->data) 
     tree->right = insert(x, tree->right); 
    return tree; 
} 

BST::node* BST::findMin(node* tree) 
{ 
    if(tree == NULL) 
     return NULL; 
    else if(tree->left == NULL) 
     return tree; 
    else 
     return findMin(tree->left); 
} 

BST::node* BST::findMax(node* tree) 
{ 
    if(tree == NULL) 
     return NULL; 
    else if(tree->right == NULL) 
     return tree; 
    else 
     return findMax(tree->right); 
} 

BST::node* BST::remove(int x, node* tree) 
{ 
    node* temp; 
    if(tree == NULL) 
     return NULL; 
    else if(x < tree->data) 
     tree->left = remove(x, tree->left); 
    else if(x > tree->data) 
     tree->right = remove(x, tree->right); 
    else if(tree->left && tree->right) 
    { 
     temp = findMin(tree->right); 
     tree->data = temp->data; 
     tree->right = remove(tree->data, tree->right); 
    } 
    else 
    { 
     temp = tree; 
     if(tree->left == NULL) 
      tree = tree->right; 
     else if(tree->right == NULL) 
      tree = tree->left; 
     delete temp; 
    } 

    return tree; 
} 

void BST::inorder(node* tree) 
{ 
    if(tree == NULL){ 
     return; 
    } 
    inorder(tree->left); 
    cout << tree->data << " "; 
    inorder(tree->right); 
} 

void BST::preorder(node* tree) 
{ 
    if(tree == NULL){ 
     return; 
    } 
    cout << tree->data << " "; 
    inorder(tree->left); 
    inorder(tree->right); 
} 



void BST::postorder(node* tree) 
{ 
    if(tree == NULL){ 
     return; 
    } 
    inorder(tree->left); 
    inorder(tree->right); 
    cout << tree->data << " "; 
} 

BST::node* BST::find(node* tree, int x) 
{ 
    if(tree == NULL) 
     return NULL; 
    else if(x < tree->data) 
     return find(tree->left, x); 
    else if(x > tree->data) 
     return find(tree->right, x); 
    else 
     return tree; 
} 

BST::BST() 
{ 
    root = NULL; 
} 

BST::~BST() 
{ 
    root = makeEmpty(root); 
} 

void BST::insert(int x) 
{ 
    root = insert(x, root); 
} 

void BST::remove(int x) 
{ 
    root = remove(x, root); 
} 

void BST::displayorder() 
{ 
    inorder(root); 
    cout << endl; 
    preorder(root); 
    cout << endl; 
    postorder(root); 
    cout << endl << endl; 
} 

void BST::search(int x) 
{ 
    if(root = find(root, x)){ 
     cout << endl << "Found!" << endl; 
    } 
    else{ 
     cout << endl << "Not Found!" << endl; 
    } 
}

Bst.h

#ifndef BST_H 
#define BST_H 



class BST 
{ 
    struct node 
    { 
     int data; 
     node* left; 
     node* right; 
    }; 

    node* root; 

    node* makeEmpty(node* tree); 

    node* insert(int x, node* tree); 

    node* findMin(node* tree); 

    node* findMax(node* tree); 

    node* remove(int x, node* tree); 

    void inorder(node* tree); 

    void preorder(node* tree); 



    void postorder(node* tree); 



public: 
    BST(); 

    ~BST(); 


    node* find(node* tree, int x); 

    void insert(int x); 

    void remove(int x); 

    void displayorder(); 

    void search(int x); 
}; 

#endif // BST_H

來源

2017-10-04 Håkon Ness

這裏有什麼問題？ – scohe001

不可以。這個網站嚴重違反* spoonfeeding *。找出問題出在哪裏，提供[MCVE]（https://stackoverflow.com/help/mcve）並提出一個很好的問題 – Fureeish

過於簡單：用「value_type」替換「int」並將「template 」替換爲在一切前面。您現在可以製作BST 的實例。把所有東西都放在bst.h裏。祝你好運:) –

你可以做到這一點通過採用t他以下變化：

在你BST.h文件中添加類decleration上面以下內容：

template < typename T > 
class BST { 
    [...] 
}

然後，方法的foreach定義，將其更改爲：

template < typename T > 
typename BST<T>::node* BST<T>::makeEmpty(BST<T>::node* tree) 
{ 
    if(tree == NULL) 
     return NULL; 
    { 
     makeEmpty(tree->left); 
     makeEmpty(tree->right); 
     delete tree; 
    } 
    return NULL; 
}

然後，搜索並在BST.h和BST.cpp中用T代替int。

然後在您的main.cpp將變量更改爲BST<int> tree。

結果應該是這樣的：

#include <iostream> 

using namespace std; 

template < typename T > 
class BST 
{ 
    struct node 
    { 
     T data; 
     node* left; 
     node* right; 
    }; 

    node* root; 

    node* makeEmpty(node* tree); 

    node* insert(T x, node* tree); 

    node* findMin(node* tree); 

    node* findMax(node* tree); 

    node* remove(T x, node* tree); 

    void inorder(node* tree); 

    void preorder(node* tree); 



    void postorder(node* tree); 



public: 
    BST(); 

    ~BST(); 


    node* find(node* tree, T x); 

    void insert(T x); 

    void remove(T x); 

    void displayorder(); 

    void search(T x); 
}; 

template < typename T > 
typename BST<T>::node* BST<T>::makeEmpty(BST<T>::node* tree) 
{ 
    if(tree == NULL) 
     return NULL; 
    { 
     makeEmpty(tree->left); 
     makeEmpty(tree->right); 
     delete tree; 
    } 
    return NULL; 
} 

template < typename T > 
typename BST<T>::node* BST<T>::insert(T x, BST<T>::node* tree) 
{ 
    if(tree == NULL) 
    { 
     tree = new node; 
     tree->data = x; 
     tree->left = tree->right = NULL; 
    } 
    else if(x < tree->data) 
     tree->left = insert(x, tree->left); 
    else if(x >= tree->data) 
     tree->right = insert(x, tree->right); 
    return tree; 
} 

template < typename T > 
typename BST<T>::node* BST<T>::findMin(BST<T>::node* tree) 
{ 
    if(tree == NULL) 
     return NULL; 
    else if(tree->left == NULL) 
     return tree; 
    else 
     return findMin(tree->left); 
} 

template < typename T > 
typename BST<T>::node* BST<T>::findMax(BST<T>::node* tree) 
{ 
    if(tree == NULL) 
     return NULL; 
    else if(tree->right == NULL) 
     return tree; 
    else 
     return findMax(tree->right); 
} 

template < typename T > 
typename BST<T>::node* BST<T>::remove(T x, BST<T>::node* tree) 
{ 
    node* temp; 
    if(tree == NULL) 
     return NULL; 
    else if(x < tree->data) 
     tree->left = remove(x, tree->left); 
    else if(x > tree->data) 
     tree->right = remove(x, tree->right); 
    else if(tree->left && tree->right) 
    { 
     temp = findMin(tree->right); 
     tree->data = temp->data; 
     tree->right = remove(tree->data, tree->right); 
    } 
    else 
    { 
     temp = tree; 
     if(tree->left == NULL) 
      tree = tree->right; 
     else if(tree->right == NULL) 
      tree = tree->left; 
     delete temp; 
    } 

    return tree; 
} 

template < typename T > 
void BST<T>::inorder(BST<T>::node* tree) 
{ 
    if(tree == NULL){ 
     return; 
    } 
    inorder(tree->left); 
    cout << tree->data << " "; 
    inorder(tree->right); 
} 

template < typename T > 
void BST<T>::preorder(BST<T>::node* tree) 
{ 
    if(tree == NULL){ 
     return; 
    } 
    cout << tree->data << " "; 
    inorder(tree->left); 
    inorder(tree->right); 
} 


template < typename T > 
void BST<T>::postorder(BST<T>::node* tree) 
{ 
    if(tree == NULL){ 
     return; 
    } 
    inorder(tree->left); 
    inorder(tree->right); 
    cout << tree->data << " "; 
} 

template < typename T > 
typename BST<T>::node* BST<T>::find(BST<T>::node* tree, T x) 
{ 
    if(tree == NULL) 
     return NULL; 
    else if(x < tree->data) 
     return find(tree->left, x); 
    else if(x > tree->data) 
     return find(tree->right, x); 
    else 
     return tree; 
} 

template < typename T > 
BST<T>::BST() 
{ 
    root = NULL; 
} 

template < typename T > 
BST<T>::~BST() 
{ 
    root = makeEmpty(root); 
} 

template < typename T > 
void BST<T>::insert(T x) 
{ 
    root = insert(x, root); 
} 

template < typename T > 
void BST<T>::remove(T x) 
{ 
    root = remove(x, root); 
} 

template < typename T > 
void BST<T>::displayorder() 
{ 
    inorder(root); 
    cout << endl; 
    preorder(root); 
    cout << endl; 
    postorder(root); 
    cout << endl << endl; 
} 

template < typename T > 
void BST<T>::search(T x) 
{ 
    if(root = find(root, x)){ 
     cout << endl << "Found!" << endl; 
    } 
    else{ 
     cout << endl << "Not Found!" << endl; 
    } 
} 

int main() 
{ 
    BST<int> tree; 
    tree.insert(8); 
    tree.insert(25); 
    tree.insert(99); 
    tree.insert(20); 
    tree.insert(25); 
    tree.insert(20); 
    tree.insert(2); 
    tree.insert(89); 
    tree.insert(15); 
    tree.insert(10); 
    tree.insert(30); 
    tree.insert(50); 
    tree.displayorder(); 



    int number; 

    int Inputnumber; 
    while (true){ 
     cout << "Choose what you want to do: " << endl << "1# Insert" << endl << "2# Display Orders" << endl << "3# Search" << endl << "4# Delete" << endl << endl << endl; 
     cin >> Inputnumber; 
     if (Inputnumber==1){ 
      cout << endl << "Enter the number you want inserted: "; 
      cin >> number; 
      tree.insert(number); 
      cout << endl << endl << endl; 
     } 
     if (Inputnumber==2){ 
      cout<<"Display Orders: " << endl; 
      tree.displayorder(); 
      cout << endl << endl << endl; 
     } 

     if (Inputnumber==3){ 
      cout<<"Enter the number you want to search for: "; 
      cin >> number; 
      tree.search(number); 
      cout << endl << endl << endl; 
     } 
     if (Inputnumber==4){ 
      cout << "Enter the number you want to remove: "; 
      cin >> number; 
      tree.remove(number); 
      cout << endl << endl << endl; 
     } 
    } 
}

來源

2017-10-04 20:57:36 Semyon

儘管這個答案提供的信息很可能是正確的，但我認爲我們**絕不應該**用勺子喂人，特別是當OP直接問我們時。這是一個問答網站，而不是代碼提供者。這種行爲導致越來越多的人來到這裏，並要求提供代碼 – Fureeish

@Fureeish，感謝您的建議，我會記住下次。 – Semyon

製作二進制搜索樹到模板中

回答

相關問題