Próbuję wykonać funkcję balance_bst (root bstNode), ale walczę z implementacją.

Implementuję funkcję jako funkcję szablonu, ponieważ moja klasa bstNode jest klasą szablonów.

Oto (niektóre) mój kod:

<code>template<class Item, class  Key>
class bstNode{
public:
    //Constructor
    bstNode(const Item& init_data = Item(), const Key& init_key = Key(), bstNode<Item, Key>* l_child = NULL, bstNode<Item, Key>* r_child = NULL){
        data_field = init_data;
        key_field = init_key;
        l_ptr = l_child;
        r_ptr = r_child;
    }
    //Destructor
    ~bstNode(){
        data_field = 0;
        key_field = 0;
        l_ptr = r_ptr = NULL;
    }
    //Basic Member Functions
    bstNode<Item, Key>*& left( )   {                    return l_ptr;       }           //returns left child pointer by reference
    bstNode<Item, Key>*& right( )  {                    return r_ptr;       }           //returns right child pointer by reference
    bstNode<Item, Key>* left( ) const   {               return l_ptr;       }       //returns left child pointer by reference
    bstNode<Item, Key>* right( ) const  {               return r_ptr;       }       //returns right child pointer by reference
    const Item& data() const{                           return data_field;  }           //returns reference to data_field
    const Key& key()const {                             return key_field;   }
    Item& data() {                                      return data_field;  }           //returns reference to data_field
    Key& key() {                                        return key_field;   }
    void set_data(const Item& new_data){            data_field = new_data;      }       //sets data_field to new_data
    void set_key(const Key& new_key){               key_field = new_key;        }       //sets key_field to new_key
    void set_left(bstNode* new_left){               l_ptr = new_left;           }       //sets left child pointer to new_left
    void set_right(bstNode* new_right){             r_ptr = new_right;          }       //sets right child pointer to new_right

private:
    bstNode<Item, Key>  *l_ptr,     //pointer to left child node 
                        *r_ptr;     //pointer to right child node
    Item    data_field;
    Key     key_field;
};

template<class Item, class Key>
void balance_bst(bstNode<Item, Key>*& root){                //unfinished

    std::vector< bstNode<Item, Key>* > nodes;
    sorter(root, nodes);
    size_t i = nodes.size()/2;                      //size() divided by 2 will yield
                                                    //index of middle element of vector for 
                                                    //odd-isized arrays and the greater of the 
                                                    //middle two elements for an even-sized array

    while(i>=0){
        root->set_key(nodes[i]->key());                             
        root->set_data(nodes[i]->data());
         //.....MORE CODE HERE: recursive call??

    }


}

template<class Item, class Key>
void sorter(bstNode<Item, Key>*& root, std::vector<bstNode<Item, Key>* >& tree_nodes){
    if(root == NULL)
        return;
    sorter(root->left(), tree_nodes);
    tree_nodes.push_back(root);
    sorter(root->right(), tree_nodes); 
}
</code>

Zagubiłem się w rzeczywistej funkcji balance_bst i myślę, że rekurencja jest oczywistym rozwiązaniem, ale nie mogę się oprzeć tej głowie ...

sorter zasadniczo wstawia elementy BST do wektora przy użyciu algorytmu przetwarzania inorder. Tak długo, jak „root” jest wskaźnikiem do katalogu głównego drzewa wyszukiwania binarnego (tj. Wszystkie wartości klucza lewego poddrzewa są niższe niż kluczowa wartość węzłów, a wszystkie kluczowe wartości prawego poddrzewa węzła są większe niż węzły), wtedy węzły wstawione do wektora będą sortować w sposób rosnący.

Następnie, aby utworzyć zbalansowane drzewo, wstawiam węzeł w środku wektora w katalogu głównym drzewa, a następnie powinienem móc rekursywnie wstawiać lewy i prawy węzeł potomny, które byłyby wtedy w środku lewej połowy wektora i środka prawej połowy wektora.

Uwaga: Rozumiem, że jest to podział na liczby całkowite i powiedzmy 7/2 = 3, który byłby indeksem środkowego elementu tablicy o rozmiarze 7. A dla macierzy o równych rozmiarach algorytm wdrożony powyżej znajdzie indeks większego z dwóch elementów w środku wektora.

W każdym razie wszelkie sugestie lub uwagi są mile widziane i zachęcane! Z góry dziękuję.

Edycja: Pytam, w jaki sposób zaimplementować funkcję równoważącą drzewo wyszukiwania binarnego? (Zrównoważony BST to taki, który ma minimalną głębokość, jaką może podać liczba węzłów).