二叉樹：節點數量和子樹高度之間的最大值

我有一個定義二叉樹的java類。現在，我必須添加一個方法（ratio（）），該方法返回對節點的引用（或者對於其中一個節點，如果有多個節點），則使得子樹中節點數量（因此包括節點本身）並且子樹的高度被最大化。要做到這一點，我必須加起來1，否則葉的比例將是1/0 =無窮大。二叉樹：節點數量和子樹高度之間的最大值

我想我會定義一個公共方法來檢查這棵樹是否爲空，然後返回一個異常，否則它會調用一個私有方法來完成對這兩個子樹的所有工作。

但私有方法（如果這個過程是正確的）我不知道如何寫它。我也可以定義一個能夠幫助我完成這個任務的類，但是怎麼做？

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 NodeReference ratio() { 
    if(isEmpty()) //equals to if(root == null) 
      throw new IllegalStateException("Empty tree."); 
     else 
      ratio(root); 
} 

    private NodeReference ratio(Node node) { 
     //... 
    } 
}

任何人都可以幫助我嗎？感謝

來源

2014-04-20 user3425699

建議，任何想法？ – user3425699

讓我們閱讀的要求

...子樹的節點數...

你需要一個方法public int numberOfNodesInSubtree()

...和子樹的高度...

你需要一個方法public int heightOfSubtree()

...的比例...

你需要一個方法double ratioScore()，（在這裏你可以實現「要做到這一點我必須加起來1 ，否則該比率的葉子將是1/0 =無窮大。 '）

如果您實施了這三種方法，ratio應該很容易。

...返回給節點的引用（或節點中的一個，...）U，使得比率...是最大化。

獲取包含所有節點的List，Collection，Iterator等。遍歷所有節點，計算比率分數，保持節點分數最高。返回分數最高的節點。

來源

2014-04-27 16:21:24 Ishtar

二叉樹：節點數量和子樹高度之間的最大值

回答

相關問題