재귀 5

[JAVA] 재귀 - 이진트리(Binary Tree)의 순회

앞에 글에서 이진탐색트리의 삽입을 구현했었다. 이진탐색트리 삽입 (1) - http://marobiana.tistory.com/81이진탐색트리 삽입 (2) - http://marobiana.tistory.com/82 이번에는 순회에 대해 짜볼 것이다.사실 이걸 정리하고 싶었을 뿐인데, 이진탐색트리 삽입이 더 복잡해서 거기서 시간 다보냄 ㅎㅎ 요번건 소스가 아주 간단함. 1. 이진트리 순회 방법컴공 2학년 때 자료구조에서 배우는 요것.. 순회 방법에는 3가지가 있다.각 순회방법으로 갔을 때 순서를 적어보겠다. - Pre order (전위) : Root부터 왼쪽 모든 노드 탐색 후 오른쪽 24 15 2 19 28 27 30 - In order (중위) : 맨 왼쪽 아래노드부터 Root, 오른쪽 2 15 19..

[JAVA] 재귀 - 이진 탐색 트리(Binary Search Tree)의 삽입 - (2)

앞에 글에 이어서.. 앞 글 - http://marobiana.tistory.com/81 문제 : 트리에 넣을 숫자들을 입력 받아 이진탐색트리를 만들어라. 3. 예제 C++로 하면 포인터 써서 눈에 보기 더 좋을 것을ㅠㅠ Java로 포인터처럼 짜봤음 ㅋㅋ아래와 같이 3개의 클래스로 구성할 수 있음. 트리 삽입참고로, Tree에 넣는 숫자 순서가 트리모양을 결정한다public class BinarySearchTree { public static void main(String[] args) {Tree tree = new Tree();tree.addNode(24);tree.addNode(15);tree.addNode(19);tree.addNode(2);tree.addNode(28);tree.addNode(27..

[JAVA] 재귀 - 이진 탐색 트리(Binary Search Tree)의 삽입 - (1)

1. 이진트리, 이진탐색트리란? 각 노드의 자식노드 수가 최대 2개까지만 존재하는 트리이다.글로만 쓰면 이해가 안가므로, 그림 투척!위의 트리는 맨 밑 노드(리프노드 - Leaf Node)를 제외한 모든 각 노드가 자식노드를 2개씩 갖고있는데, 이런 트리를 완전트리 라고 한다. 완전트리가 아니더라도 자식노드가 2개 이하이면 이진트리이다. 아래 트리처럼!!요런 모양을 편향트리? 왼쪽 경사 트리? 변질 트리? 등으로 부른다.어쨌든, 이진트리에 대한 정의는 이정도이다. 그렇다면, 이진탐색트리(Binary Search Tree)는 무엇인가? 저 위의 그림들이 바로 이진탐색트리이다. 위에 있는 트리를 보면 숫자가 들어있다.루트노드의 왼쪽 아래에는 루트보다 작은 숫자가, 루트노드의 오른쪽 아래에는 루트보다 큰 숫자..

[JAVA] 재귀 기초 - 피보나치 (Fibonacci)

재귀에 대한 이해도가 전혀 없다면 http://marobiana.tistory.com/79 fibo(2-2) + fibo(2-1) else문의 첫번째 메소드인 fibo(2-2)가 호출 된다. 3) fibo(2-2)n은 0이므로 if문에서 0리턴하고 종료 fibo(2-2) + fibo(2-1) => 0 + fibo(2-1) 4) 스택에 있던 fibo(2)로 다시 돌아가서, fibo(2-1)이 실행된다.n이 1이므로 1을 리턴하고 종료된다. 5) 스택에 있던 fibo(2)에서는 fibo(2-2) + fibo(2-1) => 0 + 1 else문에서 각각 리턴된 0과 1을 더한 1을 리턴하고 종료된다. 현재, 아래와 같이 출력된 상황임. 11 6) main 함수에서는 i는 3이 되어, fibo(3)이 호출된다...

[JAVA] 재귀 기초 - 팩토리얼 (Factorial)

오랜만에 재귀 문제를 풀다보니 헷갈려져서 정리한번 해보겠음.재귀 중에 가장 쉬운 팩토리얼부터.. 1. 재귀함수란? 함수 내에서 자기 자신을(함수)를 계속적으로 콜 하면서 풀어가는 방식이다.스택(Stack)이라고 생각할 수 있다.함수가 콜 되면서 최근에 자신을 부른 원래 함수가 스택에 차곡차곡 쌓이게 됨.중요한건 처음 불려진 함수에서(스택 맨 밑에있는 메소드) return 되는 값이 최종 return 값이 된다 2. 팩토리얼이란? 3! = 3*2*1 = 64! = 4*3*2*1 = 245! = 5*4*3*2*1 = 120 3. 재귀 예제 문제 : 특정 숫자의 팩토리얼 구하기 간단하게 소스 투척 public class Factorial {public static void main(String[] args) ..