이진트리의 개념을 서술하고, 이진트리 탐색에 대하여 각각 예를

소개

과목명: 이산수학
과제명: 이진트리의 개념을 서술하고, 이진트리 탐색에 대하여 각각 예를 들어 설명하시오.

목차

Ⅰ. 서론

Ⅱ. 본론
1. 이진트리
2. 이진트리 탐색
(1) 깊이 우선 탐색
1) 중위 순회
2) 전위 순회
3) 후위 순회
(2) 너비 우선 탐색
1) 레벨 순회

Ⅲ. 결론

Ⅳ. 참고문헌

본문내용

이산수학에서 트리는 그래프의 특수한 형태로써 정보의 항목들이 서로 간의 연결선으로 연결되어 있는 계층적인 자료 구조를 말합니다. 이와 같은 트리 구조는 컴퓨터 과학에서 인공 지능 분야의 문제를 해결하거나 검색, 컴퓨터 내부 구조, 게임 이론 등과 같은 다양한 분야에 널리 이용되고 있습니다. 또한, 실제 사회에서도 트리라는 이름으로 불리지는 않지만 회사의 경영 구조를 보여주거나 가문의 계보, 운동 경기의 토너먼트를 그릴 때 이와 같은 트리 구조가 사용되고 있습니다. 이러한 트리는 자식과 부모 관계로 되어 있는 노드들로 구성된 자료 구조를 말하며 노드로 구성되었다는 점에서 연결리스트와 비슷한 특징을 가지고 있습니다.
그렇지만 리스트는 하나로 이어지는 선형의 구조로 이루어져 있지만 트리는 여러 가지 갈래로 뻗어 나갈 수 있는 비 선형 구조를 가지고 있다는 차이를 보이고 있습니다. 트리에서는 부모와 자식 관계에 따라서 자신이 노드만 가리킬 수 있으며 부모 또는 형제를 가리키는 노드가 존재해서는 안된다는 특징을 가지고 있습니다. 따라서 트리는 “한 개 이상의 점점 또는 노드로 이루어진 유한 집합으로 노드 중에 루트라고 불리는 근노드가 존재하며 나머지 노드들이 T1, T2, …, Tn 등으로 분리되어 존재한다.”고 정의할 수 있습니다. 이 때, T1, T2, …, Tn은 각각 하나의 독립된 트리로 서브 트리라고 불립니다. 트리에 존재하는 루트 노드는 단 하나만 존재해야 합니다.

참고자료

· 박종안 외, 『이산수학』, 2023
· 천인국 외, 『C언어로 쉽게 풀어쓴 자료구조』, 2019