binaryTree.js

function Node(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = show;
}

function show() {
    return this.data;
}

function BST() {
    this.root = null;
    this.insert = insert;

    //함수
    this.inOrder = inOrder;
    this.preOrder = preOrder;
    this.postOrder = postOrder;
    this.getMin = getMin;
    this.getMax = getMax;
    this.find = find;
    this.remove = remove;
}

function insert(data) {
    var n = new Node(data, null, null);

    //루트 노드가 존재하는지 검사.
    if (this.root == null) {
        this.root = n;
    }
    
    //루트 노드가 존재하는경우
    else {

        //루트 노드를 현재 노드로 지정
        var current = this.root;
        var parent;
        while (true) {

            //부모노드를 현재노드로 지정;
            parent = current;

            //만약 입력된 데이터가 현재노드의 데이터보다 작은경우
            if (data < current.data) {

                //현재노드에 현재노드의 왼쪽자식을 지정한다.
                current = current.left;

                //만약 현재 노드가 비었으면
                if (current == null) {

                    //부모노드의 왼쪽자식에 입력된 데이터 노드를 지정한다.
                    parent.left = n;
                    break;
                }
            }

             //만약 입력된 데이터가 현재노드의 데이터보다 클경우
            else {

                //현재노드에 현재노드의 우측자식을 지정한다.
                current = current.right;

                //만약 현재노드가 비었으면
                if (current == null) {

                    //부모노드의 우측자식에 입력된 데이터 노드를 지정한다.
                    parent.right = n;
                    break;
                }
            }
        }
    }
}

//중위탐색
//1. 좌측서브트리
//2. 루트
//3. 우측서브트리
function inOrder(node) {
    if (!(node == null)) {
        inOrder(node.left);
        console.log(node.show() + " ");
        inOrder(node.right);
    }
}

//후위탐색
//1. 좌측서브트리
//2. 우측서브트리
//3. 루트
function preOrder(node){
    if(!(node == null)){
        console.log(node.show() + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
}

//후위탐색
//1. 좌측서브트리
//2. 우측서브트리
//3. 루트
function postOrder(node){
    if(!(node==null)){
        postOrder(node.left);
        postOrder(node.right);
        console.log(node.show()+" ");
    }
}

var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);

console.log("Inorder traversal: ");
inOrder(nums.root);

console.log("preOrder traversal: ");
preOrder(nums.root);

console.log("postOrder traversal: ");
postOrder(nums.root);

var min = nums.getMin();
console.log("The minimum value of the BST is: " +min);

var max = nums.getMax();
console.log("The maximum value of the BST is: "+ max);


console.log("find function test --> search 23");
var value = 23;
var found = nums.find(value);
if(found !=null){
    console.log("FOUND " +value +" in the BST");
}
else
{
    console.log(value + " was not found in the BST");
}

nums.remove(23);
console.log("Inorder traversal: ");
inOrder(nums.root);


//최소값 검색
//항상 작은값이 좌측에 저장되는 BST 특성을 이용
function getMin(){
    var current = this.root;
    while(!(current.left == null)){
        current = current.left;
    }
    return current.data;
}

//최대값 검색
//항상 큰값이 우측에 저장되는 BST 특성을 이용
function getMax(){
    var current = this.root;
    while(!(current.right == null)){
        current = current.right;
    }
    return current.data;
}

//특정 값 검색
function find(data){
    var current = this.root;

    //해당 데이터를 찾을때 까지
    while(current.data !=data){

        //만약 찾아야할 데이터가 현재 노드의 데이터보다 작을때
        if(data < current.data){

            //좌측 노드 할당
            current = current.left;
        }

        //만약 찾아야할 데이터가 현재 노드의 데이터보다 클때
        else{

            //우측 노드 할당
            current = current.right;
        }
        if(current == null){
            return null;
        }
    }
    return current;
}


//특정값을 가진 노드 삭제
function remove(data){
    root = removeNode(this.root,data);
}

function removeNode(node,data){
    if(node ==null){
        return null;

    }
    //삭제할 노드를 찾았을때
    if(data==node.data){

        //자식이 아예 없는 노드인 경우
        if(node.left == null && node.right == null){

            //null을 반환함으로써 노드 삭제
            return null;
        }

        //좌측 자식이 없는경우
        if(node.left == null){

            //우측 자식을 반환(우측 자식으로 갱신 - 현재 노드의 삭제를 의미)
            return node.right;
        }

        //양쪽 노드가 존재하는경우
        //삭제하는 노드의 기준으로 오른쪽 서브트리에서 가장 작은값을 가진 
        //노드를 검색

        //우측 서브트리내에서 가장 작은값을 찾아 
        //삭제하려는 노드를 대체한다.
        var tempNode = getSmallest(node.right);
        node.data = tempNode.data;
        node.right = removeNode(node.right, tempNode);
        return node;
    }

    //삭제 대상이 현재 노드의 데이터보다 작을때
    else if(data<node.data){
        node.left = removeNode(node.left,data);
        return node;
    }
    //삭제 대상이 현재 노드의 데이터보다 클때
    else{
        node.right = removeNode(node.right,data);
        return node;
    }

}
function getSmallest(node){
    var current = node;
    while(!(current.left == null)){
        current = current.left;
    }
    return current;
}