1. 트리 순회

간단한 알고리즘부터 간단히 작성할 예정이다.

설명위주보다 난 기록을 남기는 위주라 설명은 다른 블로그나 참고할 곳을 링크할꺼다.

 

블로그

1. kks227 

순회에는 간단히 전위, 중위, 후위, 레벨 순회가 있다.

 

각각 영어로 preorder, inorder, postorder, level-order라 불리며 각 예제 코드는 아래와 같다.

 

 

Preorder

	#include<bits/stdc++.h>
	using namespace std;
	struct Node{
	int root, left, right;
	Node(int root=-1, int left=-1, int right=-1):root(root),left(left),right(right){ }
	};
	Node tree[11];
	void makeEdge(int root, int left=-1, int right=-1){
	tree[root] = Node(root, left, right);
	}
	void preorder(int root){
	cout << root << ' ';
	if(tree[root].left != -1)preorder(tree[root].left);
	if(tree[root].right != -1)preorder(tree[root].right);
	}
	int main(){
	//root of tree : 1
	makeEdge(1, 2, 3);
	makeEdge(2, 4);
	makeEdge(3, 5, 6);
	makeEdge(5);
	makeEdge(6, -1, 7);
	makeEdge(4);
	makeEdge(7);
	//preorder : root -> left -> right
	preorder(1);
	}

view raw preorder.cpp hosted with ❤ by GitHub

Inorder

	#include<bits/stdc++.h>
	using namespace std;
	struct Node{
	int root, left, right;
	Node(int root=-1, int left=-1, int right=-1):root(root),left(left),right(right){ }
	};
	Node tree[11];
	void makeEdge(int root, int left=-1, int right=-1){
	tree[root] = Node(root, left, right);
	}
	void inorder(int root){
	if(tree[root].left != -1)inorder(tree[root].left);
	cout << root << ' ';
	if(tree[root].right != -1)inorder(tree[root].right);
	}
	int main(){
	//root of tree : 1
	makeEdge(1, 2, 3);
	makeEdge(2, 4);
	makeEdge(3, 5, 6);
	makeEdge(5);
	makeEdge(6, -1, 7);
	makeEdge(4);
	makeEdge(7);
	//inorder : left -> root -> right
	inorder(1);
	}

view raw inorder.cpp hosted with ❤ by GitHub

Postorder

	#include<bits/stdc++.h>
	using namespace std;
	struct Node{
	int root, left, right;
	Node(int root=-1, int left=-1, int right=-1):root(root),left(left),right(right){ }
	};
	Node tree[11];
	void makeEdge(int root, int left=-1, int right=-1){
	tree[root] = Node(root, left, right);
	}
	void postorder(int root){
	if(tree[root].left != -1)postorder(tree[root].left);
	if(tree[root].right != -1)postorder(tree[root].right);
	cout << root << ' ';
	}
	int main(){
	//root of tree : 1
	makeEdge(1, 2, 3);
	makeEdge(2, 4);
	makeEdge(3, 5, 6);
	makeEdge(5);
	makeEdge(6, -1, 7);
	makeEdge(4);
	makeEdge(7);
	//postorder : left -> right -> root
	postorder(1);
	}

view raw postorder.cpp hosted with ❤ by GitHub

Level-order

	#include<bits/stdc++.h>
	using namespace std;
	struct Node{
	int root, left, right;
	Node(int root=-1, int left=-1, int right=-1):root(root),left(left),right(right){ }
	};
	Node tree[11];
	void makeEdge(int root, int left=-1, int right=-1){
	tree[root] = Node(root, left, right);
	}
	void level_order(int root){
	queue<int> q;
	q.push(root);
	while(!q.empty()){
	int qsize=q.size();
	while(qsize--){
	int now = q.front(); q.pop();
	cout << now << ' ';
	if(tree[now].left != -1)q.push(tree[now].left);
	if(tree[now].right != -1)q.push(tree[now].right);
	}
	}
	}
	int main(){
	//root of tree : 1
	//directed graph
	makeEdge(1, 2, 3);
	makeEdge(2, 4);
	makeEdge(3, 5, 6);
	makeEdge(5);
	makeEdge(6, -1, 7);
	makeEdge(4);
	makeEdge(7);
	//level-order
	level_order(1);
	}

view raw levelorder.cpp hosted with ❤ by GitHub