이진 트리 노드의 깊이

Question

필자는 이진 트리의 특정 노드 깊이를 반환하는 다음 함수를 작성했습니다. 여기서 트리를 생각해보십시오. 노드 5의 깊이를 묻는다면 1 -> 2 -> 5 경로에서 3의 답을 얻어야합니다.

작동하지 않습니다. 함수에서 높이를 반환하더라도 0이됩니다.

여기에서 "데이터"는 깊이를 찾을 값이고 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에서 반환 된 값으로 아무 것도 수행하지 않습니다.

은 아마도 당신이 원하는 식으로 뭔가 : 나는 데이터에 동일한 값을 가진 노드가없는 경우 조건 if(root->info==data)는 결코 만족하지 않기 때문에 당신이 answwer 0을 얻을 생각

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

Answer 3

. 응답으로 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); 

} 

을 당신이 그것을 작동하지 않는 나무

Answer 5

에서이 개 같은 값이있을 수 없다는 supposend 생각; (-이 코드는 이제 컴파일 업데이트)

요약 - '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 층 '최대', 가장 높은 재귀 층 (4) 5.

을 반환하도록이 데이터를 찾을 수 없습니다 발견 상상 오른쪽 가지.

두 분기 모두에서 코드가 '5'값으로 반환되면 (레이어 5에서) 코드는 단순히 결과를 무시합니다.

---

이 가능한 솔루션에서 나는 왼쪽 또는 오른쪽에서 돌아온 후 retVal을 테스트했습니다. 이제 반환 값 (레이어 5에서)이 0이 아닌 경우 함수는 0이 아닌 값을 반환합니다. 결과적으로 스택에서 값을 꺼내서 재귀의 맨 아래로 '뒤로'내립니다.

아마도 간단한 전화 추적은 설명 할 수는 현재 함수에 대한 모든 호출을 종료하지 않습니다

는

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

귀하의 컴파일러는 함수가 값을 반환하지에 대해 경고되어 있어야합니다. 와,

int h = height_target(root, data); 

이 노드가 발견되지 않은 경우 0의 값을 반환 또는 1 기반의 높이 :

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); 
} 

로 호출 :

은 당신이 원하는 것은이 같은 것입니다 1은 루트 노드에서 데이터가 있음을 나타냅니다.