Sucesor en orden en el árbol de búsqueda binaria

Este team de especialistas pasados ciertos días de investigación y recopilación de de datos, encontramos los datos necesarios, nuestro deseo es que todo este artículo sea de utilidad en tu trabajo.

Solución:

La forma general depende de si tiene un enlace principal en sus nodos o no.

Si almacena el enlace principal

Entonces eliges:

1. El hijo más a la izquierda del hijo derecho, si su nodo actual tiene un hijo derecho. Si el hijo derecho no tiene hijo izquierdo, el hijo derecho es su sucesor en orden.
2. Navegue hacia arriba por los nodos antecesores principales, y cuando encuentre un padre cuyo hijo izquierdo sea el nodo en el que se encuentra actualmente, el padre será el sucesor en orden de su nodo original.

Si tiene un hijo adecuado, haga este enfoque (caso 1 anterior):

Si no tiene un hijo adecuado, siga este enfoque (caso 2 anterior):

Si no almacena el enlace principal

Luego, debe ejecutar un escaneo completo del árbol, haciendo un seguimiento de los nodos, generalmente con una pila, para que tenga la información necesaria para hacer básicamente lo mismo que el primer método que se basó en el enlace principal.

Código de Python a la respuesta de Lasse:

def findNext(node):
  # Case 1
  if node.right != None:
    node = node.right:
    while node.left:
      node = node.left
    return node

  # Case 2
  parent = node.parent
  while parent != None:
    if parent.left == node:
      break
    node = parent
    parent = node.parent
  return parent

Aquí hay una implementación sin la necesidad de enlaces principales o estructuras intermedias (como una pila). Esta función de sucesor en orden es un poco diferente de lo que la mayoría podría estar buscando, ya que opera en el key a diferencia del nodo. Además, encontrará un sucesor de un key incluso si no está presente en el árbol. Sin embargo, no es demasiado difícil de cambiar si es necesario.

public class Node> 

private T data;
private Node left;
private Node right;

public Node(T data, Node left, Node right) 
    this.data = data;
    this.left = left;
    this.right = right;


/*
 * Returns the left-most node of the current node. If there is no left child, the current node is the left-most.
 */
private Node getLeftMost() 
    Node curr = this;
    while(curr.left != null) curr = curr.left;
    return curr;


/*
 * Returns the right-most node of the current node. If there is no right child, the current node is the right-most.
 */
private Node getRightMost() 
    Node curr = this;
    while(curr.right != null) curr = curr.right;
    return curr;


/**
 * Returns the in-order successor of the specified key.
 * @param key The key.
 * @return
 */
public T getSuccessor(T key) 
    Node curr = this;
    T successor = null;
    while(curr != null) 
        // If this.data < key, search to the right.
        if(curr.data.compareTo(key) < 0 && curr.right != null) 
            curr = curr.right;
        
        // If this.data > key, search to the left.
        else if(curr.data.compareTo(key) > 0)  
            // If the right-most on the left side has bigger than the key, search left.
            if(curr.left != null && curr.left.getRightMost().data.compareTo(key) > 0) 
                curr = curr.left;
            
            // If there's no left, or the right-most on the left branch is smaller than the key, we're at the successor.
            else 
                successor = curr.data;
                curr = null;
            
        
        // this.data == key...
        else 
            // so get the right-most data.
            if(curr.right != null) 
                successor = curr.right.getLeftMost().data;
            
            // there is no successor.
            else 
                successor = null;
            
            curr = null;
        
    
    return successor;


public static void main(String[] args) 
    Node one, three, five, seven, two, six, four;
    one = new Node(Integer.valueOf(1), null, null);
    three = new Node(Integer.valueOf(3), null, null);
    five = new Node(Integer.valueOf(5), null, null);
    seven = new Node(Integer.valueOf(7), null, null);
    two = new Node(Integer.valueOf(2), one, three);
    six = new Node(Integer.valueOf(6), five, seven);
    four = new Node(Integer.valueOf(4), two, six);
    Node head = four;
    for(int i = 0; i <= 7; i++) 
        System.out.println(head.getSuccessor(i));
    

Eres capaz de añadir valor a nuestro contenido dando tu experiencia en las observaciones.

---

---

Utiliza Nuestro Buscador