Java查找树的最大深度或高度
在此程序中，我们需要找出二叉树的最大高度。二叉树的高度可以定义为根与叶之间的节点数。最大高度将是根与最深叶之间的级别数。为了解决这个问题，我们遍历左子树并计算左子树的高度。同样，通过遍历右子树来计算其高度。最大高度将是左侧子树和右侧子树的最大高度。
在上述二叉树中，
Height of left subtree is 2.
Height of right subtree is 4.
MaxHeight = Max(leftHeight, rightHeight) + 1;
Here, 1 Represents root nodes height,
The maximum height of the given binary tree is (4 + 1) = 5 denoted by white dotted line.
算法
定义Node类，它具有三个属性，即: 左和右数据。在这里，左代表节点的左子节点，右代表节点的右子节点。
创建节点后，数据将传递到该节点的data属性，并且左右都将设置为null。
定义另一个具有属性根的类。 Root 表示树的根节点，并将其初始化为null。
a.findHeight()将确定二叉树的最大高度:
它检查根是否为空，这意味着树为空。
如果树不为空，请遍历左子树以确定左子树的高度，并将其值存储在leftHeight中。
类似地，确定右子树的高度并将其值存储在rightHeight中。
最大值将确定leftHeight和rightHeight的最大值，然后为根的高度加1。
程序:
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
