빼로의 시시콜콜한 이야기

전 포스팅에서 레벨은 깊이가 같은 노드들을 의미했다. 이번 시간에는 앞서 구했던 높이를 가지고 같은 레벨의 노드들을 구하려고 한다. 기본적인 과정은 이러하다. 1. 루트 노드와 알고 싶은 레벨을 설정한다. 2. 루트에서 하위 노드들로 내려오며 레벨-1을 한다. 3. 레벨이 1이 되면 현재의 노드들을 출력한다. 아래 코든 전체 레벨을 구하기 위한 코드이고 특정 레벨만 알고 싶으면 3번째 줄의 for문을 이하를 수정하면 된다. def level(self): h = self.height(self.root) for i in range(1,h+1): self._level(self.root,level) print() def _level(self, node, level): if node is None: return ..

늦었지만 먼저 트리 관련 용어들을 정리하고 시작한다. 루트(root) : 트리의 최상단에 위치한 노드(해당 그림에선 A) 깊이 : 어떠한 노드와 루트와의 거리 레벨 : 깊이가 같은 노드들의 집합 높이 : 루트와 가장 멀리 떨어진 노드와의 거리 이번 시간에는 높이를 찾아 볼 것이다. 재귀를 이용해 왼쪽 자식으로 끝까지 이동한 다음, 0을 리턴한다. 이는 좌우 하위 노드가 None이면 끝까지 이동한 것으로 생각할 것이다. 거슬러 올라가며 좌우의 하위노드에서 리턴한 값들 중 값을 비교하여 가장 큰 값에 +1을 하여 리턴한다. 코드를 보자. def height(self,node): if node is None: return 0 else: lheight = self.height(node.left) rheight ..

전위 순회(preorder)는 노드 방문 -> 왼쪽 자식 -> 오른쪽 자식 중위 순회(inorder)는 왼쪽 자식 -> 노드 방문 -> 오른쪽 자식 후위 순회(postorder)는 왼쪽 자식 -> 오른쪽 자식 -> 노드 방문으로 스캔한다. A,B,C만 있는 트리를 가지고 설명해보면, 전위 순회 : A->B->C 중위 순회 : B->A->C 후위 순회 : B->C->A 로 움직인다. 조금 더 설명해보자면 전위 순회는 가장 처음에 A를 방문, 중위 순회는 B에서 C로 가는 도중에 방문, 후위 순회는 B와 C를 방문하고 나서 A를 방문한다. 전체 트리를 보며 생각해보자. 전위 순회 : A->B->D->E->H->C->F->G->I 중위 순회 : D->B->E->H->A->F->C->I->G 후위 순회 : D-..

이진 트리(binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리형 자료구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 아래 코드에선 Node 클래스에서 left를 왼쪽 자식으로, right를 오른쪽 자식으로 표현했다. BinaryTree 클래스는 트리의 맨 위쪽(root)을 정해준다. 각 알파벳에 해당하는 노드를 만든 후, add___로 연결한 다음, 마지막에 root를 정해주는 방식으로 진행할 것이다. class Node: def __init__(self, item): self.item = item self.left = None self.right = None def addLeft(self, Node): self.left = Node def addRig..