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

1 简介

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

2 算法思路

• 定义类Node，它具有三个属性，分别是：data，left和right。在此，左代表节点的左子节点，右代表节点的右子节点。
• 为节点的数据部分分配适当的值，并将left和right分配为null。
• 定义另一个具有属性根的类。
  • 根表示初始化为null的树的根节点。
  • maximumElement（）将找出二叉树中的最大节点：
  • 它检查根是否为空，这意味着树为空。
  • 如果树不为空，则定义一个变量max，该变量将存储temp的数据。
  • 通过递归调用largeElement（）找出左侧子树中的最大节点。将该值存储在leftMax中。将max的值与leftMax进行比较，并将最大值2存储为max。
  • 通过递归调用largeElement（）找出右侧子树中的最大节点。将该值存储在rightMax中。将max的值与rightMax进行比较，并将最大值2存储为max。
  • 最后，max将保留二叉树中最大的节点。

3 程序实现

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