DevAlgorithm

[Data Structure] Binary tree

  1. 1. 이진 트리 (Binary tree)
  2. 2. 이진 트리의 순회 (traversal)
    1. 2.1. preorder
    2. 2.2. postorder
  3. 3. 참조

이진 트리 (Binary tree)

이진 트리는 모든 Node들의 자식 Node가 두 개 이하인 트리를 의미한다.

서브 트리를 왼쪽 서브 트리와 오른쪽 서브 트리로 구분한다.

단말 Node를 제외한 나머지 Node가 두 개의 자식 Node를 가지고 있는 트리를 완전 이진 트리(complete binary tree)라고 한다.

트리의 마지막 level까지 모든 Node가 채워진 이진 트리를 포화 이진 트리(full binary tree)라고 한다.

이진 트리는 Array 또는 Linked list로 구현할 수 있다.

하나의 Node가 left child와 right child 두 개의 pointer를 가진다.

이진 트리의 순회 (traversal)

이진 트리의 순회란 이진 트리의 모든 노드를 특정한 순서대로 한 번씩 방문하는 것이다.

순회하는 방법은 아래와 같이 세 가지가 있다.

  1. preorder (전위)
  2. inorder (중위)
  3. postorder (후위)

preorder

방문 -> 왼쪽 서브 트리 방문 -> 오른쪽 서브 트리 방문```
1
2
3
4
### inorder
```왼쪽 서브 트리 방문 -> 노드 방문 -> 오른쪽 서브 트리 방문

postorder

왼쪽 서브 트리 방문 -> 오른쪽 서브 트리 방문 -> 노드 방문

아래와 같이 Node를 구성하고,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Node {
	private char mData;
	
	private Node leftNode;
	private Node rightNode;
	
	Node(char data) {
		mData = data;
	}
	
	public Node getLeftNode() {
		return leftNode;
	}
	
	public Node getRightNode() {
		return rightNode;
	}
	
	public void setLeftNode(Node newNode) {
		leftNode = newNode;
	}
	
	public void setRightNode(Node newNode) {
		rightNode = newNode;
	}
	
	public char getData() {
		return mData;
	}
}

Binary Tree를 이렇게 만든다. preorder, inorder, postorder는 결국 어느 부분에서 확인하느냐에 따라 다르다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class BinaryTree {
	private Node mRoot;
	
	BinaryTree(Node data) {
		mRoot = data;
	}
	
	public Node getRoot() {
		return mRoot;
	}
	
	public void preOrder(Node root) {
		
		System.out.print(root.getData() + " ");
		
		if (root.getLeftNode() != null) {
			preOrder(root.getLeftNode());
		}
		if (root.getRightNode() !=null) {
			preOrder(root.getRightNode());
		}
		
	}
	
	public void inOrder(Node root) {
		
		if (root.getLeftNode() != null) {
			inOrder(root.getLeftNode());
		}
		
		System.out.print(root.getData() + " ");
		
		if (root.getRightNode() != null) {
			inOrder(root.getRightNode());
		}
	}
	
	public void postOrder(Node root) {
		if (root.getLeftNode() != null) {
			postOrder(root.getLeftNode());
		}
		
		if (root.getRightNode() != null) {
			postOrder(root.getRightNode());
		}
		
		System.out.print(root.getData() + " ");
	}
}

Main에서 BinaryTree를 구성하고 실행해보면

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Main {
	public static void main(String[] args) {
		BinaryTree bTree = new BinaryTree(new Node('A'));
		
		setTree(bTree);
		
		bTree.preOrder(bTree.getRoot());
		System.out.println();
		bTree.inOrder(bTree.getRoot());
		System.out.println();
		bTree.postOrder(bTree.getRoot());
		
	}
	
	public static void setTree(BinaryTree bTree) {
		bTree.getRoot().setLeftNode(new Node('B'));
		bTree.getRoot().setRightNode(new Node('C'));
		
		bTree.getRoot().getLeftNode().setLeftNode(new Node('D'));
		bTree.getRoot().getLeftNode().setRightNode(new Node('E'));
		
		bTree.getRoot().getLeftNode().getRightNode().setLeftNode(new Node('F'));
	}
}

아래와 같은 결과를 얻을 수 있다.

A B D E F C 
D B F E A C 
D F E B C A

참조

Share