La création d'un arbre de recherche binaire Java

Donc, ici, est le Nœud de la classe:

public class Node
{
    private int _info;
    private Node _left;
    private Node _right;

    public Node()
    {
        //this._info = Integer.MIN_VALUE;
        this._left = null;
        this._right = null;
    }


    public int getInfo()
    {
        return _info;
    }

    public void setInfo(int _info)
    {
        this._info = _info;
    }

    public Node getLeft()
    {
        return _left;
    }

    public void setLeft(Node _left)
    {
        this._left = _left;
    }

    public Node getRight()
    {
        return _right;
    }

    public void setRight(Node _right)
    {
        this._right = _right;
    }  
}

Comment je créer l'arbre:

public class BalancedBinaryTree
{
    private ArrayList<Integer> _numbers;
    private Node _root;

    public BalancedBinaryTree(ArrayList<Integer> numbers)
    {
        this._numbers = new ArrayList<>();
        this._numbers.addAll(numbers);
        Collections.sort(this._numbers);

        this._root = new Node();

        this.create(this._root, 0, this._numbers.size());
    }

    private void create(Node tree, int i, int j)
    {
        if (i < j)
        {
            int m = i + (j - i) / 2;

            tree.setInfo(this._numbers.get(m));

            tree.setLeft(new Node());
            create(tree.getLeft(), i, m);

            tree.setRight(new Node());
            create(tree.getRight(), m + 1, j);
        }
    }

Cette méthode permet de calculer la profondeur:

    public static int getDepth(Node node)
    {
        if (node == null)
        {
            return 0;
        }
        else
        {
            int max = 0;
            if (getDepth(node.getLeft()) > getDepth(node.getRight()))
            {
                max = getDepth(node.getLeft());
            }
            else
            {
                max = getDepth(node.getRight());
            }
            return max + 1;
        }
    }

Et ces deux combinés doivent imprimer l'arbre à ses niveaux:

    public static void printLevel(Node node, int levelToDisplay, int currentLevel)
    {
        if (node != null)
        {
            printLevel(node.getLeft(), levelToDisplay, currentLevel);
            if (currentLevel == levelToDisplay)
            {
                System.out.print(node.getInfo() + " ");
            }
            currentLevel++;
            printLevel(node.getRight(), levelToDisplay, currentLevel);
        }
    }

    public static void printLevels(Node node)
    {
        for (int i = 0; i < getDepth(node); i++)
        {
            System.out.println("Level :" + i);
            printLevel(node, i, 0);
            System.out.println();
        }
    }

Dans une classe de test que j'ai:

    testNumbers.add(15);
    testNumbers.add(20);
    testNumbers.add(25);
    testNumbers.add(30);
    testNumbers.add(35);
    testNumbers.add(40);
    testNumbers.add(45);


    BalancedBinaryTree tree = new BalancedBinaryTree(testNumbers);
    BalancedBinaryTree.printLevels(tree.getRoot());

Et j'obtiens ce résultat:

Level :0
0 15 20 30 
Level :1
0 0 25 0 35 40 
Level :2
0 0 0 45 
Level :3
0

Je devrais obtenir

Level :0
30
Level :1
20 40
Level :2
15 25 35 45

1. Quel est le problème avec le getDepth méthode, car il semble qu'il renvoie 4 niveaux au lieu de 3?
2. Pourquoi il y a des nœuds supplémentaires? (ces zéros)

Je suis sûr que j'ai résolu le problème mais j'ai besoin d'une explication pour les éléments suivants:

C'est de la modification de la printlevel méthode:

public static void printLevel(Node node, int levelToDisplay, int currentLevel)
{
    if (node.getLeft() != null && node.getRight() != null)           
    {
        printLevel(node.getLeft(), levelToDisplay, currentLevel+1);  
        if (currentLevel == levelToDisplay)
        {
            System.out.print(node.getInfo() + " ");
        }
        printLevel(node.getRight(), levelToDisplay, currentLevel+1);  
    }
}

Comme vous pouvez le voir j'ai tester maintenant si le nœud actuel a childs au lieu de vérifier si le nœud actuel existe et c'est pourquoi ces zéros pu l'entendre, car le parcours atteint les leafs qui n'avaient pas d'info attribué à leur droite et à gauche de childs.

La chose que je veux comprendre c'est la différence entre l'incrémentation currentLevel puis en le passant à l'appel de printLevel et simplement de passage currentLevel+1 à l'appel. Ne devrait-elle pas être la même chose ?

Et la getDepth fonction:

public static int getDepth(Node node)
{
    if (node.getLeft() == null && node.getRight() == null)
    {
        return 0;
    }
    else
    {
        int max = 0;
        if (getDepth(node.getLeft()) > getDepth(node.getRight()))
        {
            max = getDepth(node.getLeft());
        }
        else
        {
            max = getDepth(node.getRight());
        }
        return 1 + max;
    }
}

Même chose ici: la traversée atteint les leafs et a obtenu un plus appel à ses childs revenant ainsi un niveau supplémentaire, encore une fois, la solution est de tester si le nœud actuel a childs au lieu de vérifier si le nœud actuel sorties.