나무에있는 인접한 아이들의 비교가 일어나지 않습니까?

Question

이 방법에 어떤 문제가 있습니까? 그것은 보인다. 그러나 나는 나무에서 인접한 아이들의 비교가 일어나지 않는다고 확신하지 않는다.

방법으로 문제가

것 같다 나는 대략 손으로이 알고리즘의 동작을 추적하고 나는 아이디어가 구현에 문제가 어쩌면 올바른 생각이나 내가 재귀 작품, 두 번째 도우미 (비교)하는 방법을 몰라

public static int MAX(BST B) { 
    int m = ((Integer) B.root.data).intValue(); 
    return call(B.root, m); 
} 

public static int call(node current, int max) { 
    //first helper method gets the max from two different levels in the tree 
    if(current == null) 
    return -1; 
    if(current.left == null && current.right == null) 
    return max; 
    else { 
    if(((Integer) current.data).intValue()>max) 
     max = ((Integer) current.data).intValue(); 
    return compare(call(current.left,max),call(current.right,max)); 
    } 
} 

//second helper method gets the max 
static int compare(int m1, int m2) { 
    if(m1>m2) 
    return m1; 
    else 
    return m2; 
} 

Answer 1

전체 트리를 검색 중이므로 구조가 올바르게 정렬되지 않았다고 가정합니다.

if(current.left==null&&current.right==null) return max; 

하는 두 개의 리프 노드 (세 개의 노드가 총)와 루트로 나무를 상상해 :

버그로 통화 기능입니다. 루트는 값 3, 오른쪽에는 값 2, 왼쪽에는 값 5가 있습니다. 알고리즘은 5를 반환하지만 코드는 3을 반환합니다. 이는 리프 (노드가 "children"이 아닌 노드)의 값을 무시하기 때문입니다. 그 코드 줄. 따라서 코드에서이 값의 5를 무시하고 최대 3을 반환합니다.

왼쪽 및 오른쪽이 null 인 경우 compare (current.value, max)를 반환하여이 문제를 해결할 수 있습니다.

Answer 2

예를 들어 right가 null이고 왼쪽이 아닌 경우에만 어린이가 모두 null인지 확인하기 때문에 문제가 발생할 수 있다고 생각합니다 (오른쪽 및 모두에 call). 아마도 하나의 자식이 null 인 경우를 확인하고 그렇지 않은 경우 call을 반환합니다.

Answer 3

... 나는 재귀가 어떻게 작동하는지 아무 생각 ...없는

재귀는 다른 인수와 함께 자체 내부에서 호출되는에있는 방법을 의미하고,에 의해 종료 몇 가지 검사가

값을 반환하거나 자체를 계속 호출 반복적으로.

call()는 -1 또는 max의 반환에 그와 같은 중 하나가 종료 간접적으로 재귀 또는 새로운 인수와 함께 다시 자신을 호출 스택가 가득 같은 OutOfMemory 오류로까지 중 하나가 종료되거나 충돌이 작업을 수행하고 있습니다.

이 방법은 재귀가 아닙니다. 이름이 잘못 지정되었습니다.

static int compare(int m1, int m2) { 
    if(m1>m2) 
    return m1; 
    else 
    return m2; 
} 

및

return Math.min(call(current.left,max),call(current.right,max)); 

중 하나의 방법으로

static int min(final int m1, final int m2) 
{ 
    return Math.min(m1,m2); 
} 

하거나 inlined로 작성 (및 이름) 될 수있다, 당신은 정말 두 값의 minimum 비교되지지고있다 다른 논리와 다른 리턴 값을 내포 한 것입니다.

이 방법은 재귀 적이 지 않으며 m1 > m2의 논리가 적절하면 문제가 될 수 없으며 그 기능에 대한 입력이 예상 한 것과 다른 것입니다.

스텝 디버깅은 강력한 도구이며 숙련 된 개발자 모두가 매일 사용합니다.