Neregistrovaný Přihlásit Registrovat

Přidat otázku mezi oblíbenéZasílat nové odpovědi e-mailem Uložení struktury binárního stromu

Dobrý den, mám problém a nevím si už rady.

Jedná se o to, že potřebuju uložit strukturu binárního stromu pomocí EBS. (nějak takto bRoKD5 - omlouvám se za kvalitu mojí kresby :-) )

Jak vypadá uzel (zjednodušeně):

struct uzel {
  const int hodnota;
  std::unique_ptr<uzel> m_leva = nullptr, m_prava = nullptr;
  uzel(const int& Hodnota) : hodnota(Hodnota) {}
};

Zatím to řeším tak, že mám rekurzivní funkci, která do vektoru přidává jednotlivé bajty (pak se převedou nakonec na jednotlivé bity).

void export_ebs(std::unique_ptr<uzel>& podstrom, std::vector<std::uint8_t>& bajty) {
  if (podstrom == nullptr) bajty.emplace(0);
  export_ebs(podstrom->m_leva, bajty);
  bajty.emplace(1);
  export_ebs(podstrom->m_prava, bajty);
}

Bohužel tenhle způsob vynechá neexistující uzly, které jsou hlouběji jak jedna urověn.
Podmínka je, že musí využívat jen existující uzly, a není možné vytvářet uzly prázdné.

Děkuji za jakýkoli nápad.

Předmět Autor Datum
vynechá neexistující uzly co??? Ten rekurzivny sposob je normalny a spravny prechod stromom, nechap… nový
MM.. 11.05.2017 16:02
 MM..
Ano, to je, ale bude to fungovat jen s uzly, které budou existovat, a na jejich potomky s hloubkou (… nový
C2202EA000 11.05.2017 17:05
 C2202EA000
Netusim co riesis ale snazit sa prechadzat vetvy ktore neexistuju neni normalne. Tak si daj do tej r… nový
MM.. 11.05.2017 17:35
 MM..
.. a samozrejme pri volani testovat pointer podstrom na null, ak je null tak do parametra dat null,… nový
MM.. 11.05.2017 17:37
 MM..
void export_ebs(std::unique_ptr<uzel>& podstrom, std::vector<std::uint8_t>& bajty, int hlbka, int ma… nový
MM.. 11.05.2017 17:48
 MM..
Tohle jsem sice použít nemohl, ale navedlo mě to na správnou cestu a už mi všechno funguje. Díky za… poslední
C2202EA000 11.05.2017 21:42
 C2202EA000

Ano, to je, ale bude to fungovat jen s uzly, které budou existovat, a na jejich potomky s hloubkou (RODIC + 1). Ale já potřebuju zachovat kompletně celou strukturu (takže i CELÉ větve stromu, které neexistují, musí být ve výsledku vyjádřené nulami).

Zatím mě napadlo, si dopředu vytvořit vektor o určité velikosti (maximální počet uzlů pro určitou hloubku stromu). Tj.: pro strom s hloubkou 1, bude velikost 1, pro 2 bude 1 + 2 a pro 3 zase 1 + 2 + 4. Pak to můžu pomocí std::fill() zaplnit nulama; ale pořád nevím jak potom zapsat ty jedničky pro existující uzly.

.. a samozrejme pri volani testovat pointer podstrom na null, ak je null tak do parametra dat null, a ne podstrom->m_leva ani podstrom->m_prava, ptz ti to crashne.

P.S. a ak hlbka ma byt dynamicky, tak si najprv prejdi cely strom normalne (len existujuce) a ukladaj si maximalnu dosiahnutu hlbku kamsi.

void export_ebs(std::unique_ptr<uzel>& podstrom, std::vector<std::uint8_t>& bajty, int hlbka, int maxhlbka) {
  if (podstrom == nullptr)
  {
    if(hlbka < maxhlbka) export_ebs(nullptr, bajty, hlbka+1, maxhlbka);
    bajty.emplace(0);
    if(hlbka < maxhlbka) export_ebs(nullptr, bajty, hlbka+1, maxhlbka);
  }
  else
  {
    if(hlbka < maxhlbka) export_ebs(podstrom->m_leva, bajty, hlbka+1, maxhlbka);
    bajty.emplace(1);
    if(hlbka < maxhlbka) export_ebs(podstrom->m_prava, bajty, hlbka+1, maxhlbka);
  }
}

Zpět do poradny Odpovědět na původní otázku Nahoru