Módulo de árbol binario en Python

Un árbol binario es una estructura de datos en la que cada Node o vértice tiene como máximo dos hijos. En Python, un árbol binario se puede representar de diferentes maneras con diferentes estructuras de datos (diccionario, lista) y representaciones de clase para un Node. Sin embargo, la biblioteca binarytree ayuda a implementar directamente un árbol binario. También es compatible con el árbol de búsqueda binaria y en montón (BST). Este módulo no viene preinstalado con el módulo de utilidad estándar de Python. Para instalarlo, escriba el siguiente comando en la terminal.
 

pip install binarytree 

Creación de Node

La clase de Node representa la estructura de un Node particular en el árbol binario. Los atributos de esta clase son valores, izquierda, derecha.
 

Sintaxis: binarytree.Node(valor, izquierda=Ninguno, derecha=Ninguno)
Parámetros:  
valor: Contiene los datos de un Node. Este valor debe ser un número. 
izquierda: Contiene los detalles del hijo del Node izquierdo. 
right: contiene detalles del hijo del Node derecho. 
 

Nota: Si el Node secundario izquierdo o derecho no es una instancia de la clase binarytree.Node, se generará binarytree.exceptions.NodeTypeError y, si el valor del Node no es un número, se generará binarytree.exceptions.NodeValueError.
Ejemplo:

from binarytree import Node
root = Node(3)
root.left = Node(6)
root.right = Node(8)
  
# Getting binary tree
print('Binary tree :', root)
  
# Getting list of nodes
print('List of nodes :', list(root))
  
# Getting inorder of nodes
print('Inorder of nodes :', root.inorder)
  
# Checking tree properties
print('Size of tree :', root.size)
print('Height of tree :', root.height)
  
# Get all properties at once
print('Properties of tree : \n', root.properties)

Producción:

Árbol binario: 
3 
/ \ 
6 8
Lista de Nodes: [Node(3), Node(6), Node(8)]
Orden de los Nodes: [Node(6), Node(3), Node(8)]
Tamaño de árbol: 3
Altura del árbol: 1
Propiedades del árbol: 
{‘altura’: 1, ‘tamaño’: 3, ‘is_max_heap’: False, ‘is_min_heap’: True, ‘is_perfect’: True, ‘is_strict’: True, ‘ is_complete’: Verdadero, ‘leaf_count’: 2, ‘min_node_value’: 3, ‘max_node_value’: 8, ‘min_leaf_ depth’: 1, ‘max_leaf_ depth’: 1, ‘is_bst’: False, ‘is_balanced’: True, ‘is_symmetric’ : Falso}

Construya un árbol binario de la Lista:

En lugar de usar el método Node repetidamente, podemos usar el método build() para convertir una lista de valores en un árbol binario. 
Aquí, una lista dada contiene los Nodes del árbol tal que el elemento en el índice i tiene su hijo izquierdo en el índice 2*i+1, el hijo derecho en el índice 2*i+2 y el padre en (i – 1)//2 . Los elementos en el índice j para j>len(lista)//2 son Nodes hoja. Ninguno indica la ausencia de un Node en ese índice. También podemos recuperar la lista de Nodes después de construir un árbol binario usando el atributo de valores.
 

Sintaxis: binarytree.build(valores)
Parámetros: 
valores: Representación de lista del árbol binario.
Devuelve: raíz del árbol binario. 
 

Ejemplo: 

# Creating binary tree 
# from given list
from binarytree import build
  
  
# List of nodes
nodes =[3, 6, 8, 2, 11, None, 13]
  
# Building the binary tree
binary_tree = build(nodes)
print('Binary tree from list :\n',
      binary_tree)
  
# Getting list of nodes from
# binarytree
print('\nList from binary tree :', 
      binary_tree.values)

Producción:

Binary tree from list :

    ___3
   /    \
  6      8
 / \      \
2   11     13


List from binary tree : [3, 6, 8, 2, 11, None, 13]

Construye un árbol binario aleatorio:

tree() genera un árbol binario aleatorio y devuelve su Node raíz.
 

Sintaxis: binarytree.tree(height=3, is_perfect=False)
Parámetros: 
height: Es la altura del árbol y su valor puede estar entre el rango 0-9 (inclusive) 
is_perfect: Si se establece en True, se crea un binario perfecto.
Devuelve: Node raíz del árbol binario. 
 

Ejemplo:

from binarytree import tree
  
  
# Create a random binary 
# tree of any height
root = tree()
print("Binary tree of any height :")
print(root)
  
# Create a random binary 
# tree of given height
root2 = tree(height = 2)
print("Binary tree of given height :")
print(root2)
  
# Create a random perfect 
# binary tree of given height
root3 = tree(height = 2,
             is_perfect = True)
print("Perfect binary tree of given height :")
print(root3)

Producción: 

Binary tree of any height :

      14____
     /      \
    2        5__
   /        /   \
  6        1     13
 /        /     /  \
7        9     4    8

Binary tree of given height :

  1__
 /   \
5     2
     / \
    4   3

Perfect binary tree of given height :

    __3__
   /     \
  2       4
 / \     / \
6   0   1   5

Construyendo un BST:

El árbol de búsqueda binaria es un tipo especial de estructura de datos de árbol cuyo orden da una lista ordenada de Nodes o vértices. En Python, podemos crear directamente un objeto BST usando el módulo binarytree. bst() genera un árbol de búsqueda binario aleatorio y devuelve su Node raíz.
 

Sintaxis: binarytree.bst(height=3, is_perfect=False)
Parámetros: 
height: Es la altura del árbol y su valor puede estar entre el rango 0-9 (inclusive) 
is_perfect: Si se establece en True, se crea un binario perfecto.
Devuelve: Node raíz del BST. 
 

Ejemplo:

from binarytree import bst
  
  
# Create a random BST 
# of any height
root = bst()
print('BST of any height : \n',
      root)
  
# Create a random BST of 
# given height
root2 = bst(height = 2)
print('BST of given height : \n',
      root2)
  
# Create a random perfect 
# BST of given height
root3 = bst(height = 2, 
            is_perfect = True)
print('Perfect BST of given height : \n',
      root3)

Producción:

BST of any height : 

        ____9______
       /           \
    __5__       ____12___
   /     \     /         \
  2       8   10         _14
 / \     /      \       /
1   4   7        11    13

BST of given height : 

    5
   / \
  4   6
 /
3

Perfect BST of given height : 

    __3__
   /     \
  1       5
 / \     / \
0   2   4   6

Montón de importación:

Heap es una estructura de datos de árbol que puede ser de dos tipos: 

• montón máximo 
• montón mínimo 
   

Usando el método heap() de la biblioteca binarytree, podemos generar un maxheap aleatorio y devolver su Node raíz. Para generar minheap, debemos establecer el atributo is_max como falso.
 

Sintaxis: binarytree.heap(height=3, is_max=True, is_perfect=False)
Parámetros: 
height: Es la altura del árbol y su valor puede estar entre el rango 0-9 (inclusive) 
is_max: Si se establece True genera un montón máximo más montón mínimo. 
is_perfect: si se establece en True, se crea un binario perfecto.
Devuelve: Node raíz del montón. 
  

from binarytree import heap
  
  
# Create a random max-heap
root = heap()
print('Max-heap of any height : \n',
      root)
  
# Create a random max-heap
# of given height
root2 = heap(height = 2)
  
print('Max-heap of given height : \n',
      root2)
  
# Create a random perfect 
# min-heap of given height
root3 = heap(height = 2, 
             is_max = False, 
             is_perfect = True)
  
print('Perfect min-heap of given height : \n',
      root3)

Producción:

Max-heap of any height : 

         _______14______
        /               \
    ___12__            __13__
   /       \          /      \
  10        8        3        9
 /  \      / \      / \      /
1    5    4   6    0   2    7

Max-heap of given height : 

    __6__
   /     \
  4       5
 / \     / \
2   0   1   3

Perfect min-heap of given height : 

    __0__
   /     \
  1       3
 / \     / \
2   6   4   5