본문 바로가기

이진트리

[C] 이진트리의 순회
coding/Data Structure(C) 2020. 12. 12. [C] 이진트리의 순회 연결리스트로 이진트리를 구현해보자. 트리도 마찬가지로 배열 혹은 연결리스트로 구현할 수 있다. 배열로는 안해봤다. 기억공간의 낭비가 심해진다고 한다(? 무슨소리냐...). 그래서 연결리스트로 구현했다. 하나의 링크에는 총 3개의 필드가 있다. 가운데에 데이터필드, 왼쪽과 오른쪽에 각각의 자식노드를 가리키는 2개의 포인터필드이다. 그림을 보면 더 쉽게 이해할 수 있음. 1 2 3 4 5 typedef struct TreeNode { int data; struct TreeNode* left, * right; }Node; Colored by Color Scripter cs 이렇게 데이터필드와 왼쪽, 오른쪽의 포인터필드를 만들어주면 된다. (1) 이진트리의 순회 개념정리 이전에 배웠던 선형 자료구조에서, 연산을..
[C] 트리와 이진트리
coding/Data Structure(C) 2020. 12. 12. [C] 트리와 이진트리 트리(Tree)와 이진트리(Binary Tree)에 대해 알아보자. (1) 트리 트리는 계층적인 구조를 나타내는 자료구조이다. 지금까지 배웠던 스택, 큐, 리스트는 모두 선형 자료구조이지만, 트리는 비선형 자료구조 중 하나이다. 트리의 응용분야에는 회사의 조직도, 컴퓨터의 폴더 구조, 인공지능에서의 결정 트리(decision tree) 등이 있다. 차수(degree): 노드의 자식 노드 수 레벨(level): 트리의 각 층의 번호 높이(height): 트리의 최대 레벨 예를 들면, 루트노드인 P의 차수는 2이고(자식이 Q, R 2개이므로), A의 레벨은 3이다. 레벨을 구할 때 루트=1인 것을 잊지말자. 이 트리의 높이는 5이다. 트리도 데이터필드와 링크필드로 나누어서 메모리상에 구현할 수 있는데, 링크..

티스토리툴바