Árbol binario extendido

El árbol binario extendido es un tipo de árbol binario en el que todos los subárboles nulos del árbol original se reemplazan con Nodes especiales llamados Nodes externos , mientras que otros Nodes se denominan Nodes internos. 
 

Aquí los círculos representan los Nodes internos y las cajas representan los Nodes externos.
Propiedades del árbol binario externo 
 

1. Los Nodes del árbol original son Nodes internos y los Nodes especiales son Nodes externos.
2. Todos los Nodes externos son Nodes hoja y los Nodes internos son Nodes no hoja.
3. Cada Node interno tiene exactamente dos hijos y cada Node externo es una hoja. Muestra el resultado, que es un árbol binario completo.

Usos:

1. Es útil para la representación en expresiones algebraicas. 

A continuación se muestra un ejemplo de cómo hacer un árbol binario extendido en C++ haciendo que todos los Nodes externos sean ‘-1’ 
 

// C++ program to make an extended binary tree
#include <bits/stdc++.h>
using namespace std;
 
// A Tree node
struct Node {
    int key;
    struct Node *left, *right;
};
 
// Utility function to
// create a new node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return (temp);
}
 
// Function for inorder traversal
void traverse(Node* root)
{
    if (root != NULL) {
        traverse(root->left);
        cout << root->key << " ";
        traverse(root->right);
    }
    else {
 
        // Making external nodes
        root = newNode(-1);
        cout << root->key << " ";
    }
}
 
// Driver code
int main()
{
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(5);
    root->right->right = newNode(4);
 
    traverse(root);
 
    return 0;
}

// Java program to make an extended binary tree
class GFG
{
     
// A Tree node
static class Node
{
    int key;
    Node left, right;
};
 
// Utility function to create a new node
static Node newNode(int key)
{
    Node temp = new Node();
    temp.key = key;
    temp.left = temp.right = null;
    return (temp);
}
 
// Function for inorder traversal
static void traverse(Node root)
{
    if (root != null)
    {
        traverse(root.left);
        System.out.print(root.key + " ");
        traverse(root.right);
    }
    else
    {
 
        // Making external nodes
        root = newNode(-1);
        System.out.print(root.key + " ");
    }
}
 
// Driver code
public static void main(String args[])
{
    Node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(5);
    root.right.right = newNode(4);
 
    traverse(root);
}
}
 
// This code is contributed by Arnab Kundu

// C# program to make an extended binary tree
using System;
 
class GFG
{
         
    // A Tree node
    public class Node
    {
        public int key;
        public Node left, right;
    };
     
    // Utility function to create a new node
    static Node newNode(int key)
    {
        Node temp = new Node();
        temp.key = key;
        temp.left = temp.right = null;
        return (temp);
    }
     
    // Function for inorder traversal
    static void traverse(Node root)
    {
        if (root != null)
        {
            traverse(root.left);
            Console.Write(root.key + " ");
            traverse(root.right);
        }
        else
        {
     
            // Making external nodes
            root = newNode(-1);
            Console.Write(root.key + " ");
        }
    }
     
    // Driver code
    public static void Main()
    {
        Node root = newNode(1);
        root.left = newNode(2);
        root.right = newNode(3);
        root.left.left = newNode(5);
        root.right.right = newNode(4);
     
        traverse(root);
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
// Javascript program to make an extended binary tree
     
// A Tree node
class Node
{
    constructor()
    {
        this.key = 0;
        this.left = null;
        this.right = null;
    }
};
 
// Utility function to create a new node
function newNode(key)
{
    var temp = new Node();
    temp.key = key;
    temp.left = temp.right = null;
    return (temp);
}
 
// Function for inorder traversal
function traverse(root)
{
    if (root != null)
    {
        traverse(root.left);
        document.write(root.key + " ");
        traverse(root.right);
    }
    else
    {
 
        // Making external nodes
        root = newNode(-1);
        document.write(root.key + " ");
    }
}
 
// Driver code
var root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(5);
root.right.right = newNode(4);
traverse(root);
 
</script>

# Python 3 program to make an extended binary tree
 
# A Tree node
class Node :
    def __init__(self):
        self.key=-1
        self.left=self.right=None
 
 
# Utility function to
# create a new node
def newNode(key):
    temp = Node()
    temp.key = key
    temp.left = temp.right = None
    return temp
 
 
# Function for inorder traversal
def traverse(root):
    if (root != None) :
        traverse(root.left)
        print(root.key,end=" ")
        traverse(root.right)
     
    else :
 
        # Making external nodes
        root = newNode(-1)
        print(root.key,end=" ")
     
 
 
# Driver code
if __name__ == '__main__':
    root = newNode(1)
    root.left = newNode(2)
    root.right = newNode(3)
    root.left.left = newNode(5)
    root.right.right = newNode(4)
 
    traverse(root)
    print()
# This code was added by Amartya Ghosh

-1 5 -1 2 -1 1 -1 3 -1 4 -1

Complejidad temporal : O(N). 
Espacio Auxiliar : O(N).  
Aplicación del árbol binario extendido: 
 

1. Calcular la longitud de la ruta ponderada: se utiliza para calcular la longitud total de la ruta en el caso de un árbol ponderado.

1. Aquí, la suma de los pesos totales ya está calculada y almacenada en los Nodes externos y, por lo tanto, hace que sea mucho más fácil calcular la longitud total de la ruta de un árbol con los pesos dados. La misma técnica se puede utilizar para actualizar tablas de enrutamiento en una red.
2. Para convertir un árbol binario en un árbol binario completo: El árbol anterior, que ha eliminado todos los Nodes externos, no es un árbol binario completo. Para introducir cualquier árbol como árbol completo, se le añaden Nodes externos. El montón es un gran ejemplo de un árbol binario completo y, por lo tanto, cada árbol binario se puede expresar como un montón si se le agregan Nodes externos.