Wie binäre Suchbaum mit einem unsortierten Array mit dieser spezifischen Formel zu implementieren?

Question

Ich muss ein Array verwenden, um eine binäre Suchstruktur mit einer bestimmten Formel zu implementieren: root ist Baum [0]. Für jeden Knoten in Baum [n] werden die Kinder von n (falls vorhanden) in Baum [2n + 1] (linker Zweig) und Baum [2n + 2] (rechter Zweig) gefunden. Ich darf ein zweites Array erstellen, um die BST zu speichern. Ich bin ein Pseudo-Code angegeben:

for(i=1;i<;i++) { 
    //Every iteration we start from the root node 
    while (the cell is not empty){ 
     if(less than the element) 
     go to 2i+1; 
     else if (greater than the element) 
     go to 2i+2; 

Bisher das, was ich brainstormed:

public class BinarySearchTree { 

    public void createBST(int[] array) { 

     int[] tree = new int[array.length]; 

     int root = array[0]; 

     for (int i = 0; i < array.length; i++) { 
      if (array[i] < root) { 
       tree[(2*i)+1] = array[i]; 
      } else { 
       array[(2 * i) + 2]; 
      } 
     } 
    } 
} 

Ich weiß nicht, wohin man von hier zu gehen. Ich mache das schon eine Weile ohne Lösung. Jede Hilfe wird geschätzt. Vielen Dank.

Answer 1

dass Pseudocode nie einen Baum erstellt.

Alle Array-Werte sind nur für den Vergleich relevant, die interessante Information ist der Index. Auch das "Gehe zu" ändert eine Position. Diese Position muss irgendwo gespeichert werden (und beginnt mit der Wurzel).

Integer[] tree = new Integer[array.length] 
//the element to add is array[i] 
for (int i = 0; i < array.length; ++i) { 
    //every iteration starts from the root node 
    int pos = 0; 
    //while the cell is not empty 
    while (tree[pos] != null) { 
     //if the cell is smaller than the element 
     if (tree[pos] < array[i]) { 
      //go to 2n+1 
      pos = 2 * pos + 1; 
     } else { 
      //go to 2n+2 
      pos = 2 * pos + 2; 
     } 
    } 
    //add at the empty position. 
    tree[pos] = array[i]; 
} 

Hinweis: Ich habe das nicht testen, es könnte ein ArrayIndexOutBoundException einen etwas Punkt werfen.