Encontrar la altura (profundidad máxima) de un árbol de búsqueda binaria (programa C ++)

aprender: Cómo encontrar la altura o profundidad máxima de un árbol de búsqueda binaria ? En este artículo se incluye la definición, el algoritmo y la implementación de programa en C ++.

La Altura (o profundidad) de un árbol se define como el nivel máximo de cualquier nodo en el árbol . Algunos autores definen la profundidad de un nodo a ser la longitud de la trayectoria más larga desde el nodo raíz a ese nodo, que da la relación:

profundidad del árbol = altura del árbol – 1

Referencia: http : //codersmaze.com/data-structure-explanations/trees-in-data-structure/

Algoritmo:

FindHeight( Node root)
If root=NULL
return 0
Else
int l=FindHeight (root->left)
int r=FindHeight(root->right)
Return max(l,r)+1
[End If]
[End]

Considere el programa:

#include<iostream>
using namespace std;
struct node
{
int data;
node* left;
node* right;
};
struct node* getNode(int data)
{
node* newNode=new node();
newNode->data=data;
newNode->left=NULL;
newNode->right=NULL;
return newNode;
}
void inorder(struct node* root)
{
if (root != NULL)
{
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
struct node* Insert(struct node* root, int data)
{
if (root == NULL)
return getNode(data);
if (data < root->data)
root->left = Insert(root->left, data);
else if (data > root->data)
root->right = Insert(root->right, data);
return root;
}
int FindHeight(node* root)
{
if(root==NULL)
return 0;
else
{
int lb=FindHeight(root->left);
int rb=FindHeight(root->right);
return max(lb,rb)+1;
}
}
int main()
{
node* root=NULL;
root=Insert(root,7);
Insert(root,9);
Insert(root,4);
Insert(root,1);
Insert(root,5);
cout<<"Inorder: ";
inorder(root);
cout<<endl;
cout<<"Height of the tree is "<<FindHeight(root)<<endl;
cout<<"Max. Depth of the tree is "<<FindHeight(root)-1;
return 0;
}

salida

Inorder: 14579
Height of the tree is 3
Max. Depth of the tree is 2


Deja un comentario

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