트리3 [백준 2263번] 트리의 순회 문제 링크 >> https://www.acmicpc.net/problem/2263 📋 문제 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 👉 입력 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. 👈출력 첫째 줄에 프리오더를 출력한다. 💡 사용된 개념 ✔️ 트리의 순회 전위순회(preorder) : 루트노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 중위순회(inorder) : 왼쪽 서브 트리 -> 루트노드 -> 오른쪽 서브 트리 후위순회(posto.. 2022. 4. 14. [12주차] 트리의 표현과 트리 순회 4월 6일 자 학습 내용 정리입니다. ✅ 트리의 표현 방법 이진 트리의 각 노드는 왼쪽 또는 오른쪽 자식을 갖고 있으므로 다음 코드와 같이 표현할 수 있다. class TreeNode : def __init__(self) : self.left = None self.right = None 완전 이진 트리는 배열을 이용해 간단하게 구현할 수 있다. 루트 노드부터 깊이를 더해가며 각 정점에 번호를 붙였을 때 어쩐 정점의 번호가 n이라면 왼쪽 자식은 2n, 오른쪽 자식은 2n+1의 인덱스를 가진다. 따라서 이를 배열로 표현하면 아래와 같다. ✅ 트리 순회 트리 순회란 트리의 모든 노드를 방문하는 순서이다. 트리는 비선형 구조로 자료 사이에 정해진 순서가 없기 때문에 각 노드를 방문하고 값을 가져오기 위해 트리 .. 2022. 4. 7. [12주차] 트리의 개념 4월 6일 자 학습 내용 정리입니다. ✅ 비선형 구조 앞서 포스팅에서 스택과 큐를 배우며 선형 구조와 비선형 구조에 대해 언급했었다. 선형 구조는 자료들이 순서를 가지고 연속된 자료구조를 의미하며 비선형 구조는 자료를 일렬로 나열하기 힘들고 자료의 순서가 불규칙해 연결 관계가 복잡한 구조를 의미한다. 바로 이 비선형 구조의 대표적인 예가 트리(Tree)와 그래프(Graph)이다. ✅ 그래프 트리는 사실 그래프의 특수한 형태 중 하나이다. 따라서 트리를 이해하기 위해서는 그래프의 정의부터 알 필요가 있다. 그래프(Graph)는 정점(vertex)과 간선(edge)으로 이루어져 있는 자료구조이다. 정점(vertex)은 자료, 상태 등 값을 담고있는 것을 의미하며 노드라고 부르기도 한다. 간선(edge)은 정.. 2022. 4. 7. 이전 1 다음
