二叉樹

Question

關於混亂高度假設我的樹是這個樣子

 5 
/\ 
    1 8 
    /\ 
    6 9 

我寫了一個程序來找到這個高度。

 65 int height(const TNODE* root) {                                                   
66   if (root == NULL) {                                                    
67     return 0;                                                     
68   } else {                                                       
69     int lDepth = height(root->left);                                               
70     int rDepth = height(root->right);                                               
71     if (lDepth > rDepth) {                                                  
72       return (lDepth + 1);                                                
73     } else {                                                     
74       return (rDepth + 1);                                                
75     }                                                       
76                                                           
77   }                                                         
78 } 

運行此方法會爲上面的樹打印3。但是高度不應該是2，因爲那是從根到最遠葉子的邊緣數量？我在網上搜索，我得到了矛盾的信息。有人會說我上面的樹高3，而其他人說2。

那麼我的樹上面應該有多高，爲什麼？

我的方法正確嗎？

Answer 1

術語「高度」在這裏有點過於籠統。根據精確的定義，2或3可能是正確的答案。

例如，如果我聲明樹的高度是它包含的「水平」的數量，則3是正確的答案。但是，如果我聲明樹的高度是跨越邊界以達到樹葉的最大數量，而不會超過一次邊（即沒有反向跟蹤），那麼2是正確的答案。

根據我的經驗，更常見的答案是3.樹有3個級別。只有根節點的樹的高度爲1.我寧願這樣做，因爲空樹的高度爲0.

Answer 2

只是關於風格的建議。

int height(const TNODE* root) {                                                   
    if (root == NULL) {                                                    
     return 0;                                                     
    } else {                                                       
     int lDepth = height(root->left);                                               
     int rDepth = height(root->right); 
     return max (lDepth, rDepth) + 1;                                                 
    }                                                         
    }