이진 트리 순회방법 - 루트 방문 : V - 왼쪽 서브트리 방문 : L - 오른쪽 서브트리 방문 : R 루트를 언제 방문하느냐에 따라 전위(1), 중위(2), 후위(3)로 구분 ① 전위순회 (preorder traversal) : VLR 루트 노드 방문 (V) 왼쪽 서브트리 방문 (L) 오른쪽 서브트리 방문 (R) void preorder(treenode* root) { // VLR 순 if (root!=NULL) { printf("[%d] ", root->data); preorder(root->left); preorder(root->right); } } ② 중위순회 (inorder traversal) : LVR 왼쪽 서브트리 방문 (L) 루트 노드 방문 (V) 오른쪽 서브트리 방문 (R) void in..

배열로 구현한 이진트리 - 노드 i의 부모 노드 인덱스 = i/2 - 노드 i의 왼쪽 자식 노드 인덱스 = 2i - 노드 i의 오른쪽 자식 노드 인덱스 = 2i+1 연결리스트로 구현한 이진트리 - 노드를 구조체로 표현 - 노드(데이터, 왼쪽 링크필드, 오른쪽 링크필드) typedef int element; typedef struct treenode { element data; struct treenode* left; // 왼쪽 노드로 연결하는 포인터 struct treenode* right; // 오른쪽 노드로 연결하는 포인터 }treenode; ※ Example #include #include // 연결리스트로 구현한 이진 트리 typedef int element; typedef struct treen..

트리 - 계층적 구조(hierarchical structure)을 가진 자료구조 - 부모-자식 관계의 노드들로 구성 트리의 용어 - 노드(node) : 트리의 구성요소 → A, B, C, D, E, F, G, H, I, J - 루트(root) : 각 Tree의 최상위 노드 → A - 서브 트리(subtree) : 최상위 노드를 제외한 나머지 노드 / 하나의 노드 + 그 노드들의 자식 → {B, E, F, G}, {C, H}, {D, I, J} - 간선(edge) : 노드들 사이의 선 - 단말 노드(terminal node) : 자식이 없는 노드 → E, F, G, H, I, J - 비단말 노드(nonterminal node) : 자식이 있는 노드 → A, B, C, D - 높이(height) : Tree..

연결리스트 덱 - 연결리스트를 이용한 덱 (이중 연결 리스트) - front, rear 둘다 삽입/삭제가 되기 때문에 이중 연결 리스트로 구현 [코드 - C] #include #include // 연결리스트를 이용한 덱 (이중 연결 리스트) // front, rear 둘다 삽입/삭제가 되기 때문에 이중 연결 리스트로 구현 typedef int element; typedef struct dnode{ element data; struct dnode* llink; struct dnode* rlink; }dnode; dnode* front; dnode* rear; int is_empty() { return front == NULL; // 공백 상태이면 front == NULL } void add_rear(ele..

연결리스트 큐 - front : 삭제(delete) - rear : 삽입(insert) - rear의 link 필드는 NULL로 설정해야 한다 - 초기 상태 : front == rear == NULL - 공백 상태 : front == NULL [코드 - C] #include #include // 연결리스트를 이용한 큐 typedef int element; typedef struct qnode { element data; struct qnode* link; }qnode; qnode* front = NULL; // 큐의 front(삭제와 관련) qnode* rear = NULL; // 큐의 rear(삽입과 관련) int is_empty() { return front == NULL; // 공백 상태이면 fro..

연결리스트 스택 - 장점 : 크기 제한 X - 단점 : 구현이 복잡, 삽입/삭제 시간이 오래 걸린다 - 크기에 제한이 없기 때문에 스택이 포화인지 확인할 필요가 없다 [코드 - C] #include #include // 연결리스트를 이용한 스택 typedef int element; typedef struct { element data; struct stacknode* link; // 각 노드들을 연결 }stacknode; stacknode* top; // 스택의 top을 가리키는 top 포인터 void init() { top = NULL; } int is_empty() { return top == NULL; } void push(element item) { stacknode* new_node = (sta..

이중 연결 리스트 (Doubly Linked List) - 링크가 양방향 이기 때문에 양방향 검색이 가능 - 삽입/삭제시 반드시 선행 노드가 필요 - 공간을 많이 차지하고 코드가 복잡하다 - 헤드 노드를 보유 - 헤드 노드 + 이중 연결 리스트 + 원형 연결 리스트로 구현할 예정 ※ 헤드 노드 / 헤드 포인터 헤드 노드 - 데이터 필드에 아무런 정보도 담고 있지 않다 → 데이터를 가지지 않는다 - 단지, 삽입/삭제의 편리함을 위해 구현 - 공백상태에서는 헤드 노드만 존재 헤드 포인터 - 리스트의 첫 번째 노드를 가리키는 포인터 ※ 항상 성립하는 관계 - 임의의 노드를 가리키는 포인터 p p = p->llink->rlink = p->rlink->llink 이중 연결 리스트의 노드 구조 - 1개의 데이터 필..

배열 vs 컬렉션 배열 - 고정 크기 - 배열의 중간에 삽입/삭제가 이루어지면 데이터들이 이동해야 한다 컬렉션 - 가변 크기 - 컬렉션 내에서 삽입/삭제가 이루어지면 컬렉션이 자동으로 데이터들을 이동시킨다 - '제네릭'이라는 기법으로 구현 - Vertor, ArrayList : 가변 크기의 배열 구현 - LinkedList : 노드들이 링크로 연결되는 리스트 구현 - Stack : 스택 구현 - HashSet : 집합 구현 모두 Collection를 상속받음 단일 클래스의 객체만을 요소로 다룬다 컬렉션 특징 1. '제네릭'이라는 기법으로 구현 - 컬렉션 클래스의 이름에 , , 등(타입 매개변수) 이 항상 포함 - 컬렉션을 여러 종류의 타입으로 변신할 수 있도록(일반화) 타입 매개변수를 사용 - 컬렉션을 ..

원형 연결 리스트 (Circular Linked List) - 마지막 노드의 링크가 첫 번째 노드의 주소를 가리키는 리스트 - 하나의 노드에서 모든 노드에 접근 가능 - 헤드 포인터가 항상 마지막 노드를 가리키게 설정 1. 삽입 연산 ① 리스트의 맨 앞에 삽입 head == NULL인 경우 : new_node를 insert하게 되면 헤드 포인터가 new_node를 가리키게 된다 void insert_first(c_listnode** head, c_listnode* new_node) { // 리스트 맨 처음에 new_node 삽입 if (*head == NULL) { // head가 NULL => 공백리스트 상태 // new_node를 insert하게되면 head pointer는 new_node를 가리키게..

단순 연결 리스트 (Singly Linked List) - 단방향 연결 - 마지막 노드의 링크값 = NULL - 헤드 포인터 : 연결 리스트의 맨 처음 노드를 가리키는 포인터 단순 연결 리스트 ADT void insert_node(s_listnode **head, s_listnode *pre, s_listnode *new_node) 삽입연산 void remove_node(s_listnode **head, s_listnode *pre, s_listnode *removed) 삭제연산 void print_list(s_listnode *head) 리스트 순서대로 출력 s_listnode *search(s_listnode *head, int value) 리스트안에 존재하는 value 찾아내기 s_listnode ..

연결 리스트 (Linked-List) - 각 상자들을 연결하는 줄 : 포인터로 구현 - 각 상자들 : 노드 - 필요할 때마다 동적 메모리 할당(malloc())을 통해 노드 생성 - 노드 : 데이터 필드/링크 필드로 구성 - 데이터 필드 : data(값) 존재 - 링크 필드 : 다른 노드를 가리키는 포인터 존재 → 포인터를 이용하여 다음 노드에 접근 - 첫 번째 노드를 알면 전체 노드에 접근 가능 - 첫 번째 노드를 가리키는 변수 : 헤드 포인터 (head pointer) - 마지막 노드의 링크 필드 = NULL (더 이상 연결된 노드 X) - 실제 메모리 안의 물리적 순서 ≠ 리스트 안의 논리적 순서 연결 리스트의 장단점 (삽입/삭제) 장점 - 삽입/삭제 시 데이터를 이동할 필요가 없다 - 연속된 메모..

[6장 1번] 다음 main()이 실행되면 아래 예시와 같이 출력되도록 MyPoint 클래스를 작성하라. public static void main(String [] args) { MyPoint p = new MyPoint(3, 50); MyPoint q = new MyPoint(4, 50); System.out.println(p); if(p.equals(q)) System.out.println("같은 점"); else System.out.println("다른 점"); } Point(3,50) 다른점 ≫ 풀이 package Java6_1; class MyPoint{ private int x, y; MyPoint(int x, int y){ this.x = x; this.y = y; } public bool..