Java查找树中最小的元素
用于查找树中最小元素的Java程序
在此程序中，我们将找出给定二叉树中的最小节点。我们首先定义变量min，它将保存根的数据。然后，我们遍历左子树以找到左子树中的最小节点。将其与最小值进行比较，并在变量min中存储最小值2。然后，我们遍历右子树以找到最小的节点，并将其与min进行比较。最后，min将具有最小的节点。
上图表示一棵二叉树。最初，min将保持4。通过左子树递归。
1. min = 4, leftMin = 2 =>
(2 < 4) then min = 2
2. min = 2, leftMin = 1 =>
(1 < 2) then min = 1
通过右子树递归。
1. min = 1, rightMin = 3 =>
(1 < 3) then min = 1
2. Recurse in left subtree of 5
3. min = 1, leftMin = 5 =>
(1 < 5) then min = 1
在3的右子树中递归
1. min = 1, rightMin = 6 =>
(1 < 6) then min = 1
因此，上述二叉树中的最小节点为1。
算法
定义Node类，它具有三个属性，即: data，left和right。在这里，左代表节点的左子节点，右代表节点的右子节点。
创建节点后，数据将传递到该节点的data属性，并且左右都将设置为null。
定义另一个具有属性根的类。 根表示树的根节点，并将其初始化为空。
a.minimumElement()将找出二叉树中的最小节点:
它检查root是否为空，这意味着树为空。
如果树不为空，请定义一个变量min，该变量将存储临时数据。
通过递归调用minimumElement()找出左子树中的最小节点。将该值存储在leftMin中。将min的值与leftMin进行比较，并将最小值2存储到min。
通过递归调用smallestElement()找出右侧子树中的最小节点。将该值存储在rightMin中。将min的值与rightMin进行比较，并将最大值2存储到min。
最后，min将保留二叉树中的最小节点。
程序:
public class SmallestNode {
//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 SmallestNode(){
root = null;
}
//smallestElement() will find out the smallest node in the binary tree
public int smallestElement(Node temp){
//Check whether tree is empty
if(root == null) {
System.out.println("Tree is empty");
return 0;
}
else {
int leftMin, rightMin;
//Min will store temps data
int min = temp.data;
//It will find smallest element in left subtree
if(temp.left != null){
leftMin = smallestElement(temp.left);
//if min is greater than leftMin then store the value of leftMin into min
min = Math.min(min, leftMin);
}
//It will find smallest element in right subtree
if(temp.right != null){
rightMin = smallestElement(temp.right);
//if min is greater than rightMin then store the value of rightMin into min
min = Math.min(min, rightMin);
}
return min;
}
}
public static void main(String[] args) {
SmallestNode bt = new SmallestNode();
//Add nodes to the binary tree
bt.root = new Node(4);
bt.root.left = new Node(2);
bt.root.right = new Node(3);
bt.root.left.left = new Node(1);
bt.root.right.left = new Node(5);
bt.root.right.right = new Node(6);
//Display smallest node in the binary tree
System.out.println("Smallest element in the binary tree: " + bt.smallestElement(bt.root));
}
}
输出:
Smallest element in the binary tree: 1
