问：查找树的最大深度或高度的程序

2025年3月17日 | 阅读 7 分钟

说明

在这个程序中，我们需要找出二叉树的最大高度。二叉树的高度可以定义为根节点到叶子节点的节点数。最大高度将是根节点和最深叶子节点之间的层数。为了解决这个问题，我们遍历左子树并计算左子树的高度。再次，通过遍历右子树来计算右子树的高度。最大高度将是左子树高度和右子树高度中的最大值。

Program to find the maximum depth or height of a tree

在上面的二叉树中，

左子树的高度为 2。
右子树的高度为 4。
MaxHeight = Max(leftHeight, rightHeight) + 1；这里，1 代表根节点的高度

给定二叉树的最大高度为 (4 + 1) = 5，用白色虚线表示。

算法

定义 Node 类，它有三个属性：data、left 和 right。其中，left 表示节点的左子节点，right 表示节点的右子节点。
创建节点时，数据将传递到节点的 data 属性，left 和 right 都将设置为 null。
定义另一个类，该类有一个 root 属性。
1. Root 表示树的根节点，并将其初始化为 null。
findHeight() 将确定二叉树的最大高度
1. 它检查 root 是否为 null，这意味着树是空的。
2. 如果树不为空，则遍历左子树以确定左子树的高度并将其值存储在 leftHeight 中。
3. 类似地，确定右子树的高度并将其值存储在 rightHeight 中。
4. Maximum 将确定 leftHeight 和 rightHeight 中的最大值，然后加 1 作为根节点的高度。

解决方案

Python

#Represent a node of binary tree
class Node:
    def __init__(self,data):
        #Assign data to the new node, set left and right children to None
        self.data = data;
        self.left = None;
        self.right = None;
 
class BinaryTree:
    def __init__(self):
        #Represent the root of binary tree
        self.root = None;
    
    #findHeight() will determine the maximum height of the binary tree
    def findHeight(self, temp):
        #Check whether tree is empty
        if(self.root == None):
            print("Tree is empty");
            return 0;
        else:
            leftHeight = 0;
            rightHeight = 0;
            
            #Calculate the height of left subtree
            if(temp.left != None):
                leftHeight = self.findHeight(temp.left);
                
            #Calculate the height of right subtree
            if(temp.right != None):
                rightHeight = self.findHeight(temp.right);
            
            #Compare height of left subtree and right subtree 
            #and store maximum of two in variable max
            maximum = leftHeight if (leftHeight > rightHeight) else rightHeight;
            
            #Calculate the total height of the tree by adding the height of the root
            return (maximum + 1);
 
bt = BinaryTree();
#Add nodes to the binary tree
bt.root = Node(1);
bt.root.left = Node(2);
bt.root.right = Node(3);
bt.root.left.left = Node(4);
bt.root.right.left = Node(5);
bt.root.right.right = Node(6);
bt.root.right.right.right= Node(7);
bt.root.right.right.right.right = Node(8);
 
#Display the maximum height of the given binary tree
print("Maximum height of given binary tree: " + str(bt.findHeight(bt.root)));

输出

Maximum height of given binary tree: 5

C

#include <stdio.h>
#include <stdlib.h>
 
//Represent a node of binary tree
struct node{
    int data;
    struct node *left;
    struct node *right;
};
 
//Represent the root of binary tree
struct node *root = NULL;
 
//createNode() will create a new node
struct node* createNode(int data){
    //Create a new node
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    //Assign data to newNode, set left and right children to NULL
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    
    return newNode;
}
 
//findHeight() will determine the maximum height of the binary tree
int findHeight(struct node *temp){
    //Check whether tree is empty
    if(root == NULL) {
        printf("Tree is empty\n");
        return 0;
    }
    else {
        int leftHeight = 0, rightHeight = 0;
        
        //Calculate the height of left subtree
        if(temp->left != NULL)
            leftHeight = findHeight(temp->left);
        
        //Calculate the height of right subtree
        if(temp->right != NULL)
            rightHeight = findHeight(temp->right);
        
        //Compare height of left subtree and right subtree 
        //and store maximum of two in variable max
        int max = (leftHeight > rightHeight) ? leftHeight : rightHeight;
        
        //Calculate the total height of tree by adding height of root
        return (max + 1);
    }
}
 
int main()
{
    //Add nodes to the binary tree
    root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->right->left = createNode(5);
    root->right->right = createNode(6);
    root->right->right->right= createNode(7);
    root->right->right->right->right = createNode(8);
    
    //Display the maximum height of the given binary tree
    printf("Maximum height of given binary tree: %d", findHeight(root));
    return 0;
}

输出

Maximum height of given binary tree: 5

JAVA

public class BinaryTree {
    
    //Represent the node of binary tree
    public static class Node{
        int data;
        Node left;
        Node right;
        
        public Node(int data){
            //Assign data to the new node, set left and right children to null
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }
    
    //Represent the root of binary tree
    public Node root;
    public BinaryTree(){
        root = null;
    }
  
    //findHeight() will determine the maximum height of the binary tree
    public int findHeight(Node temp){
        //Check whether tree is empty
        if(root == null) {
             System.out.println("Tree is empty");
            return 0;
        }
        else {
            int leftHeight = 0, rightHeight = 0;
            
            //Calculate the height of left subtree
            if(temp.left != null)
                leftHeight = findHeight(temp.left);
            
            //Calculate the height of right subtree
            if(temp.right != null)
                rightHeight = findHeight(temp.right);
            
            //Compare height of left subtree and right subtree 
            //and store maximum of two in variable max
            int max = (leftHeight > rightHeight) ? leftHeight : rightHeight;
            
            //Calculate the total height of tree by adding height of root
            return (max + 1);
        }
     }
    
    public static void main(String[] args) {
    
        BinaryTree bt = new BinaryTree();
        //Add nodes to the binary tree
        bt.root = new Node(1);
        bt.root.left = new Node(2);
        bt.root.right = new Node(3);
        bt.root.left.left = new Node(4);
        bt.root.right.left = new Node(5);
        bt.root.right.right = new Node(6);
        bt.root.right.right.right= new Node(7);
        bt.root.right.right.right.right = new Node(8);
    
        //Display the maximum height of the given binary tree
        System.out.println("Maximum height of given binary tree: " + bt.findHeight(bt.root));
  }
}

输出

Maximum height of given binary tree: 5

C#

using System;
namespace Tree 
{                     
    public class Program
    {
        //Represent a node of binary tree
        public class Node<T>{
            public T data;
            public Node<T> left;
            public Node<T> right;
            
            public Node(T data) {
                //Assign data to the new node, set left and right children to null
                this.data = data;
                this.left = null;
                this.right = null;
            }
        }
        
        public class BinaryTree<T> where T : IComparable<T>{
            //Represent the root of binary tree
            public Node<T> root;
 
            public static Boolean flag = false;
 
            public BinaryTree(){
                root = null;
            }
        
        //findHeight() will determine the maximum height of the binary tree
        public int findHeight(Node<T> temp){
            //Check whether tree is empty
            if(root == null) {
                 Console.WriteLine("Tree is empty");
                return 0;
            }
            else {
                int leftHeight = 0, rightHeight = 0;
 
                //Calculate the height of left subtree
                if(temp.left != null)
                    leftHeight = findHeight(temp.left);
 
                //Calculate the height of right subtree
                if(temp.right != null)
                    rightHeight = findHeight(temp.right);
 
                //Compare height of left subtree and right subtree 
                //and store maximum of two in variable max
                int max = (leftHeight > rightHeight) ? leftHeight : rightHeight;
 
                //Calculate the total height of tree by adding height of root
                return (max + 1);
            }
        }
    }    
        public static void Main()
        {
            BinaryTree<int> bt = new BinaryTree<int>();
            //Add nodes to the binary tree
            bt.root = new Node<int>(1);
            bt.root.left = new Node<int>(2);
            bt.root.right = new Node<int>(3);
            bt.root.left.left = new Node<int>(4);
            bt.root.right.left = new Node<int>(5);
            bt.root.right.right = new Node<int>(6);
            bt.root.right.right.right= new Node<int>(7);
            bt.root.right.right.right.right = new Node<int>(8);
        
            //Display the maximum height of the given binary tree
            Console.WriteLine("Maximum height of given binary tree: " + bt.findHeight(bt.root));            
        }    
    }
}

输出

Maximum height of given binary tree: 5

PHP

<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of binary tree
class Node{
    public $data;
    public $left;
    public $right;
    
    function __construct($data){
        //Assign data to the new node, set left and right children to NULL
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class BinaryTree{
    //Represent the root of binary tree
    public $root;
    function __construct(){
        $this->root = NULL;
    }
    
    //findHeight() will determine the maximum height of the binary tree
    function findHeight($temp){
        //Check whether tree is empty
        if($this->root == null) {
             print "Tree is empty <br>";
            return 0;
        }
        else {
            $leftHeight = 0;
            $rightHeight = 0;
            //Calculate the height of left subtree
            if($temp->left != NULL)
                $leftHeight = $this->findHeight($temp->left);
            
            //Calculate the height of right subtree
            if($temp->right != NULL)
                $rightHeight = $this->findHeight($temp->right);
            
            //Compare height of left subtree and right subtree 
            //and store maximum of two in variable max
            $max = ($leftHeight > $rightHeight) ? $leftHeight : $rightHeight;
            
            //Calculate the total height of tree by adding height of root
            return ($max + 1);
        }
     }
}
$bt = new BinaryTree();
//Add nodes to the binary tree
$bt->root = new Node(1);
$bt->root->left = new Node(2);
$bt->root->right = new Node(3);
$bt->root->left->left = new Node(4);
$bt->root->right->left = new Node(5);
$bt->root->right->right = new Node(6);
$bt->root->right->right->right= new Node(7);
$bt->root->right->right->right->right = new Node(8);
    
//Display the maximum height of the given binary tree
print "Maximum height of given binary tree: " . $bt->findHeight($bt->root);
?>
</body>
</html>

输出

Maximum height of given binary tree: 5

下一个主题程序列表

问：查找树的最大深度或高度的程序

说明

算法

解决方案

Python

C

JAVA

C#

PHP

联系信息

关注我们

教程

面试题

在线编译器

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

程序

问：查找树的最大深度或高度的程序

说明

算法

解决方案

Python

C

JAVA

C#

PHP

相关帖子

编写查找四面体（Tetrahedron）体积的程序

打印图案 3 的程序

在单链表中搜索元素的程序

计算二叉树奇数层和偶数层节点之和差的程序

不使用模运算符打印数字之和的程序

将英尺转换为英寸的程序

在双向链表中搜索元素的程序

编写查找三棱柱（Triangular Prism）表面积的程序

根据给定坐标查找三角形类型的程序

计算矩形面积的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器