Pseudo-code Binaire un arbre de recherche

Dans un arbre de recherche binaire, le prédécesseur de x clé est une clé de y qui est plus petit que
x, et pour lequel il n'existe aucune autre touche z tel que z est plus petit que x et plus
que de y.

Donner le pseudo-code d'un algorithme qui prend une clé de x et renvoie le
prédécesseur de y ou nul si x est la plus petite clé dans l'arbre. Supposons que le binaire
un arbre de recherche est représenté à l'aide de tableaux à gauche, à droite, et un parent. Donner le pseudo-code
pour toute filiale fonctions qui sont utilisées.

Je ne suis pas vraiment sûr de savoir comment aborder cette question. Mais voici ma tentative:

Pseudocode:

//Takes in key x

BST(x)
{

if ( x < parent[x] )

    return nil

if( parent[x] < x )

   return parent[x] //parent[x] = y
}
InformationsquelleAutor Hyune | 2015-04-23
  1. 0

    Ma réponse précédente était d'une mauvaise readover de votre question - ce que vous cherchez est juste le prédécesseur de l'arbre.
    http://www.quora.com/How-can-you-find-successors-and-predecessors-in-a-binary-search-tree-in-order

    voici le code qu'ils utilisent dans ce post:

    public static TreeNode findPredecessor(TreeNode node)
{
    if (node == null)
        return null;

    if (node.getLeft() != null)
        return findMaximum(node.getLeft());

    TreeNode parent = node.getParent();

    TreeNode y = parent;
    TreeNode x = node;
    while (y != null && x == y.getLeft())
    {
        x = y;
        y = y.getParent();
    }

    return y;
}
    InformationsquelleAutor Catalyst
  2. 0

    Si il n'y a pas de n'importe quel nœud de gauche présent, alors il ne peut pas être de tout prédécesseur. Autrement max élément dans le sous-arbre gauche sera le prédécesseur 

    public int findmax(Node root) {
     if (root == NULL) 
      return INT_MIN; 

    int res = root->data; 
    int lres = findMax(root->left); 
    int rres = findMax(root->right); 
    if (lres > res) 
      res = lres; 
    if (rres > res) 
      res = rres; 
    return res; 
}

public int findPredecessor(Node node) {

     if(node == null) return null;
     if(node->left == null) return null;
     return findMax(node->left);
}
    InformationsquelleAutor praneet drolia