자료구조 - Tree

자료구조 tree

• 하나의 루트 노드를 갖는 계층형 자료구조
• degree: 노드의 차수 -> 한 노드가 가지는 서브 노드의 수.

Binary Tree ( 이진 트리 )

• 각 노드의 degree가 2이하인 tree로 왼쪽,오른쪽 서브트리로 구성.

1. 포화 이진 트리

• 모든 leaf노드들의 level이 동일하며, 내부노드들의 degree가 2

2. 완전 이진 트리

• 포화 이진트리의 leaf노드들이 오른쪽부터 삭제된 트리

Binary Search Tree (BST, 이진 탐색 트리)

• 이진트리 형태로 각 노드의 왼쪽 서브트리에는 부모 노드보다 작은 값이, 오른쪽 서브트리에는 부모 노드보다 큰 값이 위치하는 트리

• 흐름

1. 시작은 루트
2. 이진 탐색 트리가 null이면 실패.
3. root의 키값이 = x 이면, 탐색은 성공하며 종료
4. 키값 < x 이면, 왼쪽 서브트리에서 탐색.
   키값 > x 이면 , 오른쪽 서브트리에서 탐색.

package javastudy;

import com.sun.source.tree.Tree;

// 트리 구조 노드 연결리스트.
class TreeNode {
  int value;
  TreeNode left;
  TreeNode right;

  public TreeNode(int value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
public class tree {
  TreeNode root; //루트 노드 선언.

  public void insert(int value) {
    TreeNode newNode = new TreeNode(value);
    if (root == null) { //root가 없으면?
      root = newNode; //새로 생성된 node가 root
    }else{ //root가 있다면?
      TreeNode current = root;// current 변수는 root를 가리킴.

      //비교해야함.
      while (true) {
        if (value < current.value) {
          if (current.left == null) {//왼쪽 서브트리가 없다면
            current.left = newNode;//왼쪽에 서브트리노드를 생성
            return;
          }
          current = current.left; //왼쪽에 서브트리가 있으면 왼쪽 서브트리로 이동.
        } else if (value > current.value) {
          if (current.right == null) {
            current.right = newNode;
            return;
          }
          current = current.right; // 오른쪽 서브트리로 이동
        }
      }
    }
  }

  public void delete(int value) {
    root = deleteNode(root,value);
  }

  TreeNode deleteNode(TreeNode node, int value) {
    if (node == null) {
      return null;// 찾는 노드가 존재하지 않는다.
    }

    if (value < node.value) {
      node.left = deleteNode(node.left,value); //왼쪽 서브트리 삭제.
    } else if (value > node.value) {
      node.right = deleteNode(node.right,value);// 오른쪽 서브트리 삭제.
    }else{
      //삭제할 노드가 발견됨 -> 자식이 없는경우 총 3가지로 구분
      //1. 해당 노드의 자식이 없는경우
      if(node.left == null && node.right == null){
        return null; // 해당 노드를 삭제.
      }
      //2. 해당 노드의 자식이 한개인 경우.
      else if(node.left == null){
        return node.right; //오른쪽 자식노드로 대체.
      }else if(node.right == null){
        return node.left; //왼쪽 자식노드로 대체
      }else {
        //3.해당 노드의 자식이 두개인 경우.
        TreeNode successor = node.right; //오른쪽 서브트리에서 최소값을 찾았을때.
        while(successor.left != null){ //자식노드의 왼쪽이 비어있다면
          successor = successor.left;
        }
      }


    }
    return node;
  }
  // 특정 값 검색
  public boolean search(int value) {
    TreeNode current = root;

    while (current != null) {//노드가 있다..
      if (current.value == value) {
        return true; // 값이 존재하는 경우
      } else if (value < current.value) {
        current = current.left; // 왼쪽으로 이동
      } else {
        current = current.right; // 오른쪽으로 이동
      }
    }

    return false; // 값이 존재하지 않는 경우
  }

  //전위 순회
  public void preOrder(){
    preOrderTraversal(root);

  }
  private void preOrderTraversal(TreeNode node){
    if(node != null){
      System.out.print(node.value +" ");
      preOrderTraversal(node.left);
      preOrderTraversal(node.right);
    }
  }
  //중위 순회
  public void inOrder(){
    inOrderTraversal(root);
  }
  private void inOrderTraversal(TreeNode node){
    if(node != null){
      inOrderTraversal(node.left);
      System.out.print(node.value+" ");
      inOrderTraversal(node.right);
    }
  }
  public void postOrder(){
    postOrderTraversal(root);
  }
  //후위 순회
  private void postOrderTraversal(TreeNode node){
    if(node != null){
      postOrderTraversal(node.left);
      postOrderTraversal(node.right);
      System.out.print(node.value+" ");
    }
  }

  public static void main(String[] args) {
    tree t = new tree();

    t.insert(50);
    t.insert(30);
    t.insert(20);
    t.insert(40);
    t.insert(70);
    t.insert(60);
    t.insert(80);

    t.inOrder(); //20 30 40 50 60 70 80
    t.postOrder();//20 40 30 60 80 70 50  
    t.preOrder();//50 30 20 40 70 60 80 


  }

}