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
- su subárbol izquierdo.
- su subárbol derecho se equilibra.
- 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:
- Conjunto root = raíz del árbol de búsqueda binaria dada.
- Conjunto leftHt = altura del subárbol izquierdo.
- Conjunto rightHt = altura del subárbol derecho.
- 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