Java在二叉树中找到最大的元素
在此程序中，我们将在给定的二进制树中找到最大的节点。我们首先定义将保存根数据的变量max。然后，我们遍历左侧的子树以找到最大的节点。将其与max进行比较，并将最大值2存储在变量max中。然后，我们遍历右侧子树以找到最大的节点，并将其与max进行比较。最后，max将具有最大的节点。
上图表示二进制树。最初，max将保留15。通过左子树递归。
1. max = 15, leftMax = 20 =>
(20 > 15) then max = 20
2. max = 20, leftMax = 74 =>
(74 > 20) then max = 74
通过右子树递归。
1. max = 74, rightMax = 35 =>
(74 > 35) then max = 74
在35的左子树中递归
1. max = 74, leftMax = 55 =>
(74 > 55) then max = 74
在35的右子树中递归
1. max = 74, rightMax = 6 =>
(74 > 6) then max = 74
因此，上述二叉树中的最大节点为74。
算法
定义类Node，它具有三个属性，即: data，left和right。在这里，左代表节点的左子节点，右代表节点的右子节点。
为节点的数据部分分配适当的值，并将left和right分配为null。
定义另一个具有属性根的类。 根表示树的根节点，该节点已初始化为空。 largestElement()将找出二叉树中最大的节点: 它检查根是否为空，这意味着树为空。 如果树不为空，请定义一个变量max，该变量将存储临时数据。 通过递归调用largeElement()找出左子树中的最大节点。将该值存储在leftMax中。将max的值与leftMax进行比较，并将最大值中的两个存储为max。 通过递归调用largeElement()找出右侧子树中的最大节点。将该值存储在rightMax中。将max的值与rightMax进行比较，并将最大值2存储为max。 最后，max将保留二叉树中最大的节点。
程序:
public class LargestNode {
//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 LargestNode(){
root = null;
}
//largestElement() will find out the largest node in the binary tree
public int largestElement(Node temp){
//Check whether tree is empty
if(root == null) {
System.out.println("Tree is empty");
return 0;
}
else{
int leftMax, rightMax;
//Max will store temps data
int max = temp.data;
//It will find largest element in left subtree
if(temp.left != null){
leftMax = largestElement(temp.left);
//Compare max with leftMax and store greater value into max
max = Math.max(max, leftMax);
}
//It will find largest element in right subtree
if(temp.right != null){
rightMax = largestElement(temp.right);
//Compare max with rightMax and store greater value into max
max = Math.max(max, rightMax);
}
return max;
}
}
public static void main(String[] args) {
LargestNode bt = new LargestNode();
//Add nodes to the binary tree
bt.root = new Node(15);
bt.root.left = new Node(20);
bt.root.right = new Node(35);
bt.root.left.left = new Node(74);
bt.root.right.left = new Node(55);
bt.root.right.right = new Node(6);
//Display largest node in the binary tree
System.out.println("Largest element in the binary tree: " + bt.largestElement(bt.root));
}
}
输出:
Largest element in the binary tree: 74
