programa en C ++ para comprobar si un determinado árbol de búsqueda binaria es equilibrada o no?

Aquí, vamos a implementar un programa de C ++ que comprobará si hay un árbol de búsqueda binaria dado es un árbol equilibrado o no?

Descripción: Solución para comprobar la dada árbol de búsqueda binaria es equilibrada o no.

Planteamiento del problema: Escribir un programa que acepte la entrada del usuario para formar un árbol de búsqueda binaria y comprobación de si el árbol está equilibrado formado o no .

Ejemplo 1:

de entrada: 2 1 3 4 5 -1

salida: Dada BST está equilibrado: Falso

Ejemplo 2:

de entrada: 2 1 3 4 -1

de salida: Dado BST está equilibrado: la verdadera

Explicación …

¿Qué quiere decir por la altura de un árbol?

una altura de un árbol es el mayor número de bordes en una trayectoria de nodo a un nodo hoja. Si un árbol tiene sólo un nodo: es decir, nodo raíz en sí entonces la altura de árbol es 0.

Ejemplo:

Altura del tronco: 2 (máximo 2 bordes de la raíz a la hoja)

Comprobar cuando el árbol está equilibrado: se dice

Un árbol binario de búsqueda que no esté vacía a ser equilibrado si: se equilibra

1. su subárbol izquierdo.
2. su subárbol derecho se equilibra.
3. La diferencia entre las alturas de subárbol izquierdo y derecho es de menos de o igual a 1.

Ejemplo:

A la altura de la raíz del subárbol izquierdo es 1, mientras que la altura de subárbol derecho es 3

Diferencia = 3-1 = 2 (que es mayor que 1), es decir árbol no está equilibrada.

Algoritmo:

1. Conjunto root = raíz del árbol de búsqueda binaria dada.
2. Conjunto leftHt = altura del subárbol izquierdo.
3. Conjunto rightHt = altura del subárbol derecho.
4. si abs (leftHt – rightHt)> 1
   class false;
   demás isHeightBalanced (Raíz> izquierda) && isHeightBalanced (Raíz> derecha)

C ++ Code

#include <iostream>
  #include <cmath>
  using namespace std;
  class TreeNode {
      public:
          int data;
          TreeNode* left;
          TreeNode* right;
          TreeNode(int d) {
              data = d;
              left = NULL;
              right = NULL;
          }
  };
  TreeNode* insertInBST(TreeNode* root, int x) {
      if (root == NULL) {
          TreeNode* tmp = new TreeNode(x);
      return tmp;
  }
  if (x < root->data) {
      root->left = insertInBST(root->left , x);
          return root;
      } else {
          root->right = insertInBST(root->right, x);
          return root;
      }
  }
  TreeNode* createBST() {
      TreeNode* root = NULL;
      int x;
      cin >> x;
      //Take input until user inputs -1
      while (true) {
          if (x == -1) break;
          root = insertInBST(root, x);
          cin >> x;
      }
      return root;
  }
  //Calculate height of tree with given root
  int height(TreeNode* root) {
      if (root == NULL) return 0;
      int leftHt = height(root->left);
      int rightHt = height(root->right);
      int curHt = max(leftHt, rightHt) + 1;
      return curHt;
  }
  //Check whether tree is balanced or not
  bool isHeightBalanced(TreeNode* root) {
      if (!root) {
          return true;
      }
      int leftHt = height(root->left);
      int rightHt = height(root->right);
      if (abs(leftHt - rightHt) > 1) 
              return false;
      return isHeightBalanced(root->left) && isHeightBalanced(root->right);
  }
  int main() {
      //Input BST
      cout<<"Input Tree elements : ";
      TreeNode* root = createBST();
      cout << "Given BST is Balanced : ";
      if (isHeightBalanced(root)) {
          cout << "True";
      }
      else {
          cout << "False";
      }
      return 0;
  }
  

salida

First run:
  Input Tree elements(stop taking input when  -1 encountered) : 2 1 3 4 5 -1
  Given BST is Balanced : False
  Second run:
  Input Tree elements(stop taking input when  -1 encountered) : 2 1 3 4  -1
  Given BST is Balanced : True