二叉樹中節點的深度

Question

我寫了下面的函數，它返回二叉樹的特定節點的深度。考慮這裏的樹：如果我要求節點5的深度，我應該從路徑1 - > 2 - > 5得到3的答案。

它不工作;即使我從函數返回高度，我也會得到0。

這裏「data」是要找到其深度的值，root是樹的根節點。高度的初始值是1（根節點是1級）。

int height_target(node *root,int data,int height){ if(root==NULL) return 0; 

if(root->info==data) 
return height; 

height_target(root->left,data,height+1); 
height_target(root->right,data,height+1); 
} 

Answer 1

最值得注意的是，你的遞歸分支什麼都不返回。把高度傳遞迴一個層次是不夠的：你必須一直把它傳遞到線上。

您需要捕獲並返回左邊&右側子樹調用的最大值。

---

編輯：刪除最後一句......

因此，你需要返回從哪個電話（左或右）的值找到所需的節點。你沒有回報任何東西。例如：

ldepth = height_target(root->left , data, height+1); 
if (ldepth > 0) 
    return ldepth; 
rdepth = height_target(root->right, data, height+1); 
if (rdepth > 0) 
    return rdepth; 
return 0; 

這將返回無論哪個分支成功找到所需的節點，並在失敗時返回0。

Answer 2

你沒有對從height_target返回的值做任何事情。

想必你想要的東西，如：

return std::max(height_target(root->left,data,height+1), 
       height_target(root->right,data,height+1)); 

Answer 3

我想你0作爲answwer因爲如果不存在與價值等於數據節點的條件 if(root->info==data)是永遠不會滿足。如果你得到0作爲響應，那麼你在二進制樹中搜索的「數據」就沒有。

Answer 4

好的。我想我明白了。嘗試使用這樣的功能：

void height_target(node* root,int data,int height,int& h) 
{ 
    if(root==NULL) 
    return; 

    if(root->info==data) 
    h=height; 

    height(root->left,data,height+1,h); 
    height(root->right,data,height+1,h); 

} 

我想你supposend有不能在樹

Answer 5

它不工作的兩個相等的值;

這裏是一個可能的修復你的代碼：（更新 - 此代碼現在編譯）

總結 - 「decursion」（當遞歸正在瓦解）在你的代碼丟棄結果的最後兩行。

int height_target(node* current, int data, int height) 
{ 
    int retVal = 0; 

    do { 

     if (nullptr == current) 
     break; // 0 indicates not found 

     if (current->info == data) { retVal = height; break; } 
     // found the node at 'height'; now de-curse 

     retVal = height_target (current->left, data, height+1); 
     if (retVal) break; // found data in left branch 

     retVal = height_target(current->right, data, height+1); 
     if(retVal) break; // found data in right branch 

    }while(0); 

    return retVal; 
} 

想象你的搜索條目找到5層「上」，使最高遞歸返回5

在層4，數據沒有被發現，那麼你的代碼，然後搜索這兩個左支和右分支。

對於任一分支，當您的代碼返回（來自第5層）的值爲'5'時，您的代碼只會丟棄結果。

---

在這種可能的解決方案中，我從左側或右側返回後測試了retVal。現在，如果返回值（來自第5層）不爲零，該函數將返回非零值;最終將堆棧中的值從堆棧中彈回到遞歸的底部。

也許簡化呼叫跟蹤可以說明：

height_target (., ., 1); // first call, data not found at root 
| height_target (., ., 2); // recursive call, data not found 
| | height_target (., ., 3); // recurse, not found 
| | | height_target (., ., 4); // recurse, not found 
| | | | height_target (., data, 5); // found! 'decursion' begins 
| | | | | 
| | | | returns 5 // height 5 returns 5 
| | | returns 5 // height 4 return 5 
| | returns 5 // height 3 returns 5 
| returns 5 // height 2 returns 5 
returns 5 // height 1 returns 5 

首先調用現在返回5

Answer 6

的問題是在你的什麼return不理解：它不會終止當前函數的所有調用，它只結束所述函數的當前迭代並將該值傳遞迴先前的堆棧幀。

考慮：

#include <iostream> 

int f(int args) { 
    if (args == 3) 
     return args; 
    f(args + 1); 
    std::cout << args << "\n"; 
} 

int main() { 
    f(0); 
} 

http://ideone.com/59Dl7X

你的編譯器應該已經警告你的函數沒有返回值。

你需要的是這樣的：

static const size_t NODE_NOT_FOUND = 0; 

size_t height_target_impl(node *root, int data, size_t height) 
{ 
    if (root == nullptr) 
     return NODE_NOT_FOUND; 

    if (root->info == data) 
     return height; 

    int branch_height = height_target_impl(root->left, data, height + 1); 
    if (branch_height != NODE_NOT_FOUND) 
     return branch_height; 
    return height_target_impl(root->right, data, height + 1); 
} 

size_t height_target(node* root, int data) 
{ 
    return height_target_impl(root, data, 1); 
} 

古稱：

int h = height_target(root, data); 

這如果節點沒有被發現或返回值爲0基於1的高度，與1表示在根節點中找到數據。