[자료구조] 트리(Tree) - 이진트리를 레벨단위 리스트로 변형하기

아래의 영상을 바탕으로 작성되었습니다. 좋은영상 감사합니다.
[자료구조 알고리즘] 이진트리를 레벨단위 리스트로 변형하기
https://youtu.be/Y9Ar9eerxQU

(1) .h

코드1

	#pragma once
	#include <iostream>
	#include <algorithm>
	#include <vector>
	#include <queue>
	using namespace std;
	class Node
	{
	public:
	int data;
	Node* left, * right;
	Node(int data) {
	this->data = data;
	this->left = this->right = NULL;
	}
	};
	class Tree
	{
	public:
	Node* root = NULL;
	vector <vector<Node*>> levels;
	Tree(vector<int> a)
	{
	root = bst(a, 0, a.size() - 1);
	}
	Node* bst(vector<int> a, int start, int end)
	{
	if (start <= end)
	{
	int mid = (start + end) / 2;
	Node* newNode = new Node(a[mid]);
	newNode->left = bst(a, start, mid - 1);
	newNode->right = bst(a, mid + 1, end);
	return newNode;
	}
	return NULL;
	}
	void bstToList1()//solutoin1.level과 재귀를 이용
	{
	levels.clear();
	traversal1(levels, root, 0);
	}
	void traversal1(vector <vector<Node*>>& lists, Node* node, int level)
	{
	if (node == NULL) return;
	vector<Node*> list;
	if (lists.size()==level){
	list.push_back(node);
	lists.push_back(list);
	}
	else
	lists[level].push_back(node);
	traversal1(lists, node->left, level + 1);
	traversal1(lists, node->right, level + 1);
	}
	void bstToList2()//solution2. bfs변형을 이용
	{
	levels.clear();
	levels= traversal2(root);
	}
	vector <vector<Node*>> traversal2(Node* node)
	{
	vector<vector<Node*>> result;
	vector<Node*>current;
	if (node != NULL) current.push_back(node);
	result.push_back(current);
	while (!current.empty()){
	vector<Node*>parent = current;
	current.clear();
	for (int i = 0; i < parent.size(); i++)
	{
	if (parent[i]->left) current.push_back(parent[i]->left);
	if (parent[i]->right) current.push_back(parent[i]->right);
	}
	if(!current.empty()) result.push_back(current);
	}
	return result;
	}
	void print()//레벨별 리스트 출력
	{
	for (int i = 0; i < levels.size(); i++)
	{
	for (int j = 0; j < levels[i].size(); j++)
	cout << levels[i][j]->data << " ";
	cout << endl;
	}
	}
	};

view raw 트리_이진트리를 레벨단위 리스트로 변형하기.h hosted with ❤ by GitHub

(2) .cpp

	#include "header.h"
	int main() {
	//정렬 되어있는 배열을 넣는다
	Tree* t = new Tree({ 0,1,2,3,4,5,6,7,8,9 });
	t->bstToList2();
	t->print();
	return 0;
	}

view raw 트리_이진트리를 레벨단위 리스트로 변형하기.cpp hosted with ❤ by GitHub