EdD - Clase BinarySearchTree (esto es mucho más útil)

Esta cláse se hereda de la clase BinaryTree, uds. deben copiar las clases Node y BinaryTree en el proyecto donde la piensan utilizar (se puede hacer con un DLL pero eso no es tema de esta materia)

El código es el siguiente:

Código:


using System;

namespace E04
{
  /// <summary>
  /// Implementación de árbol binario de búsqueda
  /// </summary>
  /// <typeparam name="ELEMENT">Tipo de dato de elementos que se introduce en el árbol</typeparam>
  public class BinarySearchTree<ELEMENT> : BinaryTree<ELEMENT> where ELEMENT : IComparable
  {
    #region Constructores (no se heredan)
    /// <summary>
    /// Constructor por defecto
    /// </summary>
    public BinarySearchTree()
      : base()
    {
    }
    /// <summary>
    /// Constructor especializado que crea un árbol
    /// binario de busqueda para el elemento indicado
    /// </summary>
    /// <param name="item">Elemento</param>
    public BinarySearchTree(ELEMENT item)
      : base(item)
    {
    }
    #endregion

    #region Comportamiento Agregar y Retirar elementos
    /// <summary>
    /// Agrega un elemento al árbol binario de búsqueda
    /// </summary>
    /// <param name="item">Elemento a agregar</param>
    public virtual void Add(ELEMENT item)
    {
      if (this.IsEmpty)
      {
        this.Root = new Node<ELEMENT>(item);
      }
      else
      {
        // Implementación iterativa que busca la posición
        // para el nuevo elemento de acuerdo al criterio
        // de comparación que se establece en el método
        // CompareTo de cada Item
        Node<ELEMENT> temp = this.Root, prev = null;
        while (temp != null)
        {
          prev = temp;
          if (temp.Item.CompareTo(item) > 0)
          {
            temp = temp.Left;
          }
          else
          {
            temp = temp.Right;
          }
        }
        // Implementación que crea y agrega un nodo
        // de acuerdo al criterio de comparación que se
        // establece en el método CompareTo de cada Item
        temp = new Node<ELEMENT>(item);
        if (prev.Item.CompareTo(item) > 0)
        {
          prev.Left = temp;
        }
        else
        {
          prev.Right = temp;
        }
      }
    }
    /// <summary>
    /// Extrae el elemento del árbol binario de busqueda
    /// </summary>
    /// <param name="item">Elemento a extraer</param>
    public virtual ELEMENT Remove(ELEMENT item)
    {
      return RemoveByCopy(item);
    }
    /// <summary>
    /// Extrae el elemento del árbol binario de busqueda
    /// implementando la eleiminación por fusión
    /// </summary>
    /// <param name="item">Elemento a extraer</param>
    protected virtual ELEMENT RemoveByFusion(ELEMENT item)
    {
      Node<ELEMENT> find = this.Root, prev = null, node, temp;
      while ((find != null) && (!find.Item.Equals(item)))
      { // búsqueda iterativa del nodo recordando al nodo padre
        prev = find;
        if (find.Item.CompareTo(item) < 0)
        {
          find = find.Right;
        }
        else
        {
          find = find.Left;
        }
      }
      // se supone que en find tenemos el nodo a retirar
      node = find;
      if ((find != null) && (find.Item.Equals(item)))
      {
        if (node.Right == null) // no hay subárbol derecho
        {
          node = node.Left;
        }
        else
        {
          if (node.Left == null)  // no hay subárbol izquierdo
          {
            node = node.Right;
          }
          else
          { // aplicar la técnica mayor de los menores
            temp = node.Left;  // (1) a la izquierda (los menores)
            while (temp.Right != null)  // (2) busca el mayor de los menores
            {
              temp = temp.Right;
            }
            // (3) conectar la rama derecha del nodo que se retira
            temp.Right = node.Right;
            // (4) desconectar el nodo (queda en find)
            node = node.Left;
          }
        }
        // (5) ajustar todo el arbol
        if (find == this.Root)
        {
          this.Root = node;
        }
        else
        {
          if (prev.Left == find)
          {
            prev.Left = node;
          }
          else
          {
            prev.Right = node;
          }
        }
      }
      if (find != null)
      {
        find.Left = find.Right = null;
        return find.Item;
      }
      else // else no está o el árbol está vacio
      {
        throw new Exception("No existe el elemento o el árbol está vacio");
      }
    }
    /// <summary>
    /// Extrae el elemento del árbol binario de busqueda
    /// implementando la eleiminación por copia
    /// </summary>
    /// <param name="item">Elemento a extraer</param>
    protected virtual ELEMENT RemoveByCopy(ELEMENT item)
    {
      Node<ELEMENT> find = this.Root, prev = null, node, temp;
      while ((find != null) && (!find.Item.Equals(item)))
      { // búsqueda iterativa del nodo recordando al nodo padre
        prev = find;
        if (find.Item.CompareTo(item) < 0)
        {
          find = find.Right;
        }
        else
        {
          find = find.Left;
        }
      }
      // se supone que en find tenemos el nodo a retirar
      node = find;
      ELEMENT save = default(ELEMENT);
      if (find != null)
      {
        save = find.Item;
      }
      if ((find != null) && (find.Item.Equals(item)))
      {
        if (node.Right == null) // no hay subárbol derecho
        {
          node = node.Left;
        }
        else
        {
          if (node.Left == null)  // no hay subárbol izquierdo
          {
            node = node.Right;
          }
          else
          { // aplicar la técnica mayor de los menores
            temp = node.Left;  // (1) a la izquierda (los menores)
            Node<ELEMENT> last = node;
            while (temp.Right != null)  // (2) busca el mayor de los menores
            {
              last = temp;
              temp = temp.Right;
            }
            // (3) realiza la copia de contenidos
            node.Item = temp.Item;
            // (4) ajusta los enlaces
            if (last == node)
            {
              last.Left = temp.Left;
            }
            else
            {
              last.Right = temp.Left;
            }
            temp.Left = null;
          }
        }
        // (5) ajustar todo el arbol
        if (find == this.Root)
        {
          this.Root = node;
        }
        else
        {
          if (prev.Left == find)
          {
            prev.Left = node;
          }
          else
          {
            prev.Right = node;
          }
        }
      }
      if (find != null)
      {
        return save;
      }
      else // else no está o el árbol está vacio
      {
        throw new Exception("No existe el elemento o el árbol está vacio");
      }
    }
    #endregion
  }
}


En esta implementación pueden ver la aplicación de las técnicas mayor de los menores; también puede cambiar entre la modalidad de remover por copia o fusión.