計算二叉搜索樹的深度？

我很難計算給定BST的深度總和[根的所有孩子的各個深度的總和]。我有樹的節點總數，我正在計算樹的平均深度，需要我有這個深度和。計算二叉搜索樹的深度？

遞歸和我不相處得很好..我發現這個問題非常困難。如果可能，我希望看到一個遞歸解決方案。

注：

我已經創建存取Node.getLeft（）和Node.getRight（）

來源

2009-12-09 Jon

這聽起來像是功課很糟糕。到目前爲止你寫了什麼？你在哪裏陷入困境，除了你與遞歸相處不好？ SO用戶不會爲此寫出完整的解決方案。 – 2009-12-09 20:05:24

另外，標記爲家庭作業。 – CookieOfFortune 2009-12-09 20:06:09

像這樣的樹問題真的不能用遞歸求解。其他解決方案往往要複雜得多，閱讀起來更難，維護也更困難。 – Michael 2009-12-09 20:06:53

想想你將如何去這個標準地通過手，如果我已經提出了BST的一個圖片你在一張紙上。當你在一個節點時，你需要跟蹤哪些信息？如何找到給定節點的高度？

從這裏，嘗試將其轉換爲僞代碼或甚至直接轉化爲Java。如果您遇到問題，請隨時發表評論，以便用戶可以幫助您。

來源

2009-12-09 20:08:33

您只需在遍歷樹時保留深度計數器（如果必須查找樹遍歷）並在每次到達節點時添加計數器的值。然後除以節點的數量。

這看起來像家庭作業，所以我沒有提供更詳細的解決方案。

來源

2009-12-09 20:09:26 CookieOfFortune

這是功課嗎？如果這樣標記問題。

您可以創建一個方法：

有一個節點的引用和深度作爲參數
增量深度
如果節點不是一個子節點調用遞歸左，右和更新總和因此
兒童的數量，否則返回總和+深度

一旦你有了這個devide在樹中獲得平均深度。

來源

2009-12-09 20:10:24 rsp

我們需要訪問所有的葉節點並找出它們的深度。這表明：

給你的節點訪問函數一個額外的參數。它不僅需要知道它的發展方向，還需要知道它有多深。每次調用它時，都會調用深度，因此您的節點訪問者只需增加調用者獲得的深度數即可。

現在的兩件事情可以發生：

無論是你找到的節點是葉節點，即它不具有任何子女;在這種情況下，您的訪問者需要將其深度返回給調用者。是的，它只是返回它從調用者那裏得到的數字，+ 1.
或者它不是葉節點。在那種情況下，它將有1或2個孩子。我們需要將來自我們孩子的深度報告返回給調用者，只需返回兒童返回的深度總和即可。

通過遞歸的魔力，返回到根的訪問者的數字將是所有孩子的深度的總和。

要獲得平均深度，您需要將其除以葉節點的數量;我將離開第二次遍歷來計算。它可以一次完成，但會稍微複雜一點。

來源

2009-12-09 20:26:08

您可以擴展嗎？或者它不是葉節點，在這種情況下，它將有1或2個孩子。來自孩子的深度報告返回給調用者，只需返回兒童返回的深度總和。「？我完全不明白你的意思。我們如何返回兒童返回的深度總和？ – Jon 2009-12-09 21:05:24

您的訪客功能無論使用何種語言，都可以將一個號碼返回給其主叫方。我告訴你如何在每種情況下計算這個數字。對於非葉子節點，它將自行調用一個或兩個子節點，並且這些1或2個呼叫中的每一個都將返回一個數字。如果有2個孩子，則退還該金額，否則返回您獲得的一個號碼。 – 2009-12-09 21:12:36

既然這是作業，我不想給你一個答案。相反，這裏是一個計算單個鏈表的長度的遞歸方法。希望這將以您能夠理解的方式展示遞歸，並且您可以從那裏推斷解決您的BST問題。

public final class LL { 
    public final int value; 
    public LL next; 

    public LL(final int value) { 
     this.value = value; 
    } 

    public void add(final int value) { 
     if (null == next) { 
      next = new LL(value); 
     } else { 
      next.add(value); 
     } 
    } 

    /** 
    * Calculate the length of the linked list with this node as its head (includes this node in the count). 
    * 
    * @return the length. 
    */ 
    public int length() { 
     if (null == next) { 
      return 1; 
     } 
     return 1 + next.length(); 
    } 

    public static void main(final String... args) { 
     final LL head = new LL(1); 
     head.add(2); 
     head.add(3); 
     System.out.println(head.length()); 
     System.out.println(head.next.length()); 
    } 
}

來源

2009-12-09 20:57:54

計算二叉搜索樹的深度？

回答

相關問題