이진 트리를 반복적으로 순회하기

Question

재귀 함수에 관해서는 절망적입니다. 바이너리 트리를 탐색하고 특정 값 사이에 새 노드를 삽입하는 재귀 함수를 만들어야합니다. 내 트래버스 함수를 다시 복사하고 그것을 사용하는 다른 모든 함수에서 수정해야합니까? 누군가가 트래버스 기능을 평가 해 주시겠습니까?

내 트래버 싱 코드가 괜찮다고 생각합니다.

Node traverse (Node currentNode){ 
    if (!currentNode.left.equals(null)){ 
     traverse (currentNode.left); 
     return currentNode.left; 
    } 
    if (!currentNode.right.equals(null)){ 
     traverse (currentNode.right); 
     return currentNode.right; 
    } 
    return currentNode; 
} 

Answer 1

이진 트리의 경우 재귀 적으로 수행 할 수있는 여러 가지 유형의 트래버스가 있습니다. 그들은 방문한 순서대로 작성됩니다 (L = 왼쪽 자식, V = 해당 노드 방문, R = 오른쪽 자식).

• 인 - 순서 탐색 (LVR)
• 역순 탐색 (RVL)
• 전순 주사 (VLR)는 (LRV)는

귀하의 코드가 나타납니다

Postorder 통과는

을 수행 할 postorder traversal 메서드를 사용하지만 몇 가지 사항이 섞여 있습니다. 먼저 노드이 트래버스하려는 대상입니다. 데이터은 귀하가 방문하기를 원하는 것입니다. 둘째, 노드 자체를 반환 할 이유가 없습니다.이 방식이 구현됩니다. 귀하의 코드는 ' 특정 데이터를 찾고 있는데, 노드 No @ 0xdeadbeef가 있습니까?'라는 조건을 허용하지 않습니다. 이것은 일종의 추가 검색 매개 변수로 발견됩니다.

학술 BST 통과는 노드 자체 만 인쇄합니다. 검색 기능을 추가하려는 경우 올바른 노드에 대한 추가 검사는 물론 하나의 매개 변수가 추가됩니다.

여기에 코드 조각입니다 :

// Academic 

public void traverse (Node root){ // Each child of a tree is a root of its subtree. 
    if (root.left != null){ 
     traverse (root.left); 
    } 
    System.out.println(root.data); 
    if (root.right != null){ 
     traverse (root.right); 
    } 
} 

// Search with a valid node returned, assuming int 

public Node traverse (Node root, int data){ // What data are you looking for again? 
    if(root.data == data) { 
     return root; 
    } 
    if (root.left != null){ 
     return traverse (root.left, data); 
    } 
    if (root.right != null){ 
     return traverse (root.right, data); 
    } 
    return null; 
} 

Answer 2

재귀 함수는 수정 된 매개 변수 또는 종료 (종료) 조건을 사용하여 자체 값을 반환합니다. 예를 들어, 계승 : 코드에서

int factorial(int param) { 
    if (param > 1) { 
     return param * factorial(param -1); 
    } else { 
     return 1; 
    } 
} 

, 당신은 '횡단'하지만이 결과 아무것도하지 않고 전화 ... 당신의 재귀 함수가 종료되면 존재하는 경우, 최종 반환 먼저 왼쪽 아이가 될 것입니다, 그렇지 않으면 첫 번째 오른쪽 자식, 존재하지 않으면 루트 노드.

트리를 트래버스해야하는 이유에 대해 자세히 설명해주십시오 (또한 "함수를 복사하고 다른 모든 함수에서 수정하십시오"라는 의미가 확실하지 않은 경우), 함수의 전체 개념은 코드 한 번입니다 -call-many)

Answer 3

preorder 방법론에서 순회하고있는 것처럼 보입니다. 그러나 실제로 당신이 현재의 노드를 실제로 U 노드에 도달했는지를 정의하는 기본 값과 비교하지 않고 성취하고자하는 것에 대해서는 회의적입니다. 목적지. 간단한 나무를 그려서 단계를 시각화하는 것이 좋습니다. 그런 다음 코드에 넣으십시오.