2011-04-30 254 views
0

我需要編寫一個方法來確定二叉樹是否平衡。所以首先我必須確定樹的每一邊的高度。但是我很難理解我將如何計算子樹的最大長度,而不計算子樹中的所有節點。這個問題很難問我,所以你們可以理解。balanced()二叉樹

// primary method 
public int Height() 
{ 
    int h = height(root); 
} 

// recursive method 
private int height(Node x) 
{ 
    if(x == null) return 0; 
    count++;     
    height(x.left); 
    height(x.right); 
    return count;   
} 

這是我的代碼,用於計算樹的最大高度。 但我不知道如何確定只是左側或右側的高度, 和這種方法似乎計算在樹本身的節點數量。

+2

聞起來像功課! – CoolBeans 2011-04-30 17:37:42

+0

是的,我知道。但這就是爲什麼我沒有要求孔平衡樹,只是高度和概念如何開始balnced樹。爲什麼我的代碼出來如此studip? – 2011-04-30 17:39:34

+0

愚蠢,對不起... – 2011-04-30 17:40:06

回答

1

由於return;聲明 - 這個方法不會編譯,所以你需要返回一個int。因此,if(x == null),你應該返回什麼?空樹的高度是多少?

一旦你明白了,想象你的根只有一個左子樹(root.right == null),並且你知道左子樹的高度。整棵樹的高度應該是多少?

如果它只有一個正確的子樹會怎麼樣?

現在,如果它有兩個呢?

請注意,您不需要全局計數變量。

+0

好初學者錯誤與第一個返回值。如果在那裏更改我的代碼。 – 2011-04-30 17:52:48

1

高度爲1 + max(left.height(),right.height())。

你應該返回一個值,而不是設置變量(計數,你的情況),否則你會發瘋。

+0

但我不明白的是,left.height()和right.height()只會返回0.如果不計算一個值,他們如何返回一個值? – 2011-04-30 17:54:18

+0

但我不明白的是,left.height()和right.height()將返回0.如果他們不算一個值,他們如何返回一個值? – 2011-04-30 17:54:19

+0

cuase我說當到達葉子時返回0 – 2011-04-30 17:54:51

0

節點的高度比其最高子節點的高度大1(提示:使用Math.max)。

0

添加提示我還會指出,你真的想使用遞歸。