Rekurencyjne drzewo wyszukiwania binarnego x = zmień (x)

Question

Oto zdjęcie tego, co mój kod musi zrobić.

Before Call: 
      +----+ 
      | -9 | 
      +----+ 
     / \ 
     /  \ 
     +----+  +----+ 
     | 3 |  | 15 | 
     +----+  +----+ 
    /  / \ 
    /  /  \ 
+----+  +----+  +----+ 
| 0 |  | 12 |  | 24 | 
+----+  +----+  +----+ 
     / \ 
     /  \ 
     +----+  +----+ 
     | 6 |  | -3 | 
     +----+  +----+ 

After Call: 
      +----+ 
      | -9 | 
      +----+ 
     / \ 
     /  \ 
     +----+  +----+ 
     | 6 |  | 30 | 
     +----+  +----+ 
    /  / \ 
    /  /  \ 
+----+  +----+  +----+ 
| 0 |  | 24 |  | 48 | 
+----+  +----+  +----+ 
     / \ 
     /  \ 
     +----+  +----+ 
     | 12 |  | -3 | 
     +----+  +----+ 

Zasadniczo ten problem wymaga podwojenia wszystkich wartości danych większych niż 0 w drzewie binarnym liczb całkowitych. Mój kod poniżej robi to dla kilku wartości, ale zatrzymuje się wcześniej. Nie jestem pewien, jak to naprawić rekursywnie. Tak wygląda moje wyjście dla drzewa podanego powyżej.

 overallRoot 
     _[-9]_______________ 
     /     \ 
    _[6]     _____[30] 
/    /  \ 
[0]    _[12]   [24] 
       / \ 
       [6]  [-3] 
public void doublePositives() { 
    doublePositives(overallRoot); 
} 

private IntTreeNode doublePositives(IntTreeNode root) { 
    if(root != null) { 
     if(root.data > 0) { 
      root.data = 2* root.data; 
     }else { 
      root.left = doublePositives(root.left); 
      root.right= doublePositives(root.right); 
     } 
    } 
    return root; 
} 

Answer 1

Musisz jeszcze przejść przez drzewo, jeśli podwajasz węzeł. Upuść else, abyś zawsze przechodził. Ponadto, usunęliśmy przypisania, ponieważ nie zmieniają strukturę drzewa:

if(root != null) { 
    if(root.data > 0) { 
     root.data = 2 * root.data; 
    } 
    doublePositives(root.left); 
    doublePositives(root.right); 
} 

Answer 2

Nie wykonujesz wywołań rekurencyjnych, gdy korzeń jest dodatni.

Wykonuje się tylko wywołania rekursywne, gdy root jest ujemny. Aby to naprawić, po prostu usuń pozostałe.

private IntTreeNode doublePositives(IntTreeNode root) { 
    if(root != null) { 
     if(root.data > 0) { 
      root.data = 2* root.data; 
     } 
     root.left = doublePositives(root.left); 
     root.right= doublePositives(root.right); 
    } 
    return root; 
} 

Answer 3

wygląda problem logiczny - będziesz tylko podwójne wartości dzieci negatywnych węzłów:

if(root.data > 0) { 
     root.data = 2* root.data; 
    }else { 
     root.left = doublePositives(root.left); 
     root.right= doublePositives(root.right); 
    } 

Jeśli wartość root jest dodatnia - nigdy nie dostaniesz root.left & root.right. Coś takiego byłoby lepiej:

if(root.data > 0) { 
     root.data = 2* root.data; 
    } 
    root.left = doublePositives(root.left); 
    root.right= doublePositives(root.right); 

Answer 4

Spróbuj tego: robili błąd w instrukcji warunkowej. To powinno być napisane w ten sposób. Jeśli root ma dane są pozytywne - spraw, żeby były podwójne, to roger! i na zewnątrz! W następnym kroku przejdź do lewego i prawego węzła podrzędnego.

Dodatkowo zanotuj to, nie musisz zwracać niczego (innego niż puste) w funkcji rekursywnej doublePositives().

public void iWillDoit() { 
     doublePositives(Root); 
    } 

    private void doublePositives(IntTreeNode root) { 
     if(root != null) { 
      if(root.data > 0) 
      { 
       root.data = 2* root.data; 
      } 
      doublePositives(root.left); 
      doublePositives(root.right);  
     } 
    }