반응형 이진트리2 [Java][자료구조] Tree (2) - 이진 트리 구현과 전위,중위,후위,레벨 순회 Binary Tree 구현 이제 이진 트리를 구현하도록 하겠다. 필요한 클래스는 Node, Binary Tree 그리고 예시를 들어볼 Main 클래스이다. Node 클래스에는 본인의 key값이 있어야 하고, 그 노드의 자식들에 대한 정보가 필요하다. 또한 key값에는 다양한 것들이 들어올 수 있으므로 제네릭으로 key값을 사용하였다. 코드는 다음과 같다. Node 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 public class Node { private key key; private Node left, right; public Node(key key, Node left, No.. 2019. 5. 13. [Java][자료구조] Tree (1) - 트리의 정의와 특성, 이진트리에 대하여 트리란? 트리라는 이름이 나온 이유는 실제 나무를 거꾸로 세워 놓은 듯한 모양이라서 트리라고 부른다고 한다. 우리는 트리를 배우기 전에 아마 단순한 배열 리스트부터 단순 연결 리스트 이중 연결 리스트 등을 봐왔을 것이다. 그렇다면 이런 것들도 있는데 왜 트리라는 자료구조가 나온 것 일까? 일반 배열에서는 삽입이나 삭제를 하는데 O(N)의 시간이 걸린다. 첫 번째 배열에 삽입하는 경우 나머지 모든 요소들을 뒤로 한 칸씩 미뤄야 하므로 최악 시간 복잡도가 O(N)이 나온다. 하지만 트리는 편향 트리가 아닌 이상 일반적인 트리에서는 O(logN) 정도의 시간으로 확 줄여진다. 또 트리는 계층구조를 이루는 경우에 굉장히 좋다. 회사의 조직도를 생각해보면 맨 위에 회장님, 사장님이 있을 것이고, 부서별, 팀별로 .. 2019. 4. 8. 이전 1 다음 반응형
