Node์ Edge๋ก ์ด๋ฃจ์ด์ง ์๋ฃ๊ตฌ์กฐ
Tree์ ํน์ฑ์ ์ดํดํ์
ํธ๋ฆฌ๋ ๊ฐ์ ๊ฐ์ง ๋
ธ๋(Node)
์ ์ด ๋
ธ๋๋ค์ ์ฐ๊ฒฐํด์ฃผ๋ ๊ฐ์ (Edge)
์ผ๋ก ์ด๋ฃจ์ด์ ธ์๋ค.
๊ทธ๋ฆผ ์ ๋ฐ์ดํฐ 1์ ๊ฐ์ง ๋
ธ๋๊ฐ ๋ฃจํธ(Root) ๋
ธ๋
๋ค.
๋ชจ๋ ๋ ธ๋๋ค์ 0๊ฐ ์ด์์ ์์(Child) ๋ ธ๋๋ฅผ ๊ฐ๊ณ ์์ผ๋ฉฐ ๋ณดํต ๋ถ๋ชจ-์์ ๊ด๊ณ๋ก ๋ถ๋ฅธ๋ค.
์๋์ฒ๋ผ ๊ฐ์กฑ ๊ด๊ณ๋๋ฅผ ๊ทธ๋ฆด ๋ ํธ๋ฆฌ ํ์์ผ๋ก ๋ํ๋ด๋ ๊ฒฝ์ฐ๋ ๋ง์ด ๋ดค์ ๊ฒ์ด๋ค. ์๋ฃ๊ตฌ์กฐ์ ํธ๋ฆฌ๋ ์ด ๋ฐฉ์์ ๊ทธ๋๋ก ๊ตฌํํ ๊ฒ์ด๋ค.
ํธ๋ฆฌ๋ ๋ช ๊ฐ์ง ํน์ง์ด ์๋ค.
- ํธ๋ฆฌ์๋ ์ฌ์ดํด์ด ์กด์ฌํ ์ ์๋ค. (๋ง์ฝ ์ฌ์ดํด์ด ๋ง๋ค์ด์ง๋ค๋ฉด, ๊ทธ๊ฒ์ ํธ๋ฆฌ๊ฐ ์๋๊ณ ๊ทธ๋ํ๋ค)
- ๋ชจ๋ ๋ ธ๋๋ ์๋ฃํ์ผ๋ก ํํ์ด ๊ฐ๋ฅํ๋ค.
- ๋ฃจํธ์์ ํ ๋ ธ๋๋ก ๊ฐ๋ ๊ฒฝ๋ก๋ ์ ์ผํ ๊ฒฝ๋ก ๋ฟ์ด๋ค.
- ๋ ธ๋์ ๊ฐ์๊ฐ N๊ฐ๋ฉด, ๊ฐ์ ์ N-1๊ฐ๋ฅผ ๊ฐ์ง๋ค.
๊ฐ์ฅ ์ค์ํ ๊ฒ์, ๊ทธ๋ํ
์ ํธ๋ฆฌ
์ ์ฐจ์ด๊ฐ ๋ฌด์์ธ๊ฐ์ธ๋ฐ, ์ด๋ ์ฌ์ดํด์ ์ ๋ฌด๋ก ์ค๋ช
ํ ์ ์๋ค.
์ฌ์ดํด์ด ์กด์ฌํ์ง ์๋ ๊ทธ๋ํ
๋ผ ํ์ฌ ๋ฌด์กฐ๊ฑด ํธ๋ฆฌ
์ธ ๊ฒ์ ์๋๋ค ์ฌ์ดํด์ด ์กด์ฌํ์ง ์๋ ๊ทธ๋ํ๋ Forest
๋ผ ์ง์นญํ๋ฉฐ ํธ๋ฆฌ์ ๊ฒฝ์ฐ ์ธ์ดํด์ด ์กด์ฌํ์ง ์๊ณ ๋ชจ๋ ๋
ธ๋๊ฐ ๊ฐ์ ์ผ๋ก ์ด์ด์ ธ ์์ด์ผ ํ๋ค
ํธ๋ฆฌ๋ฅผ ์ํํ๋ ๋ฐฉ์์ ์ด 4๊ฐ์ง๊ฐ ์๋ค. ์์ ๊ทธ๋ฆผ์ ์์๋ก ์งํํด๋ณด์
-
๊ฐ ๋ถ๋ชจ ๋ ธ๋๋ฅผ ์์ฐจ์ ์ผ๋ก ๋จผ์ ๋ฐฉ๋ฌธํ๋ ๋ฐฉ์์ด๋ค.
(๋ถ๋ชจ โ ์ผ์ชฝ ์์ โ ์ค๋ฅธ์ชฝ ์์)
1 โ 2 โ 4 โ 8 โ 9 โ 5 โ 10 โ 11 โ 3 โ 6 โ 13 โ 7 โ 14
-
์ผ์ชฝ ํ์ ํธ๋ฆฌ๋ฅผ ๋ฐฉ๋ฌธ ํ ๋ถ๋ชจ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๋ ๋ฐฉ์์ด๋ค.
(์ผ์ชฝ ์์ โ ๋ถ๋ชจ โ ์ค๋ฅธ์ชฝ ์์)
8 โ 4 โ 9 โ 2 โ 10 โ 5 โ 11 โ 1 โ 6 โ 13 โ 3 โ14 โ 7
-
์ผ์ชฝ ํ์ ํธ๋ฆฌ๋ถํฐ ํ์๋ฅผ ๋ชจ๋ ๋ฐฉ๋ฌธ ํ ๋ถ๋ชจ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๋ ๋ฐฉ์์ด๋ค.
(์ผ์ชฝ ์์ โ ์ค๋ฅธ์ชฝ ์์ โ ๋ถ๋ชจ)
8 โ 9 โ 4 โ 10 โ 11 โ 5 โ 2 โ 13 โ 6 โ 14 โ 7 โ 3 โ 1
-
๋ถ๋ชจ ๋ ธ๋๋ถํฐ ๊ณ์ธต ๋ณ๋ก ๋ฐฉ๋ฌธํ๋ ๋ฐฉ์์ด๋ค.
1 โ 2 โ 3 โ 4 โ 5 โ 6 โ 7 โ 8 โ 9 โ 10 โ 11 โ 13 โ 14
public class Tree<T> {
private Node<T> root;
public Tree(T rootData) {
root = new Node<T>();
root.data = rootData;
root.children = new ArrayList<Node<T>>();
}
public static class Node<T> {
private T data;
private Node<T> parent;
private List<Node<T>> children;
}
}