2-3-4樹的高度

我有一個工作片斷，用於包含節點的常規樹。現在我只需要擺弄2-3-4的樹，這應該更容易，因爲每條路都是相同的距離，因爲它是平衡的，對嗎？2-3-4樹的高度

我所掌握的方法包括getNextChild(),split()，當然還有insert()。

public int height() { 
    return (height(root)); 
} 

private int height(TNode localRoot) { 
    if(localRoot == null) { 
     return 0; 
    } 
    else { 
     //Find each sides depth 
     int lDepth = height(localRoot.leftChild); 
     int rDepth = height(localRoot.rightChild); 

     //Use the larger of the two 
     return (Math.max(lDepth, rDepth) + 1); 
    } 
}

來源

2010-10-28 John Redyns

可以擺脫左右深度，並使用一條線獲得下一個孩子？ – 2010-10-28 19:39:13

@John我認爲這打破了樹的概念 – Woot4Moo 2010-10-28 20:04:26

的確如此，但是關於找到並返回高度，我不知道採用哪條路徑？如果他們都返回相同的？ – 2010-10-28 20:11:56

public int height() 
{ 
    TNode cur = root; 
    int depth = -1; 

    while (cur != null) 
    { 
     cur = cur.getChild(0); 
     depth++; 
    } 

    return depth; 
}

來源

2010-10-28 20:16:37 poke

應該添加一個檢查以確保root不爲空 – Woot4Moo 2010-10-28 20:22:21

@ Woot4Moo：良好的捕獲，更新爲不同的迭代（並在樹爲空時返回-1的高度）。 – poke 2010-10-28 20:25:37

它應該是：'return ++ depth;'如果它的深度爲'1'，所以你不返回'0' – Woot4Moo 2010-10-28 20:28:56

如果它是平衡的，你就應該能夠遞歸下樹的一側，以確定高度。

來源

2010-10-28 20:18:01 Jeremy

回答

相關問題