Java 如何在二叉树中找到最大值

How to find max value in a binary tree

提问by

I have to complete the method maxElem(Node node)in such a way that the method maxElem()returns the maximum value contained in a binary tree.

我必须以方法maxElem()返回包含在二叉树中的最大值的方式完成方法maxElem(Node node)。

How can I do that? I do not know how to do that..

我怎样才能做到这一点？我不知道如何去做..

public class BinaryTree {

    protected class Node {
        protected Integer element;
        protected Node left;
        protected Node right;

        Node(int element) {
            this.element = element;
            left = right = null;
        }

        Node(int element, Node left, Node right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }

    } //end Node class

    public class NodeReference {
        private Node node;

        private NodeReference(Node node) {
            this.node = node;
        }

        public int getElement() {
            return node.element;
        }

        public void setElement(int e) {
            node.element = e;
        }
    }

    protected Node root;

    public BinaryTree() {
        root = null;
    }

    private class BoolNode {

        boolean found; 
        Node node;

        BoolNode(boolean found, Node node) {
            this.found = found;
            this.node = node;
        }
    }

    public int maxElem() {
        if(root == null) 
            throw new IllegalStateException("Empty tree.");
        return maxElem(root);
    }


    private static int max3(int x, int y, int z) {
        return max(x, max(y, z));
    }

    private int maxElem(Node node) {
        //...
    }

}

Thanks a lot!

非常感谢！

采纳答案by Jean Logeart

Try:

尝试：

private int maxElem(Node node) {
    int max = node.element;
    if(node.left != null) {
        max = Math.max(max, maxElem(node.left));
    }
    if(node.right != null) {
        max = Math.max(max, maxElem(node.right));
    }
    return max;
}

回答by ravi ranjan

public static void maxElement(Node node, int max){ static int MaxTemp; if(node==null) return; if(node.getData()>min) MaxTemp=node.getData(); if(node.getLeft()!=null && node.getLeft().getData()>max) MaxTemp=node.getLeft().getData(); if(node.getRight()!=null && node.getRight().getData()>max) MaxTemp=node.getRight().getData(); maxElement(node.getLeft(), MaxTemp); maxElement(node.getRight(), MaxTemp); }

public static void maxElement(Node node, int max){ static int MaxTemp; if(node==null) return; if(node.getData()>min) MaxTemp=node.getData(); if(node.getLeft()!=null && node.getLeft().getData()>max) MaxTemp=node.getLeft().getData(); if(node.getRight()!=null && node.getRight().getData()>max) MaxTemp=node.getRight().getData(); maxElement(node.getLeft(), MaxTemp); maxElement(node.getRight(), MaxTemp); }

回答by Harel Danieli

    public static int maxInTree(BinTreeNode<int> t)
    {
        int max = t.GetInfo();
        if (t != null)
        {
            if (t.GetLeft() != null)
                max = Math.Max(max, maxInTree(t.GetLeft()));
            if (t.GetRight() != null)
                max = Math.Max(max, maxInTree(t.GetRight()));
        }
        return max;
    }

回答by Prateek Joshi

1)Using Recursion:

1）使用递归：

Note:You need the add getElement(), getRight(), getLeft()methods in your Nodeclass so that the below code could work.

注意：您需要Node类中的 add getElement(), getRight(),getLeft()方法，以便下面的代码可以工作。

public int findMaxInTree(Node root) {
        int max = Integer.MIN_VALUE;     //set a default max value
        if (root == null)
            return max;                 //if root is null
        else {
            int left_max = findMaxInTree(root.getLeft());           //get left side max
            int right_max = findMaxInTree(root.getRight());         //get right side max
            if (left_max > right_max)                               //if left>right
                max = left_max;                                     //set max=left
            else
                max=right_max;                                      //else set max=right

            if (root.getElement() > max)                           //if root is greater than max of left or right
                max = root.getElement();                              //set max=root

        }
        return max;                                                //return max
    }

2)You can use the conceptof Breadth First Traversalto find the max.

2）你可以使用概念的广度优先遍历查找最大。

public void findMax(Node root) {
            if (root == null)
                System.out.println("empty tree");
            else {
                Queue<Node> queue = new LinkedList<Node>();  //make a queue
                Node max = root;                              //suppose max is root
                queue.add(root);                              //add root to queue
                while (queue.size() != 0) {                  //while size of queue is not empty  
                    Node temp = queue.remove();              //remove an item from queue
                    if (temp.getElement() > max.getElement())    //if removed item is greater than max
                        max = temp;                             //set new max
                    if (temp.getLeft() != null)                                  
                        queue.add(temp.getLeft());             //traverse left
                    if (temp.getRight() != null)
                        queue.add(temp.getRight());            //traverse right
                }
                System.out.println(max.getElement());       //in the end ,print the max
            }
        }

回答by Aryan Taneja

Here is one way you could get the maximum value of a tree.

这是获得树最大值的一种方法。

public static int maxElem(Node node) {
    if (node == null) {
        return Integer.MIN_VALUE;
    }

    int max = Math.max(maxElem(node.left), maxElem(node.right));
    return max > node.element ? max : node.element;
}