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

C++ program to check whether a given Binary Search Tree is balanced or not? - 4

salida: Dada BST está equilibrado: Falso

Ejemplo 2:

de entrada: 2 1 3 4 -1

C++ program to check whether a given Binary Search Tree is balanced or not? - 5

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:

C++ program to check whether a given Binary Search Tree is balanced or not? - 6

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:

C++ program to check whether a given Binary Search Tree is balanced or not? - 7

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


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *