二叉树的高度

2025年03月17日 | 阅读 9 分钟

二叉树的高度或深度可以定义为从叶节点到根节点，或从根节点到叶节点的最大边数。根节点位于第零层，这意味着如果根节点没有任何子节点与之连接，则该二叉树的高度或深度为零。

让我们举一个例子来更好地理解二叉树的高度。

在上图中，我们有一个从名为 A 的根节点开始的二叉树。根节点 A 有两个子节点 B 和 C，分别是左子节点和右子节点。类似地，左子节点 B 只有一个名为 D 的左子节点，而右子节点 C 有两个子节点 E 和 F，其中节点 E 只有一个名为 G 的左子节点。

现在让我们来计算这棵二叉树的高度。要计算二叉树的高度，需要计算从根节点到最深叶节点的边数。这棵二叉树中最深的节点是 G。因此，为了计算这棵二叉树的高度或深度，我们需要计算根节点和最深节点 G 之间的边数。第一条边是从节点 A 到节点 C，第二条边是从节点 C 到节点 E，第三条边是从节点 E 到节点 G。所以，从根节点 A 遍历到最深节点 G 共有三条边，因此该二叉树的高度或深度为 3。我们从根节点到最深叶节点的路径是 A > C > E > G，这条路径在遍历过程中经过了三条边，这就是为什么根据二叉树高度的定义，这棵二叉树的高度是 3。

计算二叉树高度的方法

现在，让我们编写代码来计算二叉树的高度。有两种方法可以计算二叉树的高度。一种是**递归法**，另一种是**非递归法**，它将使用队列数据结构来计算二叉树的高度。

递归方式

首先，让我们看一下用递归方式计算二叉树的高度。

代码

// Java program to create and to find the height of a binary tree by recursive way
 
 
// util package is imported to use classes like Queue and LinkedList
import java.util.*;
 
 
 
// A class named Node is created representing a single node of a binary tree
class Node{
 
 
  // The class Node has three class variables named key and left and right of int type and Node type respectively.
 
 
  // the key variable holds the actual value that is assigned to that node of the binary tree
  int key;
 
  // left and right variables that are of Node type will be used to store the left and right child nodes of the parent of the binary tree
  Node left, right;
 
// a parameterized constructor is created to create and add data to the node at the same time.
  public Node(int item)
  {
    key = item;
    left = right = null;
  }
 
 }
// end of node class definition
 
// A public class named BinaryTree is created having two constructors and methods to print the binary tree level-wise.
 
class BinaryTree{
 
  // A static variable named root_node is created that will represent the node of the binary tree
  static Node root_node;
 
 
 
 
  // A parametrized constructor of the BinaryTree class is written having the key as a parameter
  BinaryTree(int key)
  {
 
// here we are constructing a new node and assigning it to the root node
    root_node = new Node(key);
  }
 
  BinaryTree()
  {
    root_node = null;
  }
 
 
 
// a public static function named print tree is created to print all the nodes in the tree level-wise starting from the root node 
 
 public static void printTree()
    {
        int h = height(root_node);
        int i;
        for (i=1; i<=h; i++){
            printCurrentLevel(root_node, i);
            System.out.println();
          }
    }
 

// a public static function named height is created to fund the height of the binary tree starting from the root node to the deepest leaf node that is present in the binary tree
 
// the root node of the binary tree is passed as a parameter to the public static function named height
// the height function is called recursively until the node returned is NULL to find the height of the binary tree
    public static int height(Node root){
        
        // the root is null then the height of the tree will be Zero
        if (root == null)
           return 0;
        else
        {
            /* compute  height of each subtree */
            int lheight = height(root.left);
            int rheight = height(root.right);
             
            /* use the larger one */
            // height of both the sub trees is calcualted and which one is higher is used. 
            if (lheight > rheight)
                return(lheight+1);
            else 
                return(rheight+1);
        }
    }
 
 
// a Public static function named printCurrentLevel is created to print al the nodes that are present in that level 
// this function is called repeatedly for each level of the binary tree to print all the nodes in that particular level 
 
   public static void printCurrentLevel (Node root ,int level)
    {
        if (root == null)
            return;
        if (level == 1)
            System.out.print(root.key + " ");
        else if (level > 1)
        {
            printCurrentLevel(root.left, level-1);
            printCurrentLevel(root.right, level-1);
        }
    }
 
 
//the main function is created to create an object of the BinaryTree class and call the printTree method to level-wise print the nodes of the binary tree and the height method to find the height of the binary tree
 
  public static void main(String[] args){
 
    
 
 
    // first of all we have created an Object of the BinaryTree class that will represent the binary tree
    BinaryTree tree = new BinaryTree();
 
 
    // now a new node with the value as 150 is added as the root node to the Binary Tree
    tree.root_node = new Node(150);
 
    // now a new node with the value 250 is added as a left child to the root node 
    tree.root_node.left = new Node(250);
 
    // now a new node with the value 270 is added as a right child to the root node 
    tree.root_node.right = new Node(270);
 
 
    // now a new node with the value 320 is added as a left child to the left node of the previous level node 
    tree.root_node.left.left = new Node(320);
 
 
    // now a new node with the value 350 is added as a right child to the right node of the previous level node
    tree.root_node.left.right = new Node(350);
 
    /* 
               150
        	/          \
       250         270
        /     \       /      \
      320 350  null  null
 
*/
 
 
 
    System.out.println("Printing the nodes of tree level wise :");
    System.out.println("Level order traversal : ");
    tree.printTree();
 
    // height of the binary tree is calculated bypassing the root as parameter to the height() function.
    int h = tree.height(tree.root_node)

    System.out.println("The height of the Binary tree is : " + h );

  }
}
// end of the BinaryTree class

输出：上述代码的输出是

Printing the nodes of tree level wise:
Level order traversal: 
(level 0) 150 
(level 1) 250 270 
(level 2) 320 350 

The height of the Binary tree is: 2

在递归方式中，我们重复调用 height() 函数来计算二叉树的高度。二叉树的根节点作为参数传递给 height() 函数。height() 函数计算根节点两个子树的高度，并将两者中较高的高度视为二叉树的高度。

非递归方式

现在让我们看一下用非递归方式计算二叉树的高度。

代码

// A C++ program to create and to find the height of a binary tree by non recursive way

// iostream header file is included to use the cin and cout objects of the istream and ostream classes respectively  
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// A struct named Node is created representing a single node of a binary tree
struct Node
{
    // The struct Node has three variables named key and left and right of int type and Node type respectively.
 
    // the key variable holds the actual value that is assigned to that node of the binary tree
	int key;


  // left and right variables that are of Node type will be used to store the left and right child nodes of the parent of the binary tree
	struct Node* left, *right;
};

// A Function named newNode is created to add a new node to the binary tree, the newNode function has one parameter of integer type named key that will represent the value that particular new node will be storing  
Node* newNode(int key)
{
	Node* temp = new Node;
	temp->key = key;
	temp->left = temp->right = NULL;
	return (temp);
}

// A function named height is created to find the height of the binary tree with non recursive way 
// The parameter to the height function is the root node of the binary tree that will be present at level zero
// In the height function the nodes of the binary tree are added into the Queue data structure and the depth variable is incremented until
// the NULL node is encountered while traversing the nodes of the binary tree stored in the Queue data structure.    
int height(struct Node* root){

	//Initialising a variable to count the
	//height of tree
	int depth = 0;

	queue<Node*>q;
	
	//Pushing first level element along with NULL
	q.push(root);
	q.push(NULL);
	while(!q.empty()){
		Node* temp = q.front();
		q.pop();
	
		//When NULL encountered, increment the value
		if(temp == NULL){
			depth++;
		}
		
		//If NULL not encountered, keep moving
		if(temp != NULL){
			if(temp->left){
				q.push(temp->left);
			}
			if(temp->right){
				q.push(temp->right);
			}
		}
	
		//If queue still have elements left,
		//push NULL again to the queue.
		else if(!q.empty()){
			q.push(NULL);
		}
	}
	return depth;
}


// Start of the main function
int main()
{
	// first of all we have created an Object of the struct Node that will represent the binary tree
	// the value of the root node is 10
    Node *root = newNode(10);

   // now a new node with the value 20 is added as a left child to the root node 
	root->left = newNode(20);
    // now a new node with the value 30 is added as a right child to the root node 
	root->right = newNode(30);

    // now a new node with the value 40 is added as a left child to the left node of the previous level node 
	root->left->left = newNode(40);
	// now a new node with the value 50 is added as a right child to the left node of the previous level node
    root->left->right = newNode(50);

      /* 
               10
        	 /          \
         20         30
        /     \       /      \
      40  50  null  null
 
*/



	cout<<"The Height(Depth) of tree is: "<<height(root);
    cout<<endl;
}
// end of the main function

输出

The Height(Depth) of the tree is: 2

在这种方法中，我们使用了非递归的方式来计算二叉树的深度。为了计算二叉树的高度，我们编写了一个名为 height 的函数，它需要一个 Node 类型的参数（即需要计算高度的二叉树的根节点）。二叉树的根节点位于第零层，这意味着根节点的高度或深度为零。

在非递归方法中，我们使用队列数据结构来计算二叉树的深度。我们想要计算深度的二叉树节点通过入队操作被添加到队列数据结构中，二叉树的节点作为参数传递给该函数。

一旦所有节点都添加到队列中，通过调用出队函数来移除队列中的节点，该函数会一直从队列中移除元素，直到遇到二叉树的空节点。每次从队列中移除一个二叉树节点时，代表二叉树深度的深度变量就会加一。最后，深度变量的值就代表了二叉树的最终深度。

下一个主题不使用栈的中序树遍历

二叉树的高度

计算二叉树高度的方法

递归方式

非递归方式

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

二叉树的高度

计算二叉树高度的方法

递归方式

非递归方式

相关帖子

打印 1 到 N，不使用循环

如何检查二进制数是否可被 3 整除

使用 Trie 实现自动完成功能

数据结构中的跳表

编程中的 FIFO vs LIFO 方法

检查一个队列是否可以使用一个栈排序到另一个队列

树-列表递归的伟大问题

数组中的最大平衡和

使用 DSU 检测图中的循环

ArrayList vs LinkedList

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器