Comment trouver la valeur max dans un arbre binaire

J'ai pour valider la méthode maxElem(Nœud) de telle manière que la méthode maxElem() retourne la valeur maximale contenue dans un arbre binaire.

Comment puis-je le faire? Je ne sais pas comment faire..

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) {
//...
}
}

Merci beaucoup!

InformationsquelleAutor Katherine Maurus | 2014-04-19
  1. 11

    Essayer:

    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;
}
    • Car cela ressemble à des devoirs à faire, je pense qu'il serait plus appropriée pour expliquer le principe de la récursivité à pied à travers l'arbre que juste de lui donner le code.
    InformationsquelleAutor Jean Logeart
  2. 1

    1)À L'Aide De La Récursivité:

    Note:Vous avez besoin de l'ajouter getElement(), getRight(), getLeft() méthodes dans votre Nœud classe de façon à ce que le code ci-dessous pourrait fonctionner.

    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), Vous pouvez utiliser le concept de Largeur de la Première Traversée de pour trouver le max.

    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
}
}
    InformationsquelleAutor Prateek Joshi
  3. 0

    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);
    }

    InformationsquelleAutor ravi ranjan
  4. 0
        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;
}
    InformationsquelleAutor Harel Danieli