Hay dos convenciones para definir la altura de un árbol binario
- Número de Nodes en el camino más largo desde la raíz hasta el Node más profundo.
- Número de aristas en el camino más largo desde la raíz hasta el Node más profundo.
En este post, se sigue la primera convención. Por ejemplo, la altura del árbol de abajo es 3.
C++
#include <iostream>
#include <queue>
using namespace std;
// This approach counts the number of nodes from root to the
// leaf to calculate the height of the tree.
// Defining the structure of a Node.
class Node {
public:
int data;
Node* left;
Node* right;
};
// Helper function to create a newnode.
// Input: Data for the newnode.
// Return: Address of the newly created node.
Node* createNode(int data)
{
Node* newnode = new Node();
newnode->data = data;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
// Function to calculate the height of given Binary Tree.
// Input: Address of the root node of Binary Tree.
// Return: Height of Binary Tree as a integer. This includes
// the number of nodes from root to the leaf.
int calculateHeight(Node* root)
{
queue<Node*> nodesInLevel;
int height = 0;
int nodeCount = 0; // Calculate number of nodes in a level.
Node* currentNode; // Pointer to store the address of a
// node in the current level.
if (root == NULL) {
return 0;
}
nodesInLevel.push(root);
while (!nodesInLevel.empty()) {
// This while loop runs for every level and
// increases the height by 1 in each iteration. If
// the queue is empty then it implies that the last
// level of tree has been parsed.
height++;
// Create another while loop which will insert all
// the child nodes of the current level in the
// queue.
nodeCount = nodesInLevel.size();
while (nodeCount--) {
currentNode = nodesInLevel.front();
// Check if the current nodes has left child and
// insert it in the queue.
if (currentNode->left != NULL) {
nodesInLevel.push(currentNode->left);
}
// Check if the current nodes has right child
// and insert it in the queue.
if (currentNode->right != NULL) {
nodesInLevel.push(currentNode->right);
}
// Once the children of the current node are
// inserted. Delete the current node.
nodesInLevel.pop();
}
}
return height;
}
// Driver Function.
int main()
{
// Creating a binary tree.
Node* root = NULL;
root = createNode(1);
root->left = createNode(2);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right = createNode(3);
cout << "The height of the binary tree using iterative "
"method is: " << calculateHeight(root) << ".";
return 0;
}
Java
// An iterative java program to find height of binary tree
import java.util.LinkedList;
import java.util.Queue;
// A binary tree node
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right;
}
}
class BinaryTree
{
Node root;
// Iterative method to find height of Binary Tree
int treeHeight(Node node)
{
// Base Case
if (node == null)
return 0;
// Create an empty queue for level order traversal
Queue<Node> q = new LinkedList();
// Enqueue Root and initialize height
q.add(node);
int height = 0;
while (1 == 1)
{
// nodeCount (queue size) indicates number of nodes
// at current level.
int nodeCount = q.size();
if (nodeCount == 0)
return height;
height++;
// Dequeue all nodes of current level and Enqueue all
// nodes of next level
while (nodeCount > 0)
{
Node newnode = q.peek();
q.remove();
if (newnode.left != null)
q.add(newnode.left);
if (newnode.right != null)
q.add(newnode.right);
nodeCount--;
}
}
}
// Driver program to test above functions
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
// Let us create a binary tree shown in above diagram
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("Height of tree is " + tree.treeHeight(tree.root));
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Program to find height of tree by Iteration Method
# A binary tree node
class Node:
# Constructor to create new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Iterative method to find height of Binary Tree
def treeHeight(root):
# Base Case
if root is None:
return 0
# Create a empty queue for level order traversal
q = []
# Enqueue Root and Initialize Height
q.append(root)
height = 0
while(True):
# nodeCount(queue size) indicates number of nodes
# at current level
nodeCount = len(q)
if nodeCount == 0 :
return height
height += 1
# Dequeue all nodes of current level and Enqueue
# all nodes of next level
while(nodeCount > 0):
node = q[0]
q.pop(0)
if node.left is not None:
q.append(node.left)
if node.right is not None:
q.append(node.right)
nodeCount -= 1
# Driver program to test above function
# Let us create binary tree shown in above diagram
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print ("Height of tree is", treeHeight(root))
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// An iterative C# program to
// find height of binary tree
using System;
using System.Collections.Generic;
// A binary tree node
class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right;
}
}
public class BinaryTree
{
Node root;
// Iterative method to find
// height of Binary Tree
int treeHeight(Node node)
{
// Base Case
if (node == null)
return 0;
// Create an empty queue
// for level order traversal
Queue<Node> q = new Queue<Node>();
// Enqueue Root and initialize height
q.Enqueue(node);
int height = 0;
while (1 == 1)
{
// nodeCount (queue size) indicates
// number of nodes at current level.
int nodeCount = q.Count;
if (nodeCount == 0)
return height;
height++;
// Dequeue all nodes of current
// level and Enqueue all
// nodes of next level
while (nodeCount > 0)
{
Node newnode = q.Peek();
q.Dequeue();
if (newnode.left != null)
q.Enqueue(newnode.left);
if (newnode.right != null)
q.Enqueue(newnode.right);
nodeCount--;
}
}
}
// Driver code
public static void Main(String []args)
{
BinaryTree tree = new BinaryTree();
// Let us create a binary
// tree shown in above diagram
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
Console.WriteLine("Height of tree is " +
tree.treeHeight(tree.root));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// An iterative javascript program to find height of binary tree
// A binary tree node
class Node
{
constructor(item)
{
this.data = item;
this.left = this.right=null;
}
}
let root;
// Iterative method to find height of Binary Tree
function treeHeight(node)
{
// Base Case
if (node == null)
return 0;
// Create an empty queue for level order traversal
let q = [];
// Enqueue Root and initialize height
q.push(node);
let height = 0;
while (1 == 1)
{
// nodeCount (queue size) indicates number of nodes
// at current level.
let nodeCount = q.length;
if (nodeCount == 0)
return height;
height++;
// Dequeue all nodes of current level and Enqueue all
// nodes of next level
while (nodeCount > 0)
{
let newnode = q.shift();
if (newnode.left != null)
q.push(newnode.left);
if (newnode.right != null)
q.push(newnode.right);
nodeCount--;
}
}
}
// Driver program to test above functions
// Let us create a binary tree shown in above diagram
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
document.write("Height of tree is " + treeHeight(root));
// This code is contributed by rag2127
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA