'자료구조 및 실습' 카테고리의 글 목록

본문 바로가기

자료구조 및 실습 - [8] 트리 Tree 실습문제(파이썬으로 선위순회, 후위순회 구현) (3) 위 트리를 연결리스트를 이용해서 구현하고, 주어진 노드에 대해 자신과 왼쪽 자식, 우측 자식의 용량을 순서대로 출력하시오. ※ 참고사항: 실습 및 테스트 용이성을 위해 본 문제에서는 고정된 트리를 사용하지만, 일반적으로 동적으로 삽입, 삭제 가능한 트리를 사용함 출력 ◦ 자식 및 노드 존재 여부에 따라 출력 내용이 달라짐 - 한쪽 자식만 존재하는 경우, 자신과 해당 자식 노드의 용량 2개 값만 출력 - 자식 노드가 없는 경우, 자신의 용량 1개 값만 출력 - 존재하지 않는 노드번호가 입력되는 경우 –1을 출력 위 문제는 트리를 순회하며 해당하는 노드를 찾고, 조건에 맞게 출력해야 한다고 생각했다. class Node: def __init__(self,data,L=None,R=None,parent=None..

자료구조 및 실습 - [8] 트리 Tree (파이썬으로 선위순회, 후위순회 구현) (2) 선위순회 선위순회는 노드를 자기 자식노드보다 앞서서 방문하는 방법이다. 이는 재귀적으로 구현할 수 있다. 후위순회 선위순회는 노드를 자기 자식노드보다 나중에 방문하는 방법이다. 이또한 재귀적으로 구현할 수 있다. 두가지 방법을 구현하는데 차이점은 노드를 방문하는 타이밍에 있다. 간단하게 순서만 바꿔주면 구현할 수 있다. 아래는 전체적인 트리 ADT의 메서드에 선위순회, 후위순회를 추가해놓은 것이다. class Node: def __init__(self,data,L=None,R=None,parent=None,num=None): self.data = data self.L = L self.R = R self.parent = parent self.num = num class tree: def __init__(s..

자료구조 및 실습 - [8] 트리 Tree (파이썬으로 트리 구현) (1) 트리 ADT 트리 ADT는 계층적으로 저장된 데이터 원소들을 모델링 한 것이다. 앞선 데이터 구조들과 차이점이라면 계층적이라는 점이다. 맨 위의 원소를 제외하고, 각 트리 원소는 부모(parent) 원소와 0개 이상의 자식(children) 원소들을 가진다. 전제: 트리는 비어있지 않다 -> 알고리즘 단순화 트리 용어 루트(root): 부모가 없는 노드(A) 내부노드(internal node): 적어도 한 개의 자식을 가진 노드(A, B, C, F) 외부노드(external node), 또는 리프 (leaf): 자식이 없는 노드(E, I, J, K, G, H, D) 형제(siblings): 같은 부모를 가진 노드들(G, H) 노드의 조상(ancestor): 부모(parent), 조부모(grandparen..

자료구조 및 실습 - [7] 큐 Queue, 데크 Deque (파이썬으로 큐,데크 구현) (1) 큐 ADT 큐 ADT는 임의의 개체들을 저장하는 하나의 추상자료형이다. 삽입과 삭제는 선입선출 (First In First Out, FIFO)순서를 따른다. 삽입은 큐의 뒤(rear)에서, 삭제는 큐의 앞(front)이라 불리는 위치에서 수행된다. 큐 ADT 메서드 큐의 메서드는 다음과 같다. #주요 큐 메서드 enqueue(element) : 큐의 뒤에 원소를 삽입 element dequeue() : 큐의 앞에서 원소를 삭제하여 반환 #보조 큐 메서드 element front() : 큐의 앞에 있는 원소를 (삭제하지 않고) 반환 integer size() : 큐에 저장된 원소의 수를 반환 boolean isEmpty() : 큐가 비어있는지 여부를 반환 iterator elements() : 큐 원소 전..

이전 1 2 3 4 5 다음

티스토리툴바