La différence entre le binaire de l'arbre et de l'arbre de recherche binaire

Quelqu'un peut-il expliquer la différence entre arbre binaire et binaires de recherche arbres avec un exemple?

InformationsquelleAutor Neel | 2011-06-17

536

Arbre binaire: Arbre où chaque nœud a deux feuilles
```
  1
 /\
2   3
```
Binaires un arbre de recherche: Utilisé pour recherche. Un arbre binaire où la gauche de l'enfant contient seulement nœuds avec des valeurs de moins que le nœud parent, et où le droit de l'enfant seulement contient des nœuds avec les valeurs supérieures ou égales à la société mère.
```
  2
 /\
1   3
```
- Quel est le point de "non-recherche" arbre binaire?
- C'est un conceptuelle chose, vous ne sont pas nécessairement toujours réellement de faire celui qui est complètement sans contrainte. Cependant, il y a beaucoup de non-recherche d'arbres binaires qui sont spécial d'une autre manière, par exemple, tas binaire.
- birary les arbres ne doivent pas nécessairement contenir des données comparables, de nombreux (sans recherche) arbres binaires sont utilisés pour l'analyse d'expression algébrique, arbre binaire est parfait t écrire une notation infixe de l'analyseur, en plaçant l'opérateur en tant que nœud(s) et les valeurs numériques comme leafs
- Ils ne vont pas être d'arbres binaires dans ce cas si. (par exemple, les opérateurs unaires ne peut pas avoir deux enfants.) Je ne peux vraiment pas penser à une pratique en cas d'utilisation sans contrainte pour des arbres binaires, c'est pourquoi j'ai fait ce commentaire.
- Excellent et simple. +1 pour visual exemple 🙂
- Un arbre binaire a une ou deux enfants par nœud. Des arbres d'Expression sont un parfait exemple. Un arbre de recherche binaire aussi a un ou deux enfants par nœud, sauf si elle arrive à être pleine, ce qui ne peut se produire avec certains nombres d'éléments.
- Non, des arbres d'expression sont en fait le parfait contre-exemple. Ils peuvent avoir n'importe quel nombre d'enfants, non seulement jusqu'à 2 (par exemple, f(x,y,z)), sauf si vous êtes à la limitation artificielle pour aucune raison. Encore une fois, je ne peux pas penser à quelque chose qui est naturellement limitée à 2 enfants. (Comme une note de côté, notez que l'opérateur unaire nœuds de ne jamais avoir 2 enfants, tandis que, dans un arbre binaire de tout nœud est donné 2 enfant machines à sous qui, en général, peut être rempli.)
- À mon humble avis, l'image de l'arbre binaire peut être un peu trompeur (comme vous l'avez spécifié les nœuds avec des numéros). Les gens pourraient commencer à les comparer aux autres exemple. Je ne sais pas exactement comment fournir un ici, mais je suggère d'utiliser certains caractères qui montre toute valeur peut être placé là.
- Créez un arbre binaire, effectuer une opération de tri sur elle - pensez appelé treesort - alors, elle devient un Arbre de Recherche Binaire ; on peut rechercher de 1000 points avec seulement 10 comparaisons, donc très rapide. Cependant, le tri est beaucoup de temps de fonctionnement, de sorte que le faire une fois au début.
- Tree_Sort ici en.m.wikipedia.org/wiki/Tree_sort
- Un min-tas et max-heap peut être représenté à l'aide d'un "non-recherche" arbre binaire. @pete
- Je devine que vous avez manqué ma réponse à son commentaire juste en dessous...
- Pour les arbres binaires, ne la gauche de l'enfant doivent précéder le droit de l'enfant en termes de clés-valeurs (numériques, lexigraphically) comme le montre l'exemple? Peut la valeur de la clé de gauche des enfants de 3 et le droit de l'enfant d'être 2?
- Nan ça ne marche pas. Les seules contraintes sont celles que j'ai explicitement dit.
- est-il de la mise en œuvre d'un arbre binaire? (pas d'arbre de recherche binaires) parce que je suis débordée et n'a trouvé aucun exemple. Chacun donne de l'arbre de recherche binaire code.
- Désolé, je n'ai jamais répondu, je pense qu'il n'est pas une raison... ce serait son cas d'utilisation, et quelle serait la contribution de la mise en œuvre? Comme je l'ai écrit plus haut, je ne connais pas de cas d'utilisation pour la plaine sans contrainte d'arbres binaires, et dans certaines langues, ils sont déjà trivial pour représenter toute façon (par exemple [left, value, right] en Python).
InformationsquelleAutor Mehrdad
54

Arbre Binaire est une forme spécialisée de l'arbre avec deux enfants (à gauche de l'enfant et de droit de l'Enfant).
C'est tout simplement la représentation de données dans l'Arborescence

Un Arbre de Recherche binaire (BST) est un type spécial de l'Arbre Binaire qui suit condition suivante:
1. gauche nœud enfant est plus petit que son Nœud parent
2. droit nœud enfant est plus grand que son Nœud parent
- Ces conditions ne sont pas suffisantes. L'ensemble de la gauche de la sous-arborescence doit pas contenir des clés de moins que le parent, et de l'ensemble du droit de la sous-arborescence doit contenir des nœuds plus.
- pouvez-vous expliquer votre commentaire s'il vous plaît? qu'entendez-vous par toute la sous-arborescence? vous voulez dire toutes les valeurs du sous-arbre devrait être inférieure à la racine sur le côté gauche? et toutes les valeurs doivent être supérieures à la racine de la valeur sur le côté droit?
InformationsquelleAutor Jayzcode
36

Un arbre binaire est faite de nœuds, où chaque nœud contient une "gauche" pointeur, d'un "droit" pointeur, et un élément de données. La "racine" d'un pointeur sur le nœud le plus haut dans l'arbre. La gauche et la droite pointeurs de manière récursive point à de petites "branches" de chaque côté. Un pointeur null représente un arbre binaire à n éléments -- l'arbre vide. L'formel de définition récursive est: un arbre binaire est soit vide (représenté par un pointeur null), ou est faite d'un seul nœud, où la gauche et la droite pointeurs (définition récursive à l'avance) chaque point d'un arbre binaire.

Un arbre de recherche binaire (BST) ou "ordonné arbre binaire" est un type d'arbre binaire où les nœuds sont disposés dans l'ordre: pour chaque nœud, tous les éléments de son sous-arbre gauche sont moins pour le nœud (<), et tous les éléments de son sous-arbre droit sont plus importants que le nœud (>).
```
    5
   /\
  3   6 
 /\   \
1   4   9    
```
L'arbre ci-dessus est un arbre de recherche binaire -- la "racine" de nœud est un 5, et son sous-arbre gauche nœuds (1, 3, 4) sont < 5, et de son droit de la sous-arborescence de nœuds (6, 9) > 5. De manière récursive, chacun des sous-arbres doivent aussi obéir à la recherche binaire arbre contrainte: dans le (1, 3, 4) de la sous-arborescence, la 3 est la racine, le 1 < 3 et 4 > 3.

Regarder dehors pour le libellé exact dans les problèmes -- un "arbre de recherche binaire" est différent d'un "arbre binaire".
- Ajoutée structure d'arbre.
InformationsquelleAutor Emmanuel Oddy
13

Comme tout le monde ci-dessus a expliqué la différence entre un arbre binaire et binaire un arbre de recherche, je suis juste en ajoutant comment tester si la donnée binaire est un arbre binaire un arbre 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()<max) && (node.getValue()>=min);

}
```
Espère que ça va vous aider. Désolé si je suis en détournant le sujet que j'ai senti qu'il vaut la peine de mentionner ici.
- Soit la gauche ou la droite de la sous-arborescence peut être vide. Votre code ne gère pas ce cas correctement.
InformationsquelleAutor Trying
10

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, tous les descendants du nœud de valeur dans le sous-arbre gauche de n est inférieure à la valeur de n, et tous les descendants du nœud de valeur dans le sous-arbre droit est plus grand que la valeur de n.

InformationsquelleAutor Kaushik Lele
10

Arbre binaire représente un structure de données qui est composé de nœuds qui peut seulement ont deux enfants références.

Binaires de Recherche Arbres (BST), d'autre part, est une forme particulière de Arbre Binaire structure de données où chaque nœud a une valeur comparable, et les petits apprécié des enfants attachés à gauche et le plus apprécié des enfants attachés à la droite.

Ainsi, tous les BST's sont Arbre Binaire toutefois, seuls quelques Arbre Binaire's peut être aussi BST. Aviser que BST est un sous-ensemble de Arbre Binaire.

Donc, Arbre Binaire est plus générale de la structure des données que Binaires de Recherche Arbres. Et aussi, vous devez en aviser que Binaires de Recherche Arbres est un triés arbre alors qu'il n'y a pas de tel ensemble de règles génériques Arbre Binaire.

Arbre Binaire

Un Binary Tree qui est pas un BST;
```
         5
       /  \
      /    \
     9       2
    /\     /\
  15   17  19  21
```
Arbre de Recherche binaire (triés Arbre)

Un Binaires de Recherche Arbres qui est aussi un Arbre Binaire;
```
         50
       /   \
      /     \
     25      75
    / \    / \
  20    30 70   80
```
Binaire de Recherche Nœud de l'Arborescence de la propriété

Également aviser que, pour tout nœud parent dans le BST;
- De la gauche nœuds possèdent une valeur inférieure à la valeur du nœud parent. Dans le coin supérieur exemple, les nœuds avec des valeurs { 20, 25, 30 }, qui sont toutes situées sur la gauche (gauche descendants) de 50 ans, sont plus petits que 50.
- Tous les nœuds de droite ont plus de valeur que la valeur du nœud parent. Dans le coin supérieur exemple, les nœuds avec des valeurs { 70, 75, 80 }, qui sont tous situés sur la droite (droit descendants) de 50 ans, ce sont plus de 50.
Il n'existe pas une règle pour Arbre Binaire Nœud. La seule règle pour Arbre Binaire Nœud est d'avoir deux enfants, de sorte qu'elle ne s'explique lui-même pourquoi appelle binaire.
- Pouvons-nous mettre en œuvre Simple Arbre Binaire? est-il de la mise en œuvre disponibles? et qu'est-ce que l'utilisation de cet arbre?
- Vous pouvez utiliser le Binaire de Recherche est un Arbre de tri et de recherche. Vous pouvez trouver à la mise en œuvre de l'Arbre de Recherche Binaire ici: github.com/bzdgn/data-structures-in-java/blob/master/src/...
- Je sais à ce sujet mais est-il une existence de Simple Arbre ou un Simple Arbre Binaire? ou la mise en œuvre de Simple Arbre Binaire?
- Il n'y a pas de point de l'utiliser, mais vous pouvez ajouter arbitraire Nœud instances à la racine et aux enfants.
InformationsquelleAutor Levent Divilioglu
5

Arbre binaire

Arbre binaire peut être rien qui a 2 enfants et 1 parent. Il peut être mis en œuvre comme lié liste ou un tableau, ou avec votre API. Une fois que vous commencez à ajouter des règles plus spécifiques, elle devient de plus en plus spécialisé arbre. Les plus communes connues de la mise en œuvre est que, ajoutez les petits nœuds sur la gauche et des plus grands à droite.

Par exemple, une étiquette arbre binaire de taille 9 et de hauteur de 3, avec un nœud racine dont la valeur est 2. L'arbre est déséquilibré, n'est pas trié.
https://en.wikipedia.org/wiki/Binary_tree

Par exemple, dans l'arbre sur la gauche, Une a 6 enfants {B,C,D,E,F,G}. Il peut être converti en binaire arbre sur la droite.

Binaire De Recherche

Binaire de Recherche est la technique/algorithme qui est utilisé pour trouver un élément spécifique sur le nœud de la chaîne. Binaire de recherche travaille sur des tableaux triés.

Binaire de recherche compare la valeur cible pour la milieu élément de la matrice; si elles sont inégales, la moitié dans lequel la cible ne peut pas mentir est éliminé et la recherche continue sur la moitié restante jusqu'à ce qu'elle est réussie ou la moitié restante est vide. https://en.wikipedia.org/wiki/Binary_search_algorithm

Un arbre représentant binaire de recherche. Le tableau est recherché ici est [20, 30, 40, 50, 90, 100], et la valeur cible est de 40.

Binaires de recherche arbres

C'est l'une des implémentations de l'arbre binaire. C'est spécialisé pour recherche.

Binaires de recherche, arbres et B-arbre structures de données sont basés sur binaire de recherche.

Arbres binaires (BST), parfois appelé commandés ou triés arbres binaires, sont un type de conteneur: structures de données qui stockent des "éléments" (tels que les nombres, noms, etc.) dans la mémoire. https://en.wikipedia.org/wiki/Binary_search_tree

Un arbre de recherche binaire de taille 9 et profondeur de 3, avec 8 à la racine. Les feuilles ne sont pas dessinées.

Et enfin un grand schéma de comparer la performance des données connues, des structures et des algorithmes appliqués:

L'Image prise à partir Algorithmes (4e Édition)

InformationsquelleAutor Teoman shipahi
4

Un arbre binaire est un arbre dont les enfants ne sont jamais plus de deux. Un arbre de recherche binaire suit l'invariant que la gauche l'enfant doit avoir une valeur plus petite que le nœud racine de la clé, tandis que le droit de l'enfant devrait avoir une plus grande valeur que le nœud racine de la clé.

InformationsquelleAutor nana yaah
4
- Binaires de recherche arbres: quand afinde traversée est faite sur l'arbre binaire, vous rentrer dans l'ordre des valeurs des éléments insérés
- Arbre binaire: pas l'ordre de tri est trouvé dans n'importe quel type de parcours
- Pas l'ordre de tri besoin être trouvé. Un arbre de recherche binaire est également un arbre binaire. Ils ne sont pas mutuellement exclusives. BST est un sous-ensemble propre de BT.
InformationsquelleAutor AlienOnEarth
3

Pour vérifier la météo ou pas une donnée Binaire est un Arbre Binaire un Arbre de Recherche ici, c'est une autre Approche .

Parcourir l'Arbre En Afinde Mode (c'est à dire à Gauche de l'Enfant --> Parent --> Droit de l'Enfant ) ,
Magasin Traversé les nœuds de Données dans une Variable temporaire permet de dire temp , juste avant de le ranger dans temp , Vérifier la météo actuelle du Nœud de données est supérieur à la précédente ou non .
Puis juste pause il , n'est pas un Arbre Binaire un Arbre de Recherche d'autre traverse jusqu'à la fin.

Ci-dessous est un exemple avec Java:
```
public static boolean isBinarySearchTree(Tree root)
{
    if(root==null)
        return false;

    isBinarySearchTree(root.left);
    if(tree.data<temp)
        return false;
    else
        temp=tree.data;
    isBinarySearchTree(root.right);
    return true;
}
```
Maintenir la variable temp en dehors de
- Soit le sous-arbre peut être null. Votre algorithme ne gère pas ce cas correctement.
InformationsquelleAutor Neeraj Jain
1

Dans un arbre de recherche Binaire, tous les nœuds sont disposés dans un ordre spécifique - noeuds à gauche d'un nœud racine ont une valeur inférieure à sa racine, et tous les nœuds du droit d'un nœud ont des valeurs supérieures à la valeur de la racine.

InformationsquelleAutor Spencer Cheng
0

Un arbre peut être appelé comme un arbre binaire si et seulement si le nombre maximum d'enfants de l'un des nœuds est de deux.

Un arbre peut être appelé comme un arbre de recherche binaire si et seulement si le nombre maximum d'enfants de l'un des nœuds est deux, et à la gauche de l'enfant est toujours plus petit que le droit de l'enfant.

InformationsquelleAutor jith912

Vous devez vous connecter pour publier un commentaire.

Arbre Binaire

Arbre de Recherche binaire (triés Arbre)

Binaire de Recherche Nœud de l'Arborescence de la propriété