Recorrido del árbol de búsqueda binaria: en orden, preorden, orden posterior

Un árbol de búsqueda binaria o BST es un árbol binario donde cada Node a la izquierda de su raíz tiene un valor menor que la raíz, y cada Node a la derecha de la raíz tiene un valor mayor que la raíz. 

Para atravesar el BST utilizando DFS, existen tres métodos:

• Recorrido en orden
• Recorrido de pedido anticipado
• Recorrido posterior al pedido

Un árbol de búsqueda binaria

• Consideraremos el árbol anterior como un ejemplo de los recorridos.

Recorrido en orden: El recorrido en orden del BST da los valores de los Nodes en orden ordenado.

Paso 1: recorrer el subárbol izquierdo
Paso 2: visitar la raíz
Paso 3: recorrer el subárbol derecho

• Como primero visitamos el subárbol izquierdo, obtenemos el elemento más pequeño en el BST y luego visitamos la raíz, obteniendo así el segundo más pequeño en el subárbol y así sucesivamente. 
• Podemos visitar el subárbol derecho, raíz e izquierdo para obtener el orden decreciente.

A continuación se muestra la implementación del recorrido en orden.

// C++ code to implement the approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Class describing a node of tree
class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int v)
    {
        this->data = v;
        this->left = this->right = NULL;
    }
};
  
// Inorder Traversal
void printInorder(Node* node)
{
    if (node == NULL)
        return;
  
    // Traverse left subtree
    printInorder(node->left);
  
    // Visit node
    cout << node->data << " ";
  
    // Traverse right subtree
    printInorder(node->right);
}
  
// Driver code
int main()
{
    // Build the tree
    Node* root = new Node(100);
    root->left = new Node(20);
    root->right = new Node(200);
    root->left->left = new Node(10);
    root->left->right = new Node(30);
    root->right->left = new Node(150);
    root->right->right = new Node(300);
  
    // Function call
    cout << "Inorder Traversal: ";
    printInorder(root);
    return 0;
}

Inorder Traversal: 10 20 30 100 150 200 300 

Complejidad temporal: O(N), donde N es el número de Nodes.
Espacio Auxiliar: O(h), Donde h es la altura del árbol

Recorrido de pedido anticipado:

Paso 1: Visite la raíz
Paso 2: Atraviese el subárbol izquierdo
Paso 3: Atraviese el subárbol derecho

A continuación se muestra la implementación del recorrido de preorden.

// C++ code to implement the approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Class describing a node of tree
class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int v)
    {
        this->data = v;
        this->left = this->right = NULL;
    }
};
  
// Preorder Traversal
void printPreOrder(Node* node)
{
    if (node == NULL)
        return;
  
    // Visit Node
    cout << node->data << " ";
  
    // Traverse left subtree
    printPreOrder(node->left);
  
    // Traverse right subtree
    printPreOrder(node->right);
}
  
// Driver code
int main()
{
    // Build the tree
    Node* root = new Node(100);
    root->left = new Node(20);
    root->right = new Node(200);
    root->left->left = new Node(10);
    root->left->right = new Node(30);
    root->right->left = new Node(150);
    root->right->right = new Node(300);
  
    // Function call
    cout << "Preorder Traversal: ";
    printPreOrder(root);
    return 0;
}

Preorder Traversal: 100 20 10 30 200 150 300 

Complejidad temporal: O(N), donde N es el número de Nodes.
Espacio Auxiliar: O(h), Donde h es la altura del árbol

Recorrido posterior al pedido:

Paso 1: recorrer el subárbol izquierdo
Paso 2: recorrer el subárbol derecho
Paso 3: visitar el Node

A continuación se muestra la implementación del recorrido posterior al pedido.

// C++ code to implement the approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Class to define structure of a node
class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int v)
    {
        this->data = v;
        this->left = this->right = NULL;
    }
};
  
// PostOrder Traversal
void printPostOrder(Node* node)
{
    if (node == NULL)
        return;
  
    // Traverse left subtree
    printPostOrder(node->left);
  
    // Traverse right subtree
    printPostOrder(node->right);
  
    // Visit node
    cout << node->data << " ";
}
  
// Driver code
int main()
{
    Node* root = new Node(100);
    root->left = new Node(20);
    root->right = new Node(200);
    root->left->left = new Node(10);
    root->left->right = new Node(30);
    root->right->left = new Node(150);
    root->right->right = new Node(300);
  
    // Function call
    cout << "PostOrder Traversal: ";
    printPostOrder(root);
    cout << "\n";
  
    return 0;
}

PostOrder Traversal: 10 30 20 150 300 200 100 

Complejidad temporal: O(N), donde N es el número de Nodes.
Espacio Auxiliar: O(h), Donde h es la altura del árbol