Эта проблема в основном из-за того, что я не понимаю, как нормально
рекурсивный метод слова, хотя при взгляде на них рядом
Посмотрите, как к нему подойти, я всегда зацикливаюсь на том, что делать.
Требуется практика ... и, возможно, обзор работы других людей.
требуется два стека (для содержания left_Index и right_Index).
Мои извинения, я не понимаю, почему ОП так думает. В моей демонстрации ниже есть только один стек под названием «todo», возможно, вы найдете эту идею полезной.
#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <vector>
#include <cassert>
#include "./BTree.hh" // code not provided, used in this MCVE to
// conveniently provide "showTallTreeView()"
typedef std::vector<int> IVec_t;
class T607_t
{
IVec_t m_sortedIVec; // sorted - created with for loop
IVec_t m_recursiveIVec; // extract from sorted by recursion
IVec_t m_iterativeIVec; // extract from sorted by iteration
public:
T607_t() = default;
~T607_t() = default;
int exec(int , char** )
{
fillShowSortedIVec();
fillShowRecursiveIVec();
fillShowIterativeIVec();
showResults();
return 0;
}
private: // methods
Векторы находятся в классе T607_t, так что каждый из них доступен для любой функции-члена.
Для этого MCVE я просто создаю "IVec_t m_sortedIVec;" и заполните простой цикл for:
void fillShowSortedIVec()
{
for (int i=0; i<15; ++i)
m_sortedIVec.push_back (i*100); // create in sorted order
showIVec(m_sortedIVec, "\n m_sortedIVec :");
}
Далее (в этом MCVE) - рекурсивное заполнение и показ, и моя адаптация рекурсивного метода OP для получения последовательности рекурсивной вставки:
// ///////////////////////////////////////////////////////////////
void fillShowRecursiveIVec()
{
assert(m_sortedIVec.size() > 0);
int max = static_cast<int>(m_sortedIVec.size()) - 1;
// use OP's recursive insert
array2balancedR (m_sortedIVec, 0, max);
// NOTE - 'sequence' is inserted to 'm_recursiveIVec'
// instead of into tree the op did not share
showIVec(m_recursiveIVec, "\n m_recursiveIVec:");
}
// recursive extract from: m_sortedIVec to: m_recursiveIVec
// my adaptation of OP's recursive method
void array2balancedR(IVec_t& array, int lIndex, int rIndex)
{
//base case
if(lIndex > rIndex)
{
return;
}
else //recursive calls
{
int mid = (lIndex+rIndex)/2;
m_recursiveIVec.push_back(array[mid]); // does this
// tree.insert(array[mid]); // instead of this
array2balancedR(array, lIndex, mid-1); // recurse left
array2balancedR(array, mid+1, rIndex); // recurse right
}
}
Примечание: я оставил "IVec_t & array" в качестве параметра этой функции, потому что он есть в коде OP. В этой оболочке 'class' функция не должна передавать массив 'через рекурсию', потому что каждый метод имеет доступ к данным экземпляра.
Далее (в этом MCVE) действие заполнения и показа с использованием одного возможного итеративного подхода. Я тщательно разработал этот итеративный подход, чтобы соответствовать рекурсивным усилиям ОП.
Сначала я добавил «инструмент» (IndxRng_t), чтобы упростить захват итераций в стеке для последующей обработки. (то есть "todo").
// //////////////////////////////////////////////////////////////
// iterative extract from m_sortedIVec to: m_iterativeIVec
class IndxRng_t // tool to simplify iteration
{
public:
IndxRng_t() = delete; // no default
IndxRng_t(int li, int ri)
: lIndx (li)
, rIndx (ri)
{}
~IndxRng_t() = default;
// get'er and set'er free. also glutton free. gmo free.
bool done() { return (lIndx > rIndx); } // range used up
int mid() { return ((lIndx + rIndx) / 2); } // compute
IndxRng_t left(int m) { return {lIndx, m-1}; } // ctor
IndxRng_t right(int m) { return {m+1, rIndx}; } // ctor
private:
int lIndx;
int rIndx;
};
void fillShowIterativeIVec()
{
assert(m_sortedIVec.size() > 0);
int max = static_cast<int>(m_sortedIVec.size()) - 1;
array2balancedI(m_sortedIVec, 0, max);
// 'sequence' inserted to 'm_iterativeIVec'
showIVec(m_iterativeIVec, "\n m_iterativeIVec:");
}
void array2balancedI(IVec_t& array, int lIndex, int rIndex)
{
std::vector<IndxRng_t> todo;
todo.push_back({lIndex, rIndex}); // load the first range
// iterative loop (No recursion)
do
{
if (0 == todo.size()) break; // exit constraint
// no more ranges to extract mid from
// fetch something to do
IndxRng_t todoRng = todo.back();
todo.pop_back(); // and remove from the todo list
if(todoRng.done()) continue; // lIndex > rIndex
int mid = todoRng.mid();
m_iterativeIVec.push_back(array[mid]); // do this
// tree.insert(array[mid]); // instead of this
todo.push_back(todoRng.right(mid) ); // iterate on right
todo.push_back(todoRng.left(mid) ); // iterate on left
}while(1);
}
И этот mcve генерирует отображение результата:
void showResults()
{
assert(m_recursiveIVec.size() == m_sortedIVec.size());
assert(m_iterativeIVec.size() == m_sortedIVec.size());
std::cout << std::endl;
std::stringstream ss; // for btree use only
std::cout << "\n demo:\n create a BTree, "
<< std::flush;
std::cout << "\n Insert IVec_t " << std::endl;
BBT::BTree_t btree(ss);
std::cout << std::flush;
for (size_t i=0; i<m_iterativeIVec.size(); ++i)
btree.insertPL(m_iterativeIVec[i]);
std::cout << "\n iterative result:\n\n"
<< btree.showTallTreeView();
}
void showIVec(IVec_t& ivec, std::string lbl)
{
std::cout << lbl << std::endl;
for (auto it : ivec)
std::cout << std::setw(5) << it << std::flush;
std::cout << std::endl;
}
}; // class T607_t
int main(int argc, char* argv[])
{
T607_t t607;
return t607.exec(argc, argv);
}
Мой вывод (в Ubuntu 17.10, g ++ 7.2.0),
m_sortedIVec :
0 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400
m_recursiveIVec:
700 300 100 0 200 500 400 600 1100 900 800 1000 1300 1200 1400
m_iterativeIVec:
700 300 100 0 200 500 400 600 1100 900 800 1000 1300 1200 1400
demo:
create a BTree,
Insert IVec_t
iterative result:
BTree_t::showTallTreeView(): (balance: 0 sz: 15)
0
100
200
300
400
500
600
700
800
900
1000
1100
1200
1300
1400
-----------------