2015년 2월 16일 월요일

20141021 더블 링크드 리스트로 이진 검색 트리 구현

조만간 다시 부모가 한 개인 것을 만드러야 겠다.//2014.10.31

Implements BinarySearchTree using DoubleLinkedList;
내가 확실히 모르는 것
 1. 자료 구조
 2. 알고리즘
 3. Linked List
 4. Double Linked List
 5. Tree
 6. Binary Tree
 7. Java
 8. Exception(예외 처리)

임을 고려한 후 소스를 보면 소오름이 끼칠 것이다.
솔직히 맞는 지도 모르겠고, 이론적으로 적합하게 구현한지도 모르겠다.
그냥 이런게 아닐까 하고 만들어 본것.


그냥 DLL로는 어떻게 트리를 구현하나 찾다가 하도 안나와서 빡쳐서 만듬.
틀린거 있으면 누가좀 알려주세요!? ㅠㅠ
부모가 두개라니... 망했어...

/*
 * 트리 예 :
 *             10
 *       5           11
 *    3     7           12
 *         6 8
 *  
 */
위 트리 보고 구현해봄.

// 클래스 하나
public class DLLTreeNode {
DLLTreeNode leftP; // 좌측 부모
DLLTreeNode leftC; // 좌측 자손
int data; // 값
DLLTreeNode rightC; // 우측 자손
DLLTreeNode rightP; // 우측 부모
// 생성자
public DLLTreeNode(int data) {
this.data = data;
}
// Getter & Setter
public DLLTreeNode getLeftP() {
return leftP;
}
public void setLeftP(DLLTreeNode leftP) {
this.leftP = leftP;
}
public DLLTreeNode getLeftC() {
return leftC;
}
public void setLeftC(DLLTreeNode leftC) {
this.leftC = leftC;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public DLLTreeNode getRightC() {
return rightC;
}
public void setRightC(DLLTreeNode rightC) {
this.rightC = rightC;
}
public DLLTreeNode getRightP() {
return rightP;
}
public void setRightP(DLLTreeNode rightP) {
this.rightP = rightP;
}
}
// 클래스 둘

public class DLLTree {
DLLTreeNode root;

public DLLTree(int data) {
root = new DLLTreeNode(data);
}
// 트리가 잘 만들어 졌는지 확인용 메소드
public DLLTreeNode getLeftP() {
return root.getLeftP();
}
public DLLTreeNode getLeftC() {
return root.getLeftC();
}
public int getData() {
return root.getData();
}
public DLLTreeNode getRightC() {
return root.getRightC();
}
public DLLTreeNode getRightP() {
return root.getRightP();
}
// 확인용 끝
/**
 * <b>이진 검색 트리의 데이터 삽입</b><br>
 * 뿌리 노드의 값보다 작으면 왼쪽 크면 오른쪽 자식이 된다.<br>
 * 부모 노드에 대해서도 마찬가지 <br>
 * 
 * @param data : 삽입할 값을 입력
 */
public void insertData(int data){
if(root != null){
insertData(root, data);
}else{
return;
}
}
private void insertData(DLLTreeNode root, int data){
if(data < root.getData()){
if(root.getLeftC() != null){
insertData(root.getLeftC(), data);
}else{
DLLTreeNode insertNode = new DLLTreeNode(data);
root.setLeftC(insertNode);
insertNode.setRightP(root);
}
}else if(data > root.getData()){
if(root.getRightC() != null){
insertData(root.getRightC(), data);
}else{
DLLTreeNode insertNode = new DLLTreeNode(data);
root.setRightC(insertNode);
insertNode.setLeftP(root);
}
}else{
System.out.println("에러 :+: 같은 값은 입력 ㄴㄴ");
return;
}
}
/**
 * <b>이진 검색 트리의 데이터 삭제</b><br>
 * 뿌리 노드의 값보다 작으면 왼쪽 크면 오른쪽 자식을 검색<br>
 * 해당 노드를 찾을 때 까지 검색 후 삭제 <br>
 * 
 * 1. 자식이 둘 다 없을 때 : 해당 노드 부모의 자식 노드를 null로 set 후 해당 노드의 부모 노드를 null로 set<br>
 * 2. 자식이 둘 다 있을 때 : 해당 노드 부모의 자식 노드를 null로 set 후 자식 노드들을 다시 트리에 삽입(작은 것 부터)<br>
 * 3. 자식이 한 쪽만 있을 때 : 해당 노드의 부모 노드를 해당노드의 자식 노드로 set 후 해당 노드의 자식 노드의 부모 노드를 해당 노드의 부모 노드로 set<br>
 * 
 * @param data : 삭제할 값을 입력
 */
public void deleteData(int data){
if(root != null){
deleteData(root, data);
}else{
return ;
}
}
private void deleteData(DLLTreeNode root, int data){
if(data < root.getData()){
deleteData(root.getLeftC(), data);
}else if(data > root.getData()){
deleteData(root.getRightC(), data);
}else{
if(root.getLeftC() == null && root.getRightC() == null){
if(root.getRightP() != null){
root.getRightP().setLeftC(null);
root.setRightP(null);
}else if(root.getLeftP() != null){
root.getLeftP().setRightC(null);
root.setLeftP(null);
}
}else if(root.getLeftC() != null && root.getRightC() != null){
if(root.getRightP() != null){
DLLTreeNode left = root.getLeftC();
DLLTreeNode right = root.getRightC();
root.getRightP().setLeftC(null);
root.setRightP(null);
insertDataAfterDelete(root, left);
insertDataAfterDelete(root, right);
}else if(root.getLeftP() != null){
DLLTreeNode left = root.getLeftC();
DLLTreeNode right = root.getRightC();
root.getLeftP().setRightC(null);
root.setLeftP(null);
insertDataAfterDelete(root, left);
insertDataAfterDelete(root, right);
}
}else if(root.getLeftC() != null && root.getRightC() == null){
if(root.getRightP() != null){
if(root.getLeftC() != null){
root.getRightP().setLeftC(root.getLeftC());
root.getLeftC().setRightP(root.getRightP());
}else{
root.getLeftP().setRightC(root.getLeftC());
root.getLeftC().setLeftP(root.getLeftP());
}
}else if(root.getLeftP() != null){
if(root.getRightC() != null){
root.getLeftP().setRightC(root.getRightC());
root.getRightC().setLeftP(root.getLeftP());
}else{
root.getLeftP().setRightC(root.getLeftC());
root.getLeftC().setLeftP(root.getLeftP());
}
}
}else{
if(root.getRightP() != null){
if(root.getLeftC() != null){
root.getRightP().setLeftC(root.getLeftC());
root.getLeftC().setRightP(root.getRightP());
}else{
root.getRightP().setLeftC(root.getRightC());
root.getRightC().setRightP(root.getRightP());
}
}else if(root.getLeftP() != null){
if(root.getRightC() != null){
root.getLeftP().setRightC(root.getRightC());
root.getRightC().setLeftP(root.getLeftP());
}else{
root.getLeftP().setRightC(root.getLeftC());
root.getLeftC().setLeftP(root.getLeftP());
}
}
}
}
}
// 자식이 모두 있을 때 다시 루트에 삽입하는 메소드
private void insertDataAfterDelete(DLLTreeNode root, DLLTreeNode subNode) {
if(subNode.getData() < root.getData()){
if(root.getLeftC() != null){
insertDataAfterDelete(root.getLeftC(), subNode);
}else{
root.setLeftC(subNode);
subNode.setRightP(root);
}
}else{
if(root.getRightC() != null){
insertDataAfterDelete(root.getRightC(), subNode);
}else{
root.setRightC(subNode);
subNode.setLeftP(root);
}
}
}

/**
 * <b>이진 검색 트리의 데이터 검색</b><br>
 * 뿌리 노드의 값보다 작으면 왼쪽 크면 오른쪽 자식을 검색<br>
 * 해당 값을 찾을 때 까지 검색 후 노드를 리턴 <br>
 * <br>
 * 모든 검색 후 해당 값을 찾으면 경로를 출력<br>
 * or Print 'Cannot found'
 * 
 * @param data : 검색할 값을 입력
 */
public void searchData(int data){
if(root != null)
searchData(root, data);
else
System.out.println(":+: null :+:");
if(isThere)
System.out.println(path.toString());
}
StringBuffer path = new StringBuffer("path : ");
boolean isThere = true;
private void searchData(DLLTreeNode root, int data) {
if(data < root.getData()){
if(root.getLeftC() != null){
path.append("("+root.getData()+") LeftC -> ");
searchData(root.getLeftC(), data);
}else{
System.out.println("값 읎음");
isThere = false;
}
}else if(data > root.getData()){
if(root.getRightC() != null){
path.append("("+root.getData()+") RightC -> ");
searchData(root.getRightC(), data);
}else{
System.out.println("값 없음");
isThere = false;
}
}else{
path.append(root.getData()+" found! ");
}
}
}

// 실험해본 main 클래스



public class DLLTreeTest {
/*
 * 트리 예 :
 *             10
 *       5           11
 *    3     7           12
 *         6 8
 *  
 */
public static void main(String[] args) {
DLLTree root = new DLLTree(10);
root.insertData(5);
root.insertData(3);
root.insertData(7);
root.insertData(6);
root.insertData(8);
root.insertData(11);
root.insertData(12);
// root.deleteData(8);
root.deleteData(11);
root.searchData(8);
// System.out.println(root.getLeftC().getRightC().getRightC().getData());
// System.out.println(root.getRightC().getData());
// System.out.println(root.getRightC().getRightC().getData());
}

}
작성자: 시간:
라벨:

댓글 없음:

댓글 쓰기

피드 구독하기: 댓글 (Atom)