Différence entre arbre binaire et arbre binaire de recherche

Question

Est-ce que quelqu'un peut s'il vous plaît expliquer la différence entre arbre binaire et arbre de recherche binaire avec un exemple?

Answer 1

Arbre binaire : Arbre où chaque nœud a jusqu'à deux feuilles

  1
 / \
2   3

---

Arbre binaire de recherche : Utilisé pour la recherche. Un arbre binaire où l'enfant gauche contient seulement des nœuds avec des valeurs inférieures au nœud parent, et où l'enfant droit contient seulement des nœuds avec des valeurs supérieures ou égales au parent.

  2
 / \
1   3

Answer 2

Arbre binaire est une forme spécialisée d'arbre avec deux enfants (enfant gauche et enfant droit). C'est simplement une représentation des données dans une structure d'arbre

Arbre binaire de recherche (ABR) est un type spécial d'arbre binaire qui suit la condition suivante :

1. le nœud enfant gauche est plus petit que son nœud parent
2. le nœud enfant droit est plus grand que son nœud parent

Answer 3

Un arbre binaire est constitué de nœuds, où chaque nœud contient un pointeur "gauche", un pointeur "droit" et un élément de données. Le pointeur "racine" pointe vers le nœud le plus en haut de l'arbre. Les pointeurs gauche et droite pointent de manière récursive vers des "sous-arbres" plus petits de chaque côté. Un pointeur nul représente un arbre binaire sans éléments -- l'arbre vide. La définition récursive formelle est la suivante : un arbre binaire est soit vide (représenté par un pointeur nul), soit constitué d'un seul nœud, où les pointeurs gauche et droit (définition récursive à suivre) pointent chacun vers un arbre binaire.

Un arbre binaire de recherche (ABR) ou "arbre binaire ordonné" est un type d'arbre binaire où les nœuds sont disposés dans un ordre : pour chaque nœud, tous les éléments de son sous-arbre gauche sont inférieurs au nœud (<), et tous les éléments de son sous-arbre droit sont supérieurs au nœud (>).

    5
   / \
  3   6 
 / \   \
1   4   9    

L'arbre illustré ci-dessus est un arbre binaire de recherche -- le nœud "racine" est un 5, et ses nœuds du sous-arbre gauche (1, 3, 4) sont < 5, et ses nœuds du sous-arbre droit (6, 9) sont > 5. De manière récursive, chacun des sous-arbres doit également respecter la contrainte d'arbre binaire de recherche : dans le sous-arbre (1, 3, 4), le 3 est la racine, le 1 < 3 et 4 > 3.

Faites attention aux termes exacts utilisés dans les problèmes -- un "arbre binaire de recherche" est différent d'un "arbre binaire".

Answer 4

Comme tout le monde l'a expliqué ci-dessus, la différence entre un arbre binaire et un arbre binaire de recherche, je vais simplement ajouter comment tester si l'arbre binaire donné est un arbre binaire de recherche.

boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max)
{

    if(node == null)
    {
        return true;
    }

    boolean left = isBinarySearchTree(node.getLeft(), min, node.getValue());
    boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

    return left && right && (node.getValue()=min);

}

Je espère que cela vous aidera. Désolé si je m'éloigne du sujet, mais je pense que cela vaut la peine de le mentionner ici.

Answer 5

Un arbre de recherche binaire est un type spécial d'arbre binaire qui présente la propriété suivante : pour tout nœud n, la valeur de chaque nœud descendant dans le sous-arbre gauche de n est inférieure à la valeur de n, et la valeur de chaque nœud descendant dans le sous-arbre droit est supérieure à la valeur de n.