[Algorithm] ๐๋ฐฑ์ค 1991 ํธ๋ฆฌ ์ํ
0. ๋ฌธ์
์ด์ง ํธ๋ฆฌ๋ฅผ ์ ๋ ฅ๋ฐ์ ์ ์ ์ํ(preorder traversal), ์ค์ ์ํ(inorder traversal), ํ์ ์ํ(postorder traversal)ํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์๋ฅผ ๋ค์ด ์์ ๊ฐ์ ์ด์ง ํธ๋ฆฌ๊ฐ ์ ๋ ฅ๋๋ฉด,
- ์ ์ ์ํํ ๊ฒฐ๊ณผ : ABDCEFG //
(๋ฃจํธ) (์ผ์ชฝ ์์) (์ค๋ฅธ์ชฝ ์์)- ์ค์ ์ํํ ๊ฒฐ๊ณผ : DBAECFG //
(์ผ์ชฝ ์์) (๋ฃจํธ) (์ค๋ฅธ์ชฝ ์์)- ํ์ ์ํํ ๊ฒฐ๊ณผ : DBEGFCA //
(์ผ์ชฝ ์์) (์ค๋ฅธ์ชฝ ์์) (๋ฃจํธ)
๊ฐ ๋๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์๋ ์ด์ง ํธ๋ฆฌ์ ๋ ธ๋์ ๊ฐ์ N(1โคNโค26)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ๊ฑธ์ณ ๊ฐ ๋ ธ๋์ ๊ทธ์ ์ผ์ชฝ ์์ ๋ ธ๋, ์ค๋ฅธ์ชฝ ์์ ๋ ธ๋๊ฐ ์ฃผ์ด์ง๋ค. ๋ ธ๋์ ์ด๋ฆ์ A๋ถํฐ ์ฐจ๋ก๋๋ก ์๋ฌธ์ ๋๋ฌธ์๋ก ๋งค๊ฒจ์ง๋ฉฐ, ํญ์ A๊ฐ ๋ฃจํธ ๋ ธ๋๊ฐ ๋๋ค. ์์ ๋ ธ๋๊ฐ ์๋ ๊ฒฝ์ฐ์๋ .์ผ๋ก ํํ๋๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์ ์ ์ํ, ๋์งธ ์ค์ ์ค์ ์ํ, ์ ์งธ ์ค์ ํ์ ์ํํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ค. ๊ฐ ์ค์ N๊ฐ์ ์ํ๋ฒณ์ ๊ณต๋ฐฑ ์์ด ์ถ๋ ฅํ๋ฉด ๋๋ค.
1. ์์ด๋์ด
ํธ๋ฆฌ ํด๋์ค๋ฅผ ์ ๊ตฌํํ๋ ๊ฒ ํต์ฌ
๐ก ๊ฐ๊ณผ ๋
ธ๋๋ฅผ ๋ณ์๋ก ๊ฐ์ง๋ Node ํด๋์ค ์์ฑ
๐ก Node๋ค์ ์ด์ Tree ํด๋์ค ์์ฑ
๐ก Tree์์ Node๋ฅผ ์์ฑํ๋ createNode ํจ์
๐ก Node์ ์์น๋ฅผ ์ฐพ๋ searchNode ํจ์ ์์ฑ
๐ก ํธ๋ฆฌ ์ํ ํจ์ ์์ฑ
2. ํต์ฌ ํ์ด
1) ๊ฐ๊ณผ ๋ ธ๋๋ฅผ ๋ณ์๋ก ๊ฐ์ง๋ Node ํด๋์ค ์์ฑ
static class Node{
char value;
Node left;
Node right;
Node(char value){
this.value = value;
}
}
- Node๋ค์ ์ด์ Tree ํด๋์ค ์์ฑ
static class Tree{
Node root;
...
}
- Tree์์ Node๋ฅผ ์์ฑํ๋ createNode ํจ์
void createNode(char value, char left, char right) {
if(root == null) {
root = new Node(value);
if(left != '.')
root.left = new Node(left);
if(right != '.')
root.right = new Node(right);
} else {
searchNode(root, value, left, right);
}
}
- Node์ ์์น๋ฅผ ์ฐพ๋ searchNode ํจ์ ์์ฑ
void searchNode(Node root, char value, char left, char right) {
if(root == null)
return;
else if(root.value == value) {
if(left != '.')
root.left = new Node(left);
if(right != '.')
root.right = new Node(right);
} else {
searchNode(root.left, value, left, right);
searchNode(root.right, value, left, right);
}
}
- ํธ๋ฆฌ ์ํ ํจ์ ์์ฑ
public void preorder(Node root) {
System.out.print(root.value);
if(root.left != null) preorder(root.left);
if(root.right != null) preorder(root.right);
}
public void inorder(Node root) {
if(root.left != null) inorder(root.left);
System.out.print(root.value);
if(root.right != null) inorder(root.right);
}
public void postorder(Node root) {
if(root.left != null) postorder(root.left);
if(root.right != null) postorder(root.right);
System.out.print(root.value);
}
3. ์ฝ๋
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Graph_6 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Tree tree = new Tree();
for(int i=0; i<n; i++) {
char[] c = br.readLine().replaceAll(" ","").toCharArray();
tree.createNode(c[0], c[1], c[2]);
}
tree.preorder(tree.root);
System.out.println();
tree.inorder(tree.root);
System.out.println();
tree.postorder(tree.root);
}
static class Node{
char value;
Node left;
Node right;
Node(char value){
this.value = value;
}
}
static class Tree{
Node root;
void createNode(char value, char left, char right) {
if(root == null) {
root = new Node(value);
if(left != '.')
root.left = new Node(left);
if(right != '.')
root.right = new Node(right);
} else {
searchNode(root, value, left, right);
}
}
void searchNode(Node root, char value, char left, char right) {
if(root == null) return;
else if(root.value == value) {
if(left != '.')
root.left = new Node(left);
if(right != '.')
root.right = new Node(right);
} else {
searchNode(root.left, value, left, right);
searchNode(root.right, value, left, right);
}
}
public void preorder(Node root) {
System.out.print(root.value);
if(root.left != null) preorder(root.left);
if(root.right != null) preorder(root.right);
}
public void inorder(Node root) {
if(root.left != null) inorder(root.left);
System.out.print(root.value);
if(root.right != null) inorder(root.right);
}
public void postorder(Node root) {
if(root.left != null) postorder(root.left);
if(root.right != null) postorder(root.right);
System.out.print(root.value);
}
}
}
4. ๊ฒฐ๊ณผ
์ฑ๊ณตโจ
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm] ๐๋ฐฑ์ค 1991 ํธ๋ฆฌ ์ํ), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kha0318/Algorithm-๋ฐฑ์ค-1991-ํธ๋ฆฌ-์ํ์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค