Przepisz kod C w Javie, aby zbudować pełne drzewo binarne

Question

Chcę napisać funkcję do skonstruowania pełnego drzewa binarnego z danej tablicy przedsprzedażnej i postorder. Uważam, że link http://www.geeksforgeeks.org/full-and-complete-binary-tree-from-given-preorder-and-postorder-traversals/ który proponuje następujący kod C:

struct node* constructTreeUtil (int pre[], int post[], int* preIndex, 
          int l, int h, int size) 
{ 
// Base case 
if (*preIndex >= size || l > h) 
    return NULL; 

// The first node in preorder traversal is root. So take the node at 
// preIndex from preorder and make it root, and increment preIndex 
struct node* root = newNode (pre[*preIndex]); 
++*preIndex; 

// If the current subarry has only one element, no need to recur 
if (l == h) 
    return root; 

// Search the next element of pre[] in post[] 
int i; 
for (i = l; i <= h; ++i) 
    if (pre[*preIndex] == post[i]) 
     break; 

// Use the index of element found in postorder to divide postorder array in 
// two parts. Left subtree and right subtree 
if (i <= h) 
{ 
    root->left = constructTreeUtil (pre, post, preIndex, l, i, size); 
    root->right = constructTreeUtil (pre, post, preIndex, i + 1, h, size); 
} 

return root; 
} 

// The main function to construct Full Binary Tree from given preorder and 
// postorder traversals. This function mainly uses constructTreeUtil() 
struct node *constructTree (int pre[], int post[], int size) 
{ 
int preIndex = 0; 
return constructTreeUtil (pre, post, &preIndex, 0, size - 1, size); 
} 

próbowałem przepisać ten kod w Javie. Tu jest mój kodu:

private static TreeNode constructTree(int[] preorder, int[] postorder, Index index, int lowIndex, int highIndex){ 

    // Base case 
    if (index.index >= preorder.length || lowIndex > highIndex){ 
     return null; 
    } 

     // The first node in preorder traversal is root. So take the node at 
     // preIndex from preorder and make it root, and increment preIndex 
    TreeNode root = new TreeNode (preorder[lowIndex]); 
    index.index++; 

     // If the current subarry has only one element, no need to recur 
    if (lowIndex == highIndex){ 
     return root; 
    } 

     // Search the next element of pre[] in post[] 
    int i = 0; 
    for (i = lowIndex; i <= highIndex; ++i) 
     if (preorder[i]== postorder[lowIndex]) 
      break; 

    // Use the index of element found in postorder to divide postorder array in 
    // two parts. Left subtree and right subtree 
     if (i <= highIndex) { 
      root.left = constructTree(preorder, postorder, index, lowIndex, i); 
      root.right = constructTree(preorder, postorder, index, i + 1, highIndex); 
     } 
     return root; 
        } 

    //The main function to construct Full Binary Tree from given preorder and 
    //postorder traversals. This function mainly uses constructTreeUtil() 
public static TreeNode constructTree (int preorder[], int postorder[]) { 
    return constructTree (preorder, postorder, new Index(), 0, preorder.length - 1); 
    } 

Ale mam ciągły pętli węzła głównego (nie przechodzą do innych węzłów, które mają być jego dziecko). Czy możesz mi pomóc, aby zobaczyć, gdzie jest błąd w moim kodzie Java?

Nie jestem pewien, ale myślę, że błąd może pochodzi z tych linii:

int i = 0; 
    for (i = lowIndex; i <= highIndex; ++i) 
     if (preorder[i]== postorder[lowIndex]) 
      break; 

I nie rozumiem bardzo dobrze linie korespondencję w oryginalnym kodzie C. Zwłaszcza w tej części

Answer 1

Oto błędy:

1. Linia if (preorder[i]== postorder[lowIndex]) ma dwa błędy: po pierwsze, aby szukać w przedsprzedaży zamiast w postorder, a drugi używać lowIndex zamiast prendex. Ta linia powinna być:if (preorder[index.index]== postorder[i])
2. Linia TreeNode root = new TreeNode (preorder[lowIndex]); - lowIndex jest ponownie używany zamiast prendeksu. Linia ta powinna być:TreeNode root = new TreeNode (preorder[index.index]);

zwrócić uwagę na fakt, że ten kod będzie działać tylko dla pełne drzewo binarne

Answer 2

Zakładając, że kod napisany w C działa, to wydaje mi się, że dla tej części

// Search the next element of pre[] in post[] 
int i = 0; 
for (i = lowIndex; i <= highIndex; ++i) 
    if (preorder[i]== postorder[lowIndex]) 
     break; 

że chcesz używać tych samych zmiennych, które można wykorzystać w wersji C. W tym przypadku, twój if powinny być

if (preorder[index.index]== postorder[i]) 

Answer 3

Pierwszy dokonać TreeNode w klasie, ponieważ jest to równoważne java od struct

public class TreeNode{ 
    public int val; 
    public TreeNode left; 
    public TreeNode right; 

    public TreeNode(int val){ 
     this.val = val; 
    } 
}  

następnie dokonaj klasa TreeUtil

public class TreeUtil{ 
    private static TreeNode constructTree(int[] preorder, int[] postorder, int index, int lowIndex, int highIndex){ 

     // Base case 
     if (index >= preorder.length || lowIndex > highIndex){ 
      return null; 
     } 

     // The first node in preorder traversal is root. So take the node at 
     // preIndex from preorder and make it root, and increment preIndex 
     TreeNode root = new TreeNode (preorder[index]); 
     index++; 

     // If the current subarry has only one element, no need to recur 
     if (lowIndex == highIndex){ 
      return root; 
     } 

     // Search the next element of pre[] in post[] 
     for (int i = lowIndex; i <= highIndex; i++) 
      if (preorder[index]== postorder[i]){ 
       // Use the index of element found in postorder to divide postorder array in 
       // two parts. Left subtree and right subtree 
       root.left = constructTree(preorder, postorder, index, lowIndex, i); 
       root.right = constructTree(preorder, postorder, index, i + 1, highIndex); 
       break; 
      } 
     } 
     return root; 
    } 

    //The main function to construct Full Binary Tree from given preorder and 
    //postorder traversals. This function mainly uses constructTreeUtil() 
    public static TreeNode constructTree (int preorder[], int postorder[]){ 
     return constructTree (preorder, postorder, 0, 0, preorder.length - 1); 
    } 
} 

Błędy w kodzie były następujące: if (preorder[i]== postorder[lowIndex] i TreeNode root = new TreeNode (preorder[lowIndex]); wymienione przez aviad. Zmieniłem twój kod, abyś był nieco mniej zagmatwany. Korzystanie z indeksu jest świetnym sposobem na zmylenie siebie, szczególnie, że int będzie działało dobrze. Również ++ i inkrementuje przed uruchomieniem pętli i nie jest konwencjonalnie używane w java, a java pozwala zadeklarować zmienne jako część definicji pętli, więc zmieniłem to, by pętla była bardziej tym, czego szukasz.