[자료구조]그래프 트리

그래프,트리

그래프란 ?

노드를 다양한 방법으로 연결하여 표현하는 자료구조

일반적으로 탐색을 하기위해선 반복문같은 프로그래밍 문법이 아니라, (DFS,BFS)알고리즘을 써야한다.

트리란 ?

가지처럼 연결되어있는 비선형 자료구조이다.

#include<iostream>

int main(){
	int map[4][4] = {};
	int target = 1 ;
	for(int i = 0; i < 4; i++){
	
	cout << target << "번 노드 사용가능:";
	if(map[target][i] != 0{
	cout << i << "번";
	}
	return 0;
}

가중치가 있는 그래프

---

트리

1. 그래프 안에 포함되는 자료구조중 하나이다.
2. 단방향 그래프
3. 싸이클이 존재하지 않아야 한다.
4. 부모 자식 관계로 표현이 가능하다.
5. 데이터를 빠르게 검색하기 위해 사용한다.

<트리를 구성하는="" 요소들=""> - 노드 - 간선 - 루트 노드 - 부모 노드 - 자식노드 - 형제노드 - 외부 노드 - 내부노드,비단말 노드, 가지노드 - 깊이 - 높이 --- ## 트리의 종류 - 편향트리 - 이진트리 - 이진 탐색 트리 - 균형 트리 --- ## 트리 코딩하기 1. 인접행렬  ```cpp char value[5] = { 'D','E','F','Q','A' }; int matrix[5][5] = { 0,1,1,1,0, 0,0,0,0,1, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, }; ``` 1. 리스트로 표현  1. 1차원 배열로 표현   rootNode를 1번으로 왼쪽자식은 부모 index * 2 오른쪽 자식은 부모 index *2 + 1