Árbol binario enhebrado

El recorrido en orden de un árbol binario se puede realizar mediante recursividad o mediante el uso de una pila auxiliar . La idea de los árboles binarios enhebrados es hacer que el recorrido en orden sea más rápido y hacerlo sin pila y sin recursividad. Un árbol binario se enhebra haciendo que todos los punteros secundarios correctos que normalmente serían NULL apunten al sucesor en orden del Node (si existe).
Hay dos tipos de árboles binarios enhebrados. 
Subproceso único: donde se hace que un puntero derecho NULL apunte al sucesor en orden (si existe un sucesor)
Subproceso doble:Donde los punteros NULL izquierdo y derecho se hacen para apuntar al predecesor en orden y al sucesor en orden respectivamente. Los subprocesos predecesores son útiles para el recorrido en orden inverso y el recorrido en posorden.
Los subprocesos también son útiles para acceder rápidamente a los ancestros de un Node.
El siguiente diagrama muestra un ejemplo de árbol binario de subproceso único. Las líneas punteadas representan hilos. 

Representación en C de un Node 
con subprocesos A continuación se muestra la representación en C de un Node con un solo subproceso.

struct Node
{
    int data;
    struct Node *left, *right;
    bool rightThread; 
}

Representación Java de un Node con subprocesos

A continuación se muestra la representación en Java de un Node de subproceso único.

static class Node
{
    int data;
    Node left, right;
    boolean rightThread; 
}
 
// This code contributed by aashish1995

class Node:
    def __init__(self, data,rightThread):
        self.data = data;
        self.left = None;
        self.right = None;
        self.rightThread = rightThread;
 
# This code is contributed by umadevi9616

public class Node
{
   public int data;
   public Node left, right;
   public bool rightThread; 
}
 
// This code is contributed by aashish1995

<script>
 class Node {
        constructor(val) {
            this.data = val;
            this.left = null;
            this.right = null;
            this.rightThread = false;
        }
    }
 
// This code contributed by aashish1995
</script>

Dado que el puntero derecho se usa para dos propósitos, la variable booleana rightThread se usa para indicar si el puntero derecho apunta al hijo derecho o al sucesor en orden. De manera similar, podemos agregar leftThread para un árbol binario de doble hilo.
Recorrido en orden usando subprocesos 
A continuación se muestra el código para el recorrido en orden en un árbol binario subproceso.

// Utility function to find leftmost node in a tree rooted
// with n
struct Node* leftMost(struct Node* n)
{
    if (n == NULL)
        return NULL;
 
    while (n->left != NULL)
        n = n->left;
 
    return n;
}
 
// C code to do inorder traversal in a threaded binary tree
void inOrder(struct Node* root)
{
    struct Node* cur = leftMost(root);
    while (cur != NULL) {
        printf("%d ", cur->data);
 
        // If this node is a thread node, then go to
        // inorder successor
        if (cur->rightThread)
            cur = cur->right;
        else // Else go to the leftmost child in right
             // subtree
            cur = leftmost(cur->right);
    }
}

// Utility function to find leftmost node in a tree rooted
// with n
Node leftMost(Node n)
{
    if (n == null)
        return null;
 
    while (n.left != null)
        n = n.left;
 
    return n;
}
 
// C code to do inorder traversal in a threaded binary tree
static void inOrder(Node root)
{
    Node cur = leftMost(root);
    while (cur != null) {
        System.out.printf("%d ", cur.data);
 
        // If this node is a thread node, then go to
        // inorder successor
        if (cur.rightThread)
            cur = cur.right;
        else // Else go to the leftmost child in right
             // subtree
            cur = leftmost(cur.right);
    }
}
 
// This code contributed by aashish1995

# Utility function to find leftmost Node in a tree rooted
# with n
def leftMost(n):
 
    if (n == None):
        return None;
 
    while (n.left != None):
        n = n.left;
 
    return n;
 
 
# C code to do inorder traversal in a threaded binary tree
def inOrder(root):
 
    cur = leftMost(root);
    while (cur != None):
        print(cur.data," ");
 
        # If this Node is a thread Node, then go to
        # inorder successor
        if (cur.rightThread):
            cur = cur.right;
        else: # Else go to the leftmost child in right
             # subtree
            cur = leftmost(cur.right);
 
# This code is contributed by Rajput-Ji

// Utility function to find leftmost node in a tree rooted
// with n
Node leftMost(Node n)
{
  if (n == null)
    return null;
 
  while (n.left != null)
    n = n.left;
 
  return n;
}
 
// C code to do inorder traversal in a threaded binary tree
static void inOrder(Node root)
{
  Node cur = leftMost(root);
  while (cur != null)
  {
    Console.Write("{0} ", cur.data);
 
    // If this node is a thread node, then go to
    // inorder successor
    if (cur.rightThread)
      cur = cur.right;
    else // Else go to the leftmost child in right
      // subtree
      cur = leftmost(cur.right);
  }
}
 
// This code is contributed by gauravrajput1

<script>
 
// Utility function to find leftmost node in a tree rooted
// with n
function leftMost(n)
{
    if (n == null)
        return null;
  
    while (n.left != null)
        n = n.left;
  
    return n;
}
 
// JavaScript code to do inorder traversal in
// a threaded binary tree
function inOrder(root)
{
    let cur = leftMost(root);
    while (cur != null) {
        document.write(cur.data+" ");
  
        // If this node is a thread node, then go to
        // inorder successor
        if (cur.rightThread)
            cur = cur.right;
        else // Else go to the leftmost child in right
             // subtree
            cur = leftmost(cur.right);
        }
}
 
// This code is contributed by unknown2108
 
</script>

El siguiente diagrama demuestra el recorrido en orden en orden usando subprocesos.
 

Ventajas del árbol binario enhebrado

• En este Árbol permite el recorrido lineal de elementos.
• Elimina el uso de la pila ya que realiza un recorrido lineal.
• Permite encontrar el Node principal sin el uso explícito del puntero principal
• El árbol enhebrado proporciona un recorrido hacia adelante y hacia atrás de los Nodes en orden.
• Los Nodes contienen punteros al predecesor y sucesor en orden
   

Pronto discutiremos la inserción y eliminación en árboles binarios enhebrados.
Fuentes:  
http://en.wikipedia.org/wiki/Threaded_binary_tree  
www.cs.berkeley.edu/~kamil/teaching/su02/080802.ppt
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema discutido anteriormente