개발63 완전 이진트리(Complete Binary Tree) 연결리스트(Linked List)로 만들기 서론 완전 이진트리(Complete Binary Tree)는 규칙적으로 모든 노드가 순차적으로 2개의 지식 노드를 갖는다. 따라서, 배열은 사용할 경우 배열의 모든 칸이 낭비없이 가득 차게 되어 구현하기 편한 배열을 주로 사용한다. 하지만 연결리스트(Linked List)를 사용해서 구현하려면 어떻게 해야할까? 생각보다 복잡하지 않다. 이 글에서는 방법만을 설명하도록 하겠다. 필요지식 - 완전이진트리란? 본론 완전이진트리를 구성함에 있어 가장 걸림돌이 되는 부분은 새로 노드를 삽입해야 할 때, 이를 "어디에" 삽입해야 될 지를 모른다는 것이다. 여러가지 방법이 있지만, 필자가 소개하는 방법은 큐(Queue)를 사용하는 방법이다. 바로 방법을 소개하도록 하겠다. IF (Queue가 비어있을 경우)(1) 첫.. 2017. 11. 17. 완전이진트리(Complete Binary Tree)란? 필요한 사전지식 - 이진트리란? 본론 이진트리의 한 종류인 완전 이진트리는 그림으로 보면 쉽게 이해됩니다. 위의 그림은 완전이진트리(Complete Binary Tree)인 트리들이고, 밑의 그림은 아닌 트리들입니다. 차이가 느껴지시나요? 완전 이진트리들은 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리입니다. 완전이진트리가 아닌 트리들을 보시면 왼쪽이 비어있는데 오른쪽부터 들어가 있죠? 이런 트리들은 완전 이진트리가 아닙니다. 2017. 11. 17. 이진트리(Binary Tree)란? - From 위키백과 From https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC 이진 트리위키백과, 우리 모두의 백과사전.크기가 9이고, 높이가 3인 이진 트리이진 트리(binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 뜻한다. 보통 첫 번째 노드를 부모 노드라고 하며 자식 노드는 왼쪽(left)과 오른쪽(right)으로 불린다. 이진 트리는 이진 탐색 트리와 이진 힙의 구현에 흔히 쓰인다.목차 [숨기기] 1정의2종류3특징4이진 트리 탐색5표현 방법정의[편집]방향 간선(directed edge)은 부모에서 자식으로 가는 경로를 가리킨다. (그림의 화살표 부분)루트 노드(root node)는 부모가 없는 노드이다. 트리는 하나의 .. 2017. 11. 17. 이전 1 ··· 8 9 10 11 다음
