查找二叉树中最小元素的Java程序

1 简介

在此程序中，我们将找出给定二叉树中的最小节点。我们首先定义变量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。

2 算法思路

• 定义Node类，它具有三个属性，即：data，left和right。在此，左代表节点的左子节点，右代表节点的右子节点。
• 创建节点时，数据将传递到该节点的data属性，并且左右都将设置为null。
• 定义另一个具有属性根的类。
  • 根表示树的根节点，并将其初始化为null。
• 它检查root是否为空，这意味着树为空。
• 如果tree不为空，则定义一个变量min，该变量将存储临时数据。
• 通过递归调用minimumElement（）找出左子树中的最小节点。将该值存储在leftMin中。将min的值与leftMin进行比较，并将最小值2存储到min。
• 通过递归调用smallestElement（）找出右侧子树中的最小节点。将该值存储在rightMin中。将min的值与rightMin进行比较，并将最大值2存储到min。
• 最后，min将保留二叉树中的最小节点。

3 程序实现

/**
 * 一点教程网： http://www.yiidian.com
 */
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 temp's 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