二進制搜索樹中的高度函數

-3

以下是我用於在BST中查找高度的代碼。雖然它的功能完美，但我通過反覆試驗來編寫此代碼。任何人都可以請解釋它是如何工作的一步一步？代碼的一個空運行示例將非常感謝。二進制搜索樹中的高度函數

int Tree::height(tree * Height) 
{ 
    if(Height->left==NULL && Height->right==NULL) 
    { 
     return 0; 
    } 
    else 
    { 
     l=height(Height->left); 
     r=height(Height->right); 

     if (l>r) 
     { 
      l=l+1; 
      return l; 
     } 
     else 
     { 
      r=r+1; 
      return r; 
     } 
    } 
}

來源

2016-02-29 Hassaan Hasan

使用調試器和沿單步通過代碼編寫跟進。 – PaulMcKenzie

我正在使用代碼塊來運行此程序。你能告訴我如何使用調試器嗎？@PaulMcKenzie –

沒有「調試」菜單項或類似的選項？我不使用CodeBlocks。必須有，因爲默認情況下CodeBlocks使用'gcc'而調試器是'gdb'。 – PaulMcKenzie

我會建議您將參數的名稱更改爲「節點」，根據其含義以及小寫字母。

然後，該代碼立即檢查，如果根有孩子，如果不是則返回0。

然後遞歸您訪問由左到右，這是正確的樹的所有節點。當它到達葉節點時，返回的值爲0，無論是l還是r，所以r值會遞增，並且繼續執行。當遞歸結束時，樹的左右高度減1（前面的葉子數爲0），所以添加1並且您有整個高度。

請注意，此方法返回樹的高度，但無法知道哪個葉子最深，因爲當l和r都返回0時，總是遞增r。

來源

2016-02-29 22:01:26

您的getHeight（） - 函數是這個

int getHeight(tree *p) 
{ 
    if (!p) 
     return 0; 

    int left = getHeight(p->left); 
    int right = getHeight(p->right); 
    return max(left, right) +1; 
}

最重要的要注意的事情，變體，它採用遞歸這意味着該函數調用自身（的getHeight（）被調用內部的getHeight（）本身）在你的代碼的getHeight（）被命名爲高度（）

樹的高度相當於深度recursi的在

功能的getHeight（）遞歸儘可能多的二叉搜索樹的最底層是遞歸的reached.The深度是多少（因子）是的getHeight（）被遞歸調用調用。 的getHeight（）的每一個電話要麼由一個增加一個計數器，以便最終計數器的值是二進制搜索的高度樹或在BST的最低水平「的數量級跳」由max(left, right) +1;確定。這是getHeight（）如何確定二叉搜索樹的高度的過程。

參見遞歸維基百科文章https://en.wikipedia.org/wiki/Recursion_(computer_science)

箭頭的操作員 - >當的結構的構件由指針引用被使用（在這種情況下，結構「P」是樹或它的當前BRACH點「左」和「右」是傳出分支）

關鍵的一點要明白的是遞歸是如何工作的。在物理和數學遞歸是模擬到自映射或自我參照

在函數編程/λ演算（https://en.wikipedia.org/wiki/Functional_programming）遞歸是唯一使用的編程技術。它是強制性編程的對應物。

阿蘭圖靈證明，每一次可以在命令式編程寫入的程序也可以在函數式編程/演算（使用遞歸）

來源

2016-02-29 22:06:10

二進制搜索樹中的高度函數

回答

相關問題