Matematické Fórum

U toho prvniho problemu by se mi zdalo korektnejsi ty dva posledni radky presounout pred to nulovani, takhle:

if(root->m_L) delBelow(root->m_L, depth - 1);
if(root->m_R) delBelow(root->m_R, depth - 1);
if(depth < 1){
free(root->m_L);
free(root->m_R);
root->m_L = NULL;
root->m_R = NULL;
}

Tak jak to mas, tak ti tam budou zustavat alokovane ty dalsi vetve ve vetsi hloubce jestli se nepletu (Protoze tim ze vynulujes m_L a m_R, tak delBelow se uz nezavola pro ty dalsi).

jj diky to mi dava smysl :) (tvuj prvni prispevek)
A ta trojka myslim ze je to myslene tak ze je to uzel na kterem visi uz jen listy ale ne dalsi uzel, pro to by to snad mnelo byt dobre tusim.

Ano u te petky jsem se preklikl asi. Jinak jsem vdecny za kazdy postrceni k reseni :)

Nebolo by jednoducho prejsť strom do hĺbky trebárs. Zamysli sa, že vtedy vieš kedy prídeš do listu. A jednoducho zo všetkých listov si vybrať ten, ktorý má najmenšiu hodnotu.

Prejsť do hĺbky sa dá jednoducho, rekurzívne (kód je z knihy Algoritmy a programovací techniky):

procedure Pruchod1(U: Uk);
  {pruchod binarnim stromem do hloubky pomoci rekurze.
   U je ukazatel na koren zkoumaneho stromu}
  begin
  if U <> nil then
    begin
    writeln(U^.Info);      {nebo jina akce s uzlem U}
    Pruchod1(U^.L);
    Pruchod1(U^.P)
    end
  end;  {procedure Pruchod1}

Časová zložitosť je O(n), kde n je počet vrcholov.

Mam zadany nesetrideny binarni strom a mam najit nejmensi hodnotu listu a tu z dane funkce vratit.

Ja som pochopil, že ty máš nájsť list ktorý má najmenšiu hodnotu zo všetkých listov, je to tak?

Ak áno, tak potom to nemá nič spoločné s tým, že v akej hĺbke ten list je.

Však si proste dáš nejakú premennú, ktorej priradíš konštantu "nekonečno". A vždy keď narazíš na hodnotu, ktorá je menšia ako hodnota premennej, tak si zapamätáš novú najmenšiu hodnotu. A spravíš to len ak si v liste.

jj to vim s tim jak poznam list a tak i to porovnavani ale dejme tomu ze by dany algoritmus vypadal takhle:

int minLeaf(BNODE *root){
int min = 999;

if(!root){
    return 0;}                                //kontrola jestli je koren
if(root->right || root->left){
               return cntOneChild(root->left) + cntOneChild(root->right);    //projizdeni dalsich uzlu
               }        
    if(!root->right && !root->left){ //najdu list
                  if(root->key < min){//key je dana hodnota listu
min = root->key;
return min;
                          }
                  }    
    }

Nevrati mi to nahodou hodnotu vsech listu, protoze tuto funkci volam vicekrat a kdyz je volana tak promena min bude vzdy znova 999 ?

Tak sem lehce poladil tvoje reseni a ozkousel a funguje, diky za postrkovani :)

int find_min(BNODE * root) {
    int min = sizeof(int); int x=0;
    if (!root->right && !root->left) return root->key;
    else {
    if(root->left && root->right){         
         if(find_min(root->left) < min) min = find_min(root->left);
        if(find_min(root->right) < min) min = find_min(root->right);
}
    if(!root->left && root->right){         
        if(find_min(root->right) < min) min = find_min(root->right);
}
    if(root->left && !root->right){         
         if(find_min(root->left) < min) min = find_min(root->left);
}
    }
    return min;
}