이진트리

1차원배열에 노드 관계랑 값을 저장할수 있다.

1)이진트리 초기화
2)이진트리 DFS돌리기

이진트리 배우는이유
힙에서도 쓰임

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

//이진트리로 dfs돌리기

char names[20] = "_ABCDEFI____GH";
void run(int now) {
	
	if (now >= 20)return;
	if (!(names[now]>='A'&&names[now]<='Z'))return;
	int left = 2 * now;
	int right = 2 * now + 1;
	cout << names[now] << " ";
	run(left);
	run(right);
}

int main() {

	run(1);


	return 0;
}

[출력]
A B D E C F G H I

이진트리는 노드번호가 정해져 있다.

[문제]

#include <iostream>
#include <cstring>
#include <string>

using namespace std;

char names[20] = "_713_649____5";

void run(int now) {
	
	if (now >= 20)return;
	if (names[now]=='_')return;
	cout << names[now] << " ";
	int left = now * 2;
	int right = now * 2 + 1;
	run(left);
	run(right);
	//run(갈수있는곳)

}

int main() {

	run(1);
	return 0;
}

[출력]
7 1 6 3 4 5 9

2)다른 아이디어 코드
선택하지 않는것에 0 넣는다.

[코드]

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

int arr[13] = { 0,7,1,3,0,6,4,9,0,0,0,0,5 };

void run(int now) {
	if (now >= 13)return;
	if (arr[now] == 0)return;


	int left = now * 2;
	int right = now * 2 + 1;

	cout << arr[now] << " ";
	run(left);
	run(right);
}
int main() {

	run(1);

	return 0;
}

[출력]
7 1 6 3 4 5 9