Quelles sont les caractéristiques d'un arbre de recherche binaire ?

La caractéristique d'un arbre de recherche binaire est que pour chaque nœud X de l'arbre, toutes les valeurs clés de son sous-arbre gauche sont inférieures à la valeur clé de X, et toutes les valeurs clés de sa droite valeur du mot clé du sous-arbre supérieure à

Caractéristiques des arbres de recherche binaires

Caractéristiques des arbres de recherche binaires : Pour le Pour chaque nœud X , toutes les valeurs clés de son sous-arbre gauche sont inférieures à la valeur clé de X, et toutes les valeurs clés de son sous-arbre droit sont supérieures à la valeur clé de X.

D'après cette propriété, si un parcours dans l'ordre est effectué sur un arbre binaire, s'il est croissant de manière monotone, on peut dire que l'arbre est un arbre de recherche binaire.

Recherche dans l'arbre de recherche binaire

Processus : comparez d'abord avec le nœud racine, et s'il est égal au nœud racine, revenez. S'il est inférieur au nœud racine, recherchez dans le sous-arbre gauche du nœud racine. S'il est supérieur au nœud racine, recherchez dans le sous-arbre droit du nœud racine.

/* 查找以t为根节点的树中，是否包含x */
Position Find(ElementType x, SearchTree t)
{
    if (t == NULL) {
        return NULL;
    } else if (x < t->element) {
        return Find(x, t->left);
    } else if (x > t->element) {
        return Find(x, t->right);
    } else {
        return t;
    }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!