|
package com.eugeneprogram.tree;
import java.util.ArrayList;
public class Queue { private ArrayList <Object>queue; //queue를 배열로 구성. public Queue() { queue = new ArrayList<Object>(); }
/* * queue에 추가 명령어. */ public void push(Object o) { queue.add(o); }
/* * queue의 맨앞 값 반환 후 삭제 명령어. */ public Object pop() { return queue.remove(0); }
/* * queue가 공백인지 아닌지 판별하는 명령어. * queue가 공백이거나 크기가 0일경우 true 반환, 그렇지 않으면 false 반환. */ public boolean isEmpty() { if (null == queue || queue.size() == 0) return true; else return false; } } |
|
package com.eugeneprogram.tree;
public class Node { private int data; //노드의 값 private Node leftChild; //왼쪽자식노드 private Node rightChild; //오른쪽자식노드
public Node(int data) { this.data = data; this.leftChild= null; this.rightChild = null; }
/* * 왼쪽자식노드 조회. */ public Node getLeftChild() { return this.leftChild; }
/* * 데이터 조회. */ public int getData() { return data; }
/* * 데이터 설정. */ public void setData(int data) { this.data = data; }
/* * 오른쪽자식노드 조회. */ public Node getRightChild() { return rightChild; }
/* * 오른쪽자식노드 설정. */ public void setRightChild(Node rightChild) { this.rightChild = rightChild; }
/* * 왼쪽자식노드 설정. */ public void setLeftChild(Node leftChild) { this.leftChild = leftChild; } }
|
|
package com.eugeneprogram.tree;
public class BinaryTree { /* * Node의 root를 공백으로 만들어주고 시작. */ Node rootNode = null;
/* * 값이 data인 Node추가. */ public void addNode(int data) {
/* * rootNode가 없다면, 즉 이진 트리가 생성되지 않았을 때 주어진 데이타로 노드를 생성하여 rootNode로. */ if(rootNode == null) { rootNode = new Node(data); }
/* * rootNode가 공백이 아니라면 실행. * 새로운 Queue인 queue를 생성. * queue에 rootNode의 값 추가. */ else { Queue queue = new Queue(); queue.push(rootNode);
/* * queue가 공백이 아니라면 반복. * queue에 맨앞에 있는 값을 삭제하고 반환하여 tempNode에 대입한다. */ while (!queue.isEmpty()) {
Node tempNode = (Node) queue.pop();
/* * tempNode의 왼쪽자식노드의 값이 공백이 아니라면 실행. * queue에 tempNode의 왼쪽자식노드의 값을 추가. */ if (tempNode.getLeftChild() != null) { queue.push(tempNode.getLeftChild());
/* * tempNode의 오른쪽자식노드의 값이 공백이 아니라면 실행. * queue에 tempNode의 오른쪽자식노드의 값을 추가. */ if (tempNode.getRightChild() != null) { queue.push(tempNode.getRightChild()); }
/* * tempNode의 오른쪽자식노드의 값이 공백이라면 실행. * data값을 갖는 노드를 tempNode의 오른쪽자식노드로 설정. * queue에 data값 추가. * 반복문 중단. */ else { tempNode.setRightChild(new Node(data)); queue.push(data); break; } }
/* * tempNode의 왼쪽자식노드의 값이 공백이라면 실행. * data값을 갖는 노드를 tempNode의 왼쪽자식노드로 설정. * queue에 data값 추가. * 반복문 중단. */ else { tempNode.setLeftChild(new Node(data)); queue.push(data); break; }
} } }
/* * 중위순회 */ public void inorder(Node node) {
/* * 노드값이 공백이 아니라면 실행. */ if(node != null) { /* * node의 왼쪽자식노드의 값이 공백이 아니라면 실행. * (리커시브) node의 왼쪽자식노드로 inorder명령어 실행. */ if(node.getLeftChild() != null) { inorder(node.getLeftChild()); } /* * node의 값 출력. */ System.out.print(node.getData()+" "); /* * node의 오른쪽자식노드의 값이 공백이 아니라면 실행. * (리커시브) node의 오른쪽자식노드로 inorder명령어 실행. */ if(node.getRightChild() != null) { inorder(node.getRightChild()); } } }
/* * 전위순회 */ public void preorder(Node node) { /* * node의 값이 공백이 아닐경우 실행. */ if(node != null) { /* * node의 값 출력. */ System.out.print(node.getData()+" "); /* * node의 왼쪽자식노드의 값이 공백이 아닐경우 실행. * (리커시브) node의 왼쪽자식노드로 preorder명령어 실행. */ if(node.getLeftChild() != null) { preorder(node.getLeftChild()); } /* * node의 오른쪽자식노드의 값이 공백이 아닐경우 실행. * (리커시브) node의 오른쪽자식노드로 preorder명령어 실행. */ if(node.getRightChild() != null) { preorder(node.getRightChild()); } } }
/* * 후위순회 */ public void postorder(Node node) { /* * node의 값이 공백이 아닐경우 실행. */ if(node != null) { /* * node의 왼쪽자식노드가 공백이 아닐경우 실행. * (리커시브) node의 왼쪽자식노드로 postorder명령어 실행. */ if(node.getLeftChild() != null) { postorder(node.getLeftChild()); } /* * node의 오른쪽자식노드가 공백이 아닐경우 실행. * (리커시브) node의 오른쪽자식노드로 postorder명령어 실행. */ if(node.getRightChild() != null) { postorder(node.getRightChild()); } /* * node의 값 출력. */ System.out.print(node.getData() + " "); } }
/* * 레벨순회 */ public void levelorder(Node node) { /* * 새로운 Queue인 queue 생성. * node값을 queue에 추가. */ Queue queue = new Queue(); queue.push(node);
/* * queue가 공백이 아닐경우 반복실행. * queue의 맨앞에 값을 삭제하고 반환하여 tempNode에 대입. * tempNode의 값을 출력. */ while(!queue.isEmpty()) { Node tempNode = (Node) queue.pop(); System.out.print(tempNode.getData() + " "); /* * tempNode의 왼쪽자식노드가 공백이 아닐경우 실행. * tempNode의 왼쪽자식노드를 queue에 추가. */ if(tempNode.getLeftChild() != null) { queue.push(tempNode.getLeftChild()); } /* * tempNode의 오른쪽자식노드가 공백이 아닐경우 실행. * tempNode의 오른쪽자식노드를 queue에 추가. */ if(tempNode.getRightChild() != null) { queue.push(tempNode.getRightChild()); } } } }
|
|
package com.eugeneprogram.tree;
public class BinaryTreeApp { public static void main(String[] args) { /* * 새로운 이진트리 tree를 생성. * tree에 정수형 1,2,3,4,5,6,7,8를 addNode명령어로 실행. */ BinaryTree tree = new BinaryTree(); tree.addNode(1); tree.addNode(2); tree.addNode(3); tree.addNode(4); tree.addNode(5); tree.addNode(6); tree.addNode(7); tree.addNode(8);
/* * 전위순회 */ System.out.println("Preorder"); tree.preorder(tree.rootNode); System.out.println();
/* * 중위순회 */ System.out.println("Inorder"); tree.inorder(tree.rootNode); System.out.println();
/* * 후위순회 */ System.out.println("Postorder"); tree.postorder(tree.rootNode); System.out.println();
/* * 레벨순회 */ System.out.println("Levelorder"); tree.levelorder(tree.rootNode); System.out.println();
}
} |
Developed by 김지훈, 교통대학교
댓글 0
| 번호 | 제목 | 글쓴이 | 날짜 | 조회 수 |
|---|---|---|---|---|
| 12 | Java 기초 - Parameter를 가진 메쏘드의 선언 | Eugene | 2025.04.16 | 34 |
| 11 | Java 기초 - 메쏘드를 가진 클래스의 선언과 클래스의 객체를 예시화(instantiate)하기 | Eugene | 2024.03.25 | 59 |
| 10 | Java Heap Sort(힙 정렬) | Eugene | 2022.04.12 | 309 |
| 9 | Java Max Heap(자바 맥스 힙) | Eugene | 2021.09.16 | 221 |
| » | Java - Binary Tree(자바 이진 트리) | Eugene | 2021.08.17 | 276 |
| 7 | Java Tree(자바 트리) - 자식 노드들을 리스트 자료구조를 사용하여 구현 | Eugene | 2021.04.01 | 2539 |
| 6 | JAVA Linked List(링크드 리스트) [1] | Eugene | 2021.02.09 | 792 |
| 5 | Java 기초 - 재귀 함수를 이용한 최대값 구하기 | Eugene | 2019.05.14 | 1101 |
| 4 | Java 기초 - while, for [2] | Eugene | 2018.04.05 | 860 |
| 3 | Java 기초 - 조건문 if | Eugene | 2017.11.03 | 757 |
| 2 | Java 기초 - 두 정수 입력 받아 합 구하기 | Eugene | 2017.11.01 | 3771 |
| 1 | Java 기초 - Hello, World! | Eugene | 2017.09.27 | 1780 |