알고리즘 공부 [Tree]

트리는 제약 조건이 하나만 있는 간단한 구조이다.

1. 싸이클의 형태를 띄우지 않는다.

 

이진트리(Binary Search Tree)는 해당 제약 조건에서 2개의 제약 조건이 더 붙는다.

1. 노드의 브랜치는 2개로 제약된다.

2. 노드의 왼쪽은 자신보다 작은 값, 오른쪽은 큰 값을 가지고있는다.

 

import java.util.*;

public class Main
{
public static void main(String[] args) {
 NodeMgmt mgmt = new NodeMgmt();
 mgmt.insertValue(14);
 mgmt.insertValue(12);
 mgmt.insertValue(13);
 mgmt.insertValue(16);
 mgmt.showAllNodes(mgmt.head);
}
}
class NodeMgmt{
    Node head;
    class Node{
        Node left;
        Node right;
        int value;
        public Node(int value)
        {
            this.value = value;
        }
    }
    public void insertValue(int value)
    {
        if(this.head == null)
        {
            head = new Node(value);
        }
        else
        {
            Node find = head;
            while(true)
            {
                if(value > find.value)
                {
                    if(find.right == null)
                    {
                        find.right = new Node(value);
                        break;
                    }
                    else
                    find = find.right;
                }
                else
                {
                    if(find.left == null)
                    {
                        find.left = new Node(value);
                        break;
                    }
                    else
                    find = find.left;
                }
            }
        }
    }
    
}
     
쉽게, 단순히 넣는 방식은 위와 같다. null체크 후에, 값을 넣어주는 것이다 별로 공부해야되거나 주의 해야할 점은 없다.

만약에 해당 특정 값에 대한 find함수를 작성한다고 하면 아래와 같다.

  public Node searchNode(int data)
    {
        if(head == null)
        {
            return null;
        }
        else{
            Node findNode = this.head;
            while(findNode != null){
            if(findNode.value == data)
            {
                return findNode;
            }
            else if(findNode.value > data){
              
                findNode = findNode.left;
            }
            else{
                
                findNode = findNode.right;
            }
            }
        }
        return null;
    }

 

해당 소스를 기준으로, Search를 하던, Search이후에 insert를 하면 된다,