如何二叉樹

Question

找到最大值必須完成的方法maxElem（節點節點），該方法maxElem（）返回最大值包含在二叉樹這樣的方式。

我該怎麼做？我不知道該怎麼做..

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

} 

非常感謝！

Answer 1

嘗試：

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

Answer 2

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

Answer 3

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

Answer 4

）使用遞歸：

注意：您需要添加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 
    } 

）可以使用廣度優先遍歷的概念找到最大。

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