計算二叉搜索樹的高度

我一直在尋找如何計算二叉搜索樹的高度，我的研究已經引導我進入下面的實現。我仍然試圖圍繞爲什麼它應該起作用，但我也不確定它爲什麼不起作用。這是我的身高功能。計算二叉搜索樹的高度

int BinaryTreeNode::height() const { 
    int lefth = left->height(); 
    int righth = right->height(); 
    if(lefth > righth) { 
     return lefth + 1; 
    } else { 
     return righth + 1; 
    } 
}

，這裏是爲節點

class BinaryTreeNode { 
    public: 
    Data * nodeData; 
    BinaryTreeNode * left; 
    BinaryTreeNode * right;

我的類定義當我嘗試運行我的程序locksup和崩潰。我錯過了明顯的東西嗎？

編輯：爲什麼不應該這樣工作？

int BinaryTreeNode::height() const { 
    int l = 0; 
    if (left != NULL) { 
     left->height(); 
    } 
    int r = 0; 
    if (right != NULL) { 
     right->height(); 
    } 
    if (l > r) { 
     return l + 1; 
    } 
    else { 
     return r + 1; 
    } 
}

來源

2013-03-30 Sean Lafferty

你可以使用調試器嗎？ – Synxis

您錯過了基本案例。沒有基礎案例，你會遇到無限遞歸。 – us2012

你做的第一件事是再次調用'height（）'，你有一個無限循環/ –

你的樹不是無限的。所以，我想有些節點沒有左或右孩子，在這種情況下指針left和/或right爲空。在嘗試使用它們之前，你必須檢查它們的存在。

嘗試該功能來代替：

int BinaryTreeNode::height() 
{ 
    int l = left ? left->height() : 0; // height of left child, if any 
    int r = right ? right->height() : 0; // idem for right child 
    return 1 + max(l, r); 
}

注：我已經簡化了你的高度的計算。

來源

2013-03-30 21:28:16 Synxis

你的代碼有效，但我試過重寫它喜歡但它沒有。我打破了什麼？（把代碼放在OP中） –

它不是什麼？ – Synxis

@SeanLafferty：你粘貼的是* my *代碼的原始版本，它的確被破壞了（我忘記了這個任務）。現在它可以工作。但我承認Synxis的這個版本更好 –

的問題是，你的功能從來沒有檢查，如果孩子指針是NULL，從訪問一個空指針，以便分開，你有錯過了基本情況遞歸函數：

試試這個版本：

int BinaryTreeNode::height() const 
{ 
    int lefth = 0; 
    if (left != NULL) { lefth = left->height(); } 

    int righth = 0; 
    if (righth != NULL) { righth = right->height(); } 

    if (lefth > righth) { return lefth + 1; } 
    else { return righth + 1; } 
}

來源

2013-03-30 21:26:14

你忘了將'left-> height（）'的值賦給'lefth'（對於右邊的孩子也是一樣的）;） – Synxis

@Synxis：呵呵，對:)謝謝你編輯 –

即使我面臨着同樣的問題，你的代碼的問題是，在你的函數中，你正在使用recurssion兩次，並且你要去左右兩端，但是你沒有檢查可能性，其中一個左子樹中的父節點有其自己的子節點，因此您不會遍歷樹中的最後一個葉子節點！希望這可以幫助

來源

2017-01-03 03:13:32 user7367589

計算二叉搜索樹的高度

回答

相關問題