la conversion de la STB à la matrice

J'ai cherché partout et n'arrive pas à trouver toute l'aide pour cette question.. pour un projet d'école, j'ai un BST arbre et je dois mettre tous les services de renseignements de l'arbre dans un tableau int appelé BSTarray.
C'est ce que j'ai à ce jour:

public int [] toBSTArray() {
    int size = 20;
    int [] BSTarray = new int [size];
    for(int i = 0; i <size; i++) {
        makeArray(root);
        BSTarray[i] = root.getValue();
}

    return BSTarray;
}

//helper method called by toBSTArray
public void makeArray(BinarySearchTreeNode node) {
    if (node != null) {
        makeArray(node.getLeft());
        makeArray(node.getRight());
        //System.out.print(node.getValue() + " ");
    }
}

Je pensais que cette méthode était censé aller dans l'arborescence, puis d'ajouter les valeurs qu'il trouve dans les différents indices dans la BSTarray, mais tout ce qu'il fait est d'ajouter le même nombre dans tous les index dans le tableau. Suis-je en train de faire quelque chose de mal avec la récursivité?

OriginalL'auteur Gcap | 2012-12-13

5

Essayez ceci:
```
Integer[] values = extractValues(n).toArray(new Integer[] {});
```
avec cette définition de la méthode:
```
private static List<Integer> extractValues(Node n) {
    List<Integer> result = new ArrayList<>();
    if (n.getLeft() != null) {
        result.addAll(extractValues(n.getLeft()));
    }

    if (n.getRight() != null) {
        result.addAll(extractValues(n.getRight()));
    }

    result.add(n.getValue());

    return result;
}
```
J'ai pris un nœud de la structure est semblable à la vôtre. Bien sûr, la méthode ne doit pas être statique si vous ne l'utilisez pas dans une de manière statique.

Cette méthode pourrait ne pas être le plus efficace grâce à la liste de conversion, mais vous n'avez pas à s'embêter avec toute la taille des matrices. Si vous avez vraiment besoin de la fonction pour retourner un tableau, juste envelopper dans une autre fonction, ou laissez-la proposition de la fonction retourne un tableau (cela ferait-il nécessaire de convertir la liste à un tableau avant chaque retour).

Concernant votre code, vous itérer sur les ipour remplir le tableau d'ensemble (peu importe où vous savez que la taille d') mais de toujours définir la valeur à la valeur du nœud racine. C'est pourquoi vous devez toujours avoir la même valeur. Votre makeArray la fonction s'appelle elle-même de manière récursive, mais il ne fait rien (même si vous ajoutez un sysout déclaration 😉 )

Mise à jour:

Et pour la contrainte de l'utilisation de pas de listes, voici une autre version qui utilise uniquement les tableaux:
```
int size = 20;
int[] results = new int[size];
extractValues(n, results, 0);
```
avec la définition de la méthode:
```
private static int extractValues(Node n, int[] results, int index) {
    if (n.getLeft() != null) {
        index = extractValues(n.getLeft(), results, index);
    }

    if (n.getRight() != null) {
        index = extractValues(n.getRight(), results, index);
    }

    results[index] = n.getValue();

    return index + 1;
}
```
Noter que le résultat sera results, alors. La taille doit être supposées être plus le nombre de nœuds ou il doit être compté en parcourant l'arbre, avant d'.

nous ne sommes pas autorisés à utiliser la "Liste"
J'ai ajouté une version qui n'utilise pas les listes, voir ma mise à jour.
merci!!!! nous devons appeler à partir d'un pilote de classe, ce que j'ai fait le toBSTArray méthode à nouveau avec extractValues(n,les résultats,0); et j'ai le tableau "résultats" être retournés, mais il se termine à l'impression à la console comme ceci: [I@66780515
Le [I@66780515 semble être juste la représentation de Chaîne de caractères le tableau Entier. Malheureusement, Java standard n'affiche pas toutes les valeurs lors de l'impression d'un tableau mais seulement [I@66780515 où le support indique que c'est un tableau, le I représente l'Entier et le nombre est juste le code de hachage de l'objet.

OriginalL'auteur sebastian_oe

Comment à ce sujet: (Votre récursivité ne pas apporter des modifications au tableau)

public int [] toBSTArray() {
    int size = 20; //ASSUMING THIS IS LESS THAN OR EQUAL TO NUMBER OF NODES IN THE TREE
    int [] BSTarray = new int [size];
    makeArray(root, 0, BSTarray);
    return BSTarray;
}

//helper method called by toBSTArray
public void makeArray(BinarySearchTreeNode node, int i, int [] BSTarray ) {
    if (node != null) {
        BSTarray[i] = root.getValue();   
        makeArray(node.getLeft(), 2*i+1, BSTarray);
        makeArray(node.getRight(), 2*i+2, BSTarray);
   }
}

j'ai une erreur de compilation avec la signature de la méthode de makeArray, c'est à dire que j'ai besoin d'un identificateur après BSTarray

OriginalL'auteur CEGRD

0

Vous pouvez parcourir l'arborescence d'ajouter les éléments dans un tableau. Par exemple, à l'aide de précommande de la traversée, vous auriez quelque chose comme ceci:
```
void preOrder (BSTNode root){

  if(root == null) 
    return;

  array.add(root.getValue);

  preOrder(root.leftNode());
  preOrder(root.rightNode()); 

}
```
OriginalL'auteur Rafael

Vous devez vous connecter pour publier un commentaire.