Convertir árbol binario en árbol binario de búsqueda

1. Algoritmo de conversión de árbol binario a BST
2. Convertir árbol binario en ilustración BST
3. Convertir árbol binario en BST Implementación
4. Convierta el árbol binario en la complejidad del algoritmo BST

Un árbol binario es una estructura de datos no lineal. Se llama árbol binario porque cada nodo tiene un máximo de dos hijos. Estos niños se llaman niños izquierdos y niños derechos. También se puede interpretar como un gráfico no dirigido en el que el nodo superior se llama raíz. Un árbol binario de búsqueda (BST) es un árbol binario con propiedades especiales que ayuda a mantener los datos organizados de forma ordenada.

En este tutorial, discutiremos cómo convertir un árbol binario a BST manteniendo la estructura original del árbol binario.

Algoritmo de conversión de árbol binario a BST

Convertir árbol binario en ilustración BST

Convertir árbol binario en BST Implementación

#include <bits/stdc++.h>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
vector<int> v;

void inorder(Node* root) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
  }
}

void storetree(Node* root, int i = 0) {
  if (!root) {
    return;
  }
  storetree(root->left);
  v.push_back(root->data);
  storetree(root->right);
}

void restoretree(Node* root, int& i) {
  if (!root) {
    return;
  }
  restoretree(root->left, i);
  root->data = v[i];
  i++;
  restoretree(root->right, i);
}

void converttoBST(Node* root) {
  if (!root) {
    return;
  }
  storetree(root);
  sort(v.begin(), v.end());
  int i = 0;
  restoretree(root, i);
}

int main() {
  Node* root = new Node(3);
  root->left = new Node(1);
  root->right = new Node(7);
  root->left->left = new Node(4);
  root->left->right = new Node(5);
  root->left->left->right = new Node(2);
  root->right->left = new Node(6);
  root->right->right = new Node(9);
  root->right->right->left = new Node(8);
  cout << "The inorder traversal of the tree is : ";
  inorder(root);
  cout << endl;
  converttoBST(root);
  cout << "The inorder traversal of the tree is : ";
  inorder(root);
  cout << endl;
}

Convierta el árbol binario en la complejidad del algoritmo BST

Complejidad del tiempo

• Caso promedio

La complejidad de tiempo de hacer el recorrido en orden en el que almacenamos el array en sorted y almacenamos el array sorted en el árbol binario es O(n). Pero, la complejidad de ordenar el array es O(nlogn) y, por lo tanto, la complejidad total se da como O(nlogn) + 2*O(n). La complejidad del tiempo es del orden de O(nlogn).

• Mejor caso

La complejidad del tiempo en el mejor de los casos es del orden de O(n). Cuando el árbol binario dado ya es una BST, hacemos el recorrido en orden para realizarlo y no se requieren operaciones de clasificación.

• Peor caso

La complejidad de tiempo en el peor de los casos es del orden de O(nlogn).

Complejidad espacial

La complejidad espacial del algoritmo es O(n) debido al espacio extra requerido por las llamadas recursivas.