Come funziona l'operazione Trova in un albero binario?

0

Sto avendo una confusione in questa Codifica degli alberi binari. Conosco il concetto di albero binario e so come funzionano e tutti, ma in questo codice sorgente sono confuso con l'operazione "Trova". Non riesco a capire come funziona e tutto. Per favore aiutami, sono così interessato a quest'area.

package binarytree_task4;


  class Node 
    {

    private static class Equivalent {

        public Equivalent() {
        }
    }

        public Equivalent data; 
        public Node right; 
        public Node left; 

        public Node(Equivalent data) 
        {

            this(data, null, null);
        }

        public Node(Equivalent data, Node left, Node right) 
        {

            this.data = data;
            this.left = left;
            this.right = right;
        }   
    }


 class binarytree {


    public static void main(String[] args) {

    }

    private static class Equivalent {

        public Equivalent() {
        }
    }

    private static class present {

        public present() {
        }
    }
    private Node root; 
    private int size;

    public binarytree() 
    {
        size = 0;
        root = null;
    }


    public void printTree() 
    {
        if(size == 0)
            System.out.println("Empty");
        else {
            System.out.println("Tree contents:");   
            inorder(root);
        }
    }


    public void inorder(Node present)
    {
        if(present != null) 
        {
            inorder(present.left);
            System.out.println(present.data);
            inorder(present.right);
        }
    }  

    public void Insert(Equivalent data) 
    {
        root = Insert(data, root);
    }


    private Node Insert(Equivalent data, Node present) 
    {
        if( present == null) 
        {
            size++; 
            present = new Node(data, null, null); 
        }

        else if(data.compareTo(present.data)<0)
        {
            present.left = Insert(data,present.left);
                }

        else if(data.compareTo(present.data)>0)
                { 

            present.right = Insert(data, present.right);
        }

        return present;
    }  



    public boolean Find(Equivalent data) 
    {
        return Find(data, root);    
    }


    private boolean Find(Equivalent data, Node present) 
    {

        if(present == null ) 
        {
            return false;
        }
        else if(present.data == data)
        {
            return true;    
        }
        else if(data.compareTo(present.data)<0)  
        {
            return Find(data, present.left); 
        }
        else 
        {
            return Find(data, present.right); 
        }
    }



    public boolean Delete(Equivalent key){

        if (Find(key)){
            Delete(key);
            return true;
        }
        else{
            return false;
        }
    }

    public void delete(Equivalent key) 
    { 
        Node present = root;
        Node parent = root;

        boolean isLeftChild = true;


        while(present.data.compareTo(key) != 0)        
        {

            parent = present;
            if(present.data.compareTo(key) > 0)      
            {
                isLeftChild = true; 
                present = present.left; 
            }
            else                            
            {
                isLeftChild = false; 
                present = present.right; 
            }
            if(present == null)            
                return ;            
        }   

        if(present.left == null && present.right == null) 
        {
            if(present == root) 
                root = null;                
            else if(isLeftChild)      
                parent.left = null;    
            else                             
                parent.right = null;
        }

        else if(present.right == null)   
            if(present == root)      
                root = present.left; 
            else if(isLeftChild) 
                parent.left = present.left;  
            else 
                parent.right = present.left;  

        else if(present.left == null)    
            if(present == root)              
                root = present.right;    
            else if(isLeftChild) 
                parent.left = present.right; 
            else  
                parent.right = present.right;   

        else 
        {

            Node successor = getSuccessor(present); 

            if(present == root)  
                root = successor;
            else if(isLeftChild)     
                parent.left= successor; 
            else
                parent.right = successor;

            successor.left = present.left; 
         }   
    }


   private Node getSuccessor(Node delNode)
   {
        Node successorParent = delNode;  
        Node successor = delNode;    
        Node present = delNode.right; 

        while(present != null) 
        { 


            successorParent = successor; 
            successor = present;             
            present = present.left;          
        }
        if(successor != delNode.right) 
        { 

            successorParent.left = successor.right;  
            successor.right = delNode.right;         
        }
        return successor; 
   }


}
    
posta Reem 30.12.2011 - 16:00
fonte

1 risposta

5

Trova funziona in modo ricorsivo, nel senso che può chiamare se stesso. Tuttavia, non si chiama solo con gli stessi argomenti, ogni volta che si chiama va più in profondità nell'albero. Se non ci fossero controlli, questo potrebbe andare avanti all'infinito. Tuttavia, questa ricorsione ha un paio di controlli per terminare la ricerca se viene assegnato un nodo nullo (ovvero, non ha trovato quello che cercava), oppure il nodo che gli viene assegnato è quello cercato (ovvero ha trovato quello che cercava). Alla fine una di queste condizioni deve essere vera.

Funziona così:

Prima controlla il nodo che gli è stato assegnato. Se il nodo è nullo, non ha trovato ciò che cercava e non ci sono bambini da cercare, quindi restituisce false. Questo è il primo controllo di terminazione e significa "non l'abbiamo trovato".

Se il nodo non è nullo, controlla se il nodo ha i dati richiesti. Questo è il secondo controllo di terminazione. Se lo fa, restituisce il vero significato "l'abbiamo trovato".

Se non trova i dati richiesti, deve guardare a sinistra oa destra a seconda che i dati richiesti siano più grandi o più piccoli dei dati correnti.

Come fa questo ultimo passo? Prendendo il nodo sinistro o destro e iniziando l'intero processo chiamandolo con il nodo sinistro o destro del nodo corrente e quindi restituendo il risultato. Se il nodo su cui è attualmente attivo è un nodo foglia (cioè: nessun ramo sinistro o destro da seguire), allora un nodo null verrà inviato quando si chiama da solo, e come si può vedere da prima nel processo, se Trova è dato un nodo null restituirà false.

Quindi, in sostanza, Find dice "Sono il nodo che stiamo cercando?" Se la risposta è no, allora si chiede "il mio nodo sinistro è quello che stiamo cercando?" o "il mio nodo destro è quello che sto cercando?" e continua a porsi questa domanda mentre va sempre più in profondità nell'albero.

Si noti che in tutti i casi, Trova restituisce true, false o il risultato della prossima chiamata a Trova. Ciò significa che alla fine, alcune versioni di Trova restituiranno true o false quando arriverà alla fine dell'albero e che true o false eseguiranno il backup della catena - true (o false) ritornerà al chiamante, che restituisce quel valore al suo chiamante, che restituisce quel valore al suo chiamante, ... fino a quando non si torna a dove è stato chiamato per la prima volta.

    
risposta data 30.12.2011 - 16:41
fonte

Leggi altre domande sui tag