반응형 Computer Science/Data Structure3 트리의 순회 - 레벨 순서 순회 1. 레벨 순서 순회란? 레벨 순서 순회는 위에서 아래로, 좌에서 우로 순차적으로 순회를 하는 것입니다. 위의 트리에서 레벨 순서 순회를 할 경우, 결과는 1 - 2 - 3 - 4 - 5 - 6 이 됩니다. 개념적으로는 가장 이해하기 쉽고 간단한 순회 방법이지만, 구현은 상대적으로 까다로운 편입니다. 2. 구현 1) 재귀 Queue q = new LinkedList(); public void levelOrder(TreeNode node) { System.out.print(node.getData() + " "); // ① q.add(node.getLeftChild()); // ② q.add(node.getRightChild()); TreeNode temp = q.remove(); // ③ if(temp !.. 2022. 10. 12. 트리의 순회 - 전위 순회, 중위 순회, 후위 순회 1. 트리의 순회 (Tree traversal) 트리 순회란 트리의 모든 노드를 방문하는 것을 말합니다. 방문 순서에 따라 다음 3가지 방법이 있습니다. 처음에는 헷갈리지만 몇 번만 연습해보면 매우 간단하다는 것을 깨닫게 되실 겁니다. 2. 전위 순회(preorder) - VLR 전위 순회는 먼저 자기 자신을 방문한 뒤, 왼쪽 자식-오른쪽 자식 순으로 방문합니다. 만약 자식에게 또 자식이 있다면 자식 노드를 방문하기 전에 자식의 왼쪽 자식 노드를 방문합니다. 즉, 자기 자신을 방문한 다음(V) 왼쪽 자식으로 이동하여 자식이 있는 지 확인하고, 있다면 자식이 없는 리프 노드(leaf node)를 만날 때까지 계속 왼쪽으로 이동합니다. 왼쪽 서브트리에 대한 방문을 모두 마친 뒤에야 (L), 오른쪽 자식에 대.. 2022. 10. 11. 스택과 (원형) 큐 Stack & Queue 만들기 1. 소개 스택과 큐는 쉽고 간단하지만, 운영체제의 시스템 스택이나 스케줄링 등 다방면으로 활용되는 중요한 자료구조입니다. 스택과 큐는 모두 원소를 하나씩 저장하고 저장된 원소를 순서대로 출력 및 삭제하는 방식으로 동작합니다. 차이점으로는, 스택은 가장 나중에 입력된 원소가 가장 먼저 출력되는 후입선출(Last In First Out, LIFO) 방식인 반면, 큐는 가장 먼저 입력된 원소가 가장 먼저 출력되는 선입선출(First In First Out, FIFO) 방식입니다. 2. 구성 스택과 큐는 기본적으로 원소들을 저장할 저장소와 현재 위치를 기억하는 포인터, 그리고 현재 상태를 체크할 2가지 메서드, 핵심 기능인 삽입과 삭제를 위한 메서드 2개가 필요합니다. 3. 구현 with Java (1) 스택.. 2022. 9. 27. 이전 1 다음 반응형
