Eu estou tentando fazer uma função balance_bst (bstNode root), mas estou lutando com a implementação.

Estou implementando a função como uma função de modelo, já que minha classe bstNode é uma classe de modelo.

Aqui está (alguns de) meu código:

<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>

Eu tenho mexido com a função balance_bst, e acho que a recursão é a solução óbvia, mas eu não consigo envolver minha cabeça nessa ...

classificador basicamente insere os elementos de um BST em um vetor usando um algoritmo de processamento dentro da ordem. Portanto, desde que "root" seja um ponteiro para a raiz de uma árvore de pesquisa binária (ou seja, todos os valores de chave de uma subárvore esquerda de nós são menores que o valor de chave dos nós e todos os valores de chave da subárvore direita são maiores que nós) então os nós inseridos no vetor serão classificados de maneira ascendente.

Em seguida, para criar uma árvore balanceada, insiro o nó no centro do vetor na raiz da árvore e, em seguida, devo inserir recursivamente os nós filhos direito e esquerdo, que então estarão no meio da metade esquerda. do vetor e meio da metade direita do vetor.

Nota: Eu entendo que isso está usando a divisão de inteiros e que diz, 7/2 = 3, que seria o índice do elemento do meio de uma matriz de tamanho 7. E para matrizes de tamanho uniforme, o algoritmo implementado acima encontrará o índice do maior dos dois elementos no meio do vetor.

De qualquer forma, quaisquer sugestões ou observações são bem-vindas e incentivadas! Desde já, obrigado.

Edit: O que estou perguntando é como eu implementar uma função para equilibrar uma árvore de pesquisa binária? (Um BST balanceado é aquele que tem a profundidade mínima que pode receber o número de nós.)