Riscrivere un codice C in Java per costruire un albero binario completo

Question

Desidero scrivere una funzione per costruire un albero binario completo da un determinato array di preorder e postorder. Ho trovato che puntano http://www.geeksforgeeks.org/full-and-complete-binary-tree-from-given-preorder-and-postorder-traversals/ che propone il seguente codice 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); 
} 

ho provato a riscrivere il codice in Java. Ecco il mio codice:

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); 
    } 

Ma ho avuto un ciclo continuo nel nodo principale (che non ha superato agli altri nodi che devono essere il suo bambino). Potete aiutarmi per favore per vedere dove si trova l'errore nel mio codice Java?

Io non sono davvero sicuro, ma penso che l'errore forse deriva da queste righe:

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

non ho capito molto bene le linee di corrispondenza codice originale C. Soprattutto in questa parte

Answer 1

Qui ci sono gli insetti:

1. Linea if (preorder[i]== postorder[lowIndex]) ha due errori: il primo è che si cerca in preordine invece che in postorder, e la seconda è che usi lowIndex invece di preIndex. Questa linea dovrebbe essere:if (preorder[index.index]== postorder[i])
2. Linea TreeNode root = new TreeNode (preorder[lowIndex]); - lowIndex viene utilizzato ancora una volta, invece di preIndex. Questa linea dovrebbe essere:TreeNode root = new TreeNode (preorder[index.index]);

Prestare attenzione al fatto che questo codice potrebbe funzionare solo per pieni alberi binari

Answer 2

Supponendo che il codice scritto in C funziona, allora la mia ipotesi è che per questa parte

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

che ci si vuole utilizzare le stesse variabili che si utilizzano nella versione C. In questo caso, la vostra istruzione if dovrebbe essere

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

Answer 3

prima fa TreeNode in una classe, in quanto è la Java equivalente di una struttura

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

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

poi prendere la vostra classe 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); 
    } 
} 

Gli errori nel codice erano if (preorder[i]== postorder[lowIndex] e TreeNode root = new TreeNode (preorder[lowIndex]); come menzionato da aviad. Ho cambiato il tuo codice per farti essere un po 'meno confuso. L'uso dell'Indice è un ottimo modo per confonderti, soprattutto dal momento che un int funziona bene. Inoltre, gli incrementi di ++ prima di eseguire il ciclo e non sono usati convenzionalmente in java e java, consentono di dichiarare le variabili come parte della definizione del ciclo, quindi ho deciso che il ciclo fosse più quello che state cercando.