0401_ 이진 탐색 트리 (Binary Search Tree : BST) // Add 메서드

이진탐색트리 쉰회
주로 중위 순회 방식을 사용한다.
이진탐색 트리의 구현
이진트리와 동일한 노드 클래스를 사용한다.
루트 노드를 배누 프라이빗필드로. 필요한 메서드는 퍼블릭,
보통 노드를 외부에 노출 시킬 필요가 없어서 , 노드 클래스 역시 Nested private class로 구현

노드 키 데이타를 추가할때 사용하는 Add, 검색하는 Search. 삭제 Remove

데이타를 추가하기 위해서는 먼저 루트 노드로부터 키를 비교한다.
좌,우 노드로 계속 이동해 내려가면서 새키를 추가할 장소를 찾는다.
즉, 키가 루트 혹은 서브트리의 루트보다 작으면 왼쪽, 크면 오른쪽으로 이동
마약 이동한 노드가 null이 되면 그곳이 새 노드를 넣을 곳

 

 

---

 

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace study19
{
    public class BinarySearchTree
    {
        private BSTNode root;
        public BinarySearchTree()
        {

        }

        public void Add(int data) {
            if (root == null) {
                this.root = new BSTNode(data);
                return;
            }
            //비교
            var node = this.root;
            while (node != null) {
                //추가하려는 값과 노드의 값을 비교
               var result = data.CompareTo(node.data);
                if (result == 0){
                    //같다.
                    throw new ApplicationException("동일함");
                }
                else if (result < 0){
                    //작다
                    if (node.left == null){
                        node.left = new BSTNode(data);
                        break;
                    }
                    else{
                        node = node.left;
                    }
                }
                else{
                    //크다.
                    if (node.right == null)
                    {
                        node.right = new BSTNode(data);
                        break;
                    }
                    else
                    {
                        node = node.right;
                    }
                }
            }
        }
    }
}