트리 (Tree)

트리 (Tree)

트리란 *계층적인 구조를 표현하기 위한 일상적으로 사용하는 구조이다 ( *비선형 자료구조 )

* 계층적 구조는 일반적으로 조직도를 나타내는 경우이다.

* 비선형이란 일직선으로 나타내지 못하는 방식이다.

---

트리 값 저장

1. 데이터와 연결 상태를 저장할 클래스 생성 ( 노드 )

2. 각각의 노드들에 값 저장

3. 노드 간 연결 상태 정의

---

1. 데이터와 연결 상태를 저장할 클래스 생성 ( 노드 )

Node 라는 클래스를 만들고,

저장할 값 변수 ( value ) , 왼쪽 연결 노드 ( left ) , 오른쪽 연결 노드 ( right ) 에 대한 정보를 저장할 변수를 생성한다.

---

2. 각각의 노드들에 값 저장

3개의 Node를 생성하고, 우선 leftNode와 rightNode에 대한 정보를 null로 초기화 한다.

---

3. 노드 간 연결 상태 정의

Node1 의 leftNode : Node2

Node1 의 rightNode : Node3

코드 :

Node node1 = tree.addNode(1);
Node node2 = tree.addNode(2); 
Node node3 = tree.addNode(3); 

node1.addLeft(node2);
node1.addRight(node3);

---

기능

Node의 기능

- void addLeft(Node node) : 현재 노드의 좌측에 노드 연결 정보를 추가한다.

- void addRight(Node node) : 현재 노드의 우측에 노드 연결 정보를 추가한다.

- void deleteLeft() : 현재 노드의 좌측 노드 연결 정보를 삭제한다.

- void deleteRight() : 현재 노드의 우측 노드 연결 정보를 삭제한다.

 

Tree

- Node addNode(Object data) : 노드를 새롭게 생선한다.

- void preOrder(Node node) : *전위 순회 방법을 이용해 출력한다.

- void inOrder(Node node) : *중위 순회 방법을 이용해 출력한다.

- void postOrder(Node node) : *후위 순회 방법을 이용해 출력한다.

 

*전위 순회 방법 : 루트 노드를 먼저 순회한 이후 '왼쪽 하위' -> '오른쪽 하위' 순으로 순회하는 방법

*중위 순회 방법 : 왼쪽 가장 하위 노드를 먼저 순회한 이후 '바로 상위 노드' -> '오른쪽 하위' 순으로 순회하는 방법

*후위 순회 방법 : 왼쪽 가장 하위 노드를 먼저 순회한 이후 '오른쪽 하위 노드'-> '바로 상위 노드' 순으로 순회하는 방법

전위 순회 순서 : 1 - 2 - 4 - 5 - 3 - 6 - 7

중위 순회 순서 : 4 - 2 - 5 - 1 - 6 - 3 - 7

후위 순회 순서 : 4 - 5 - 2 - 6 - 7 - 3 - 1

---

package test;

public class Tree {
	
	int count;
	
	public Tree() {
		count = 0;
	}
	
	public class Node {
		Object data;
		Node left;
		Node right;
	
		// 생성 시 매개변수를 받아 초기화하는 방법으로만 선언 가능
		public Node(Object data) {
			this.data = data;
			left = null;
			right = null;
		}

		public void addLeft(Node node) {
			left = node;
			count++;
		}

		public void addRight(Node node) {
			right = node;
			count++;
		}

		public void deleteLeft() {
			left = null;
			count--;
		}

		public void deleteRight() {
			right = null;
			count--;
		}
	}
	
	public Node addNode(Object data) {
		Node n = new Node(data);
		return n;
	}
	
	public void preOrder(Node node) {
		if(node == null) {
			return;
		}
		
		System.out.print(node.data + " ");
		preOrder(node.left);
		preOrder(node.right);
	}

	public void inOrder(Node node) {
		if(node == null) {
			return;
		}
		
		inOrder(node.left);
		System.out.print(node.data + " ");
		inOrder(node.right);
	}

	public void postOrder(Node node) {
		if(node == null) {
			return;
		}
		
		postOrder(node.left);
		postOrder(node.right);
		System.out.print(node.data + " ");
	}
}

---

package test;

import test.Tree.Node;

public class JavaTree {
	public static void main(String[] args) {
		// 트리 생성
		Tree tree = new Tree();
		
		// 노드 생성
		Node node1 = tree.addNode(1);
		Node node2 = tree.addNode(2);
		Node node3 = tree.addNode(3);
		Node node4 = tree.addNode(4);
		Node node5 = tree.addNode(5);
		Node node6 = tree.addNode(6);
		Node node7 = tree.addNode(7);
		
		// 트리 연결관계 생성
		/*  트리 모양       
		 *        1
		 *     2     3
		 *   4  5  6   7
		 */
		node1.addLeft(node2);
		node1.addRight(node3);
		node2.addLeft(node4);
		node2.addRight(node5);
		node3.addLeft(node6);
		node3.addRight(node7);
		
		// 순회
		tree.preOrder(node1);
		System.out.println();
		tree.inOrder(node1);
		System.out.println();
		tree.postOrder(node1);
		System.out.println();
		
		// 삭제
		node2.deleteLeft();
		node3.deleteRight();
		/* 삭제 이후 트리 모양
		 *        1
		 *     2     3
		 *      5  6   
		 */
		
		// 순회
		System.out.println();
		tree.preOrder(node1);
		System.out.println();
		tree.inOrder(node1);
		System.out.println();
		tree.postOrder(node1);
		System.out.println();
	}
}